# Competitive Programming Guides

Various resources

## Online Judges

- Codeforces organizes contests almost every week
- CSES contains a problemset of 300 problems
- AtCoder contains educational contests
- SPOJ has a random problemset
- Leetcode contains problems commonly used in interviews
- CodeChef there are some games you can play
- OJ.UZ contains problems from the olympics
- HackerRank educational problemset
- VJudge is a website that you can see problems from +40 online judges

## Learning Resources

### Books

### Websites

### Youtube Channels

## Chinese Resources

- https://blog.xehoth.cc/
- https://oi.men.ci/
- https://memset0.cn/
- https://www.cnblogs.com/Ning-Mew/
- https://blog.csdn.net/cabi_zgx/article/details/79963427
- https://www.cnblogs.com/Paul-Guderian/

## IOI-Style Contests Hints

- At first read all the problems (that should be at most 30m), try to optimize this
- Spend about 40 minutes on easiest problem, then try to gather points
- Don't spend more than 1 consecutive hour on a single problem
- Take a little 1 or 2 breaks in the middle of the exam
- Debugging usually takes the whole time, don't let it steal your time.

## Debugging Wrong Answer

- Check the constaints of the arrays
- Check if there is a code for input/output
- Check if there could be an overflow (usually caused by multiplication, powers, or factorial)
- Clear & Resize data-structures after each testcase
- Check the for loops starting & ending
- Check the binary search condition
- Handle the edge cases (i.e. 0, 1, even, odd, primes, etc..)
- Check sorting the array
- Make your code either all 0-based or all 1-based
- Check paranthesis when dealing with bitwise operations
- The size of segment tree should be
`4*MAXN`

- Avoid comparing doubles using
`==`

or`!=`

- Avoid using
`memset`

with values other than 0 or -1 - Memorize the answers with indecies, if you sorted them at first
- Output
`Case x:`

Before calculating the answer - In case of processing queries offline, do a
`while`

instead of`if`

to check queries if it was somehow offline - Don't forget
`cout << fixed << setprecision(X);`

if the output is double - In intractive problems, remove fast i/o code
- Split your program to functions, especially in intractive problems
- In case of frequency array/map, check
`++`

instead of`=1`

- Don't forget endlines (
`endl`

,`'\n'`

) - Write a simulater program for the operations and output them
- Don't forget to handle the edge cases in two-pointers
- Don't rely on
`#ifndef ONLINE_JUDGE`

, Rely on some local defines - Probably the given graph has loops, cycles, non-distinct edges

## Debugging Time/Memory Limit

- Calculate the
**exact**time complexity of your code (Online Judges can handle ~$10^8$ complexity in 1 second) - Calculate the
**exact**memory complexity of your code and calculate memory limit in bytes - Calculate the
**exact**amount of interactions in your code (if the problem is interactive) - Try to balance time & memory in the code
- Use
`bitset`

instead of boolean array to optimize memory - Use fast i/o (
`ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)`

in C++) and replace`endl`

with`'\n'`

- Add/Remove depending on system (32/64)
`#define int long long`

- Use
`map`

instead of`unordered_map`

, (Or vice-versa) - Use
`set`

instead of`unordered_set`

, (Or vice-versa) - Compress the numbers (i.e. Distinct Values Queries)
- Use array to count the frequencies instead of
`map`

`sqrt`

takes long time, So use this`i*i <= n`

is more effecient than`i <= sqrt(n)`

- Optimize your seive from $O(N * \log_2{N})$ to $O(N * \log_2{\log_2{N}})$
- Don't clear the arrays & data-structures if there is no testcases
- Use array of sets instead of defining a
`set`

everytime - Use memoization in recursion as much as possible
- Convert a recursive DP to an iterative DP
- Use
`break`

,`continue`

,`goto`

, and`return`

as much as you could - Use Porgan Princible (in 2SUM, you should add to the map while trying to find, not before)
- Use small-to-large decomposition (in trees or in DSU)
- Optimize memory in DP
- In finding shortest route path, put a matrix tells you were you came from, then roll back
- When rolling back to find a path, use a while instead of recursion
- In binary exponintiation, use
`while`

instead of recursion - Write
`const`

in constant variables (i.e.`MOD`

), because the compiler calculate it faster - Write/Remove
`inline`

in functions that you are using - In segment trees, building is faster than updating every element
- Pass parameters by reference if you can
- In DSU, use path compression + order by rank (small to large) optimizations, so your code runs in $O(\alpha(N))$
- Try different versions of the language (i.e. G++17, G++20, Clang20)
- If your code gets TLE on the edge, resubmitting the code may work
- If the solution of the problem is one of the subarrays, try to think how to convert it to two-pointers
- You may precalculate (hardcode) some values on local device and put them in your submission to optimize it
- You may use
`#pragma`

so read vectorization guide, don't put it in your template, it may cause RTE in some online judges other than SOJ - If non of these above worked, probably your algorithm is bad