Competitive Programming Guides

· · tutorial cp

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

Online tools

Track your progress

  • CFTracker: Check solved/unsolved problems for any user, search for a problem.
  • CF Visualizer: Compare and check progress in more details
  • OI Checklist: Track Olympiad Informatics problems that you solved
  • Kenkoooo: Same as CFTracker but for AtCoder

Visualizing problems

Checking duplicate problems

  • OEIS: you can search for any sequence like Fibonacci, Catalan or any more complex sequence.
  • Yuantiji: Problem duplication searcher

Online judges extensions

  • CF Carrot (Firefox/Chrome) : A browser extension that predicts rating changes based on performance
  • CF Analytics (Firefox/Chrome): A browser extention
  • CSES Helper (Chrome): Allows submitting by copy-pasting
  • Competitive Companion: (Firefox/Chrome): Fetches problems tests to your code editor in VSCode and CPEditor

IOI-Style Contests Startegy

  • At first read all the problems (that should be at most 20 minutes), 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 !=, define const double EPS = 1e-9, and use abs(X - Y) <= EPS
  • 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

  1. Calculate the exact time complexity of your code (Online Judges can handle ~$10^8$ complexity in 1 second)</code>
  2. Calculate the exact memory complexity of your code and calculate memory limit in bytes
  3. Calculate the exact amount of interactions in your code (if the problem is interactive)
  4. Try to balance time & memory in the code
  5. Use bitset or vector<bool> instead of boolean array to optimize memory
  6. Use fast i/o (ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) in C++) and replace endl with '\n'
  7. Add/Remove depending on system (32/64) #define int long long
  8. Use map instead of unordered_map, (Or vice-versa)
  9. Use set instead of unordered_set, (Or vice-versa)
  10. Compress the numbers (i.e. Distinct Values Queries)
  11. Use array to count the frequencies instead of map
  12. sqrt takes long time, So use this i*i <= n is more effecient than i <= sqrt(n)
  13. Optimize your seive from $O(N * \log_2{N})$ to $O(N * \log_2{\log_2{N}})$
  14. Don't clear the arrays & data-structures if there is no testcases
  15. Use array of sets instead of defining a set everytime
  16. Use memoization in recursion as much as possible
  17. Convert a recursive DP to an iterative DP
  18. Use break, continue, goto, and return as much as you could
  19. Use Porgan Princible (in 2SUM, you should add to the map while trying to find, not before)
  20. Use small-to-large decomposition (in trees or in DSU)
  21. Optimize memory in DP
  22. In finding shortest route path, put a matrix tells you were you came from, then roll back
  23. When rolling back to find a path, use a while instead of recursion
  24. In binary exponintiation, use while instead of recursion
  25. Write const in constant variables (i.e. MOD), because the compiler calculate it faster
  26. Write/Remove inline in functions that you are using
  27. In segment trees, building is faster than updating every element
  28. Pass parameters by reference if you can
  29. In DSU, use path compression + order by rank (small to large) optimizations, so your code runs in $O(\alpha(N))$
  30. Try different versions of the language (i.e. G++17, G++20, Clang20)
  31. If your code gets TLE on the edge, resubmitting the code may work
  32. If the solution of the problem is one of the subarrays, try to think how to convert it to two-pointers
  33. You may precalculate (hardcode) some values on local device and put them in your submission to optimize it
  34. 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
  35. If non of these above worked, probably your algorithm is bad