Competitive programming cheatsheet

This is a cheat sheet made for when you are stuck on a problem and can't find the optimal solution. This will refresh your memory and hopefully help you find the concept/approach you should be using for your problem.

This is not made to teach your any of these concepts/approaches, it's only made to help you quickly identify which one you should be using for each problem.

If you'd like to start in Competitive Programming, I'd recommend reading the Competitive Programmer's Handbook by Antti Laaksonen. Most, if not all of the things mentioned here are explained in detail in this book.

If you aren't familiar with one of these concepts/approaches I'd recommend you learn it at Usaco Guide. That is also the source for most of the example problems.

Note: time complexity and space complexity are very dependent on the input data and therefore the ones written here are purely an estimation of what they usually are in common problems.

Approaches/Concepts

Complete search

• Problems: this is used in problems where you need to check every possible solution and pick out the one your need.
• Time complexity: O(n²) || O(n³) Depending on input dimensions
• Example problem: Cow Gymnastics

Sorting

• Problems: this is used in problems where sorting will make it easier to compare/find something.
• Time complexity: O(n * log n)
• Example problem: Kayaking

Greedy algorithms

• Description: greedy algorithms are those which always make the locally optimal choice at each stage of the problem.
• Problems: this is used in problems where you can always make the right decision with your current information.
• Time complexity: O(n)
• Example problem: Coin Problem

Binary search

• Problems: this is usually not enough to solve an entire problem, but it helps finding items in a sorted array.
• Time complexity: O(log n) If the array is sorted, else O(n * log n)
• Example problem: Social Distancing

Prefix sum

• Description: a prefix sum is usually an array, where all the values are changed, with, the sum of all the previous values and the value you are changing.
• Problems: this is used in problems where calculating a prefix/cumulative sum beforehand, avoids computation afterwards.
• Time complexity: O(n)
• Example problem: Subsequences summing to 7

Dynamic programming

• Problems: this is used in problems which you can divide in sub-problems.
• Time complexity: O(2^n)
• Example problem: Coin combinations

Sliding window

• Problems: this is used in problems where want to compute a local value for each (constant length) sub-array in the original array.
• Time complexity: O(n * log n) If the window is very large O(n²)
• Example problem: Subarray Distinct Values

If none from these approaches will do it for your problem, maybe using the right data type will. Usually these data types will have to be mixed with one of the approaches seen above.

Data types

Maps

• Problems: this is used in problems where you need to associate 2 values, and read them in O(1) time.
• Example problem: Team Tic Tac Toe
• Note: in C++ there is a map and an unordered_map.

Sets

• Problems: this is used in problems where: you need to be able to check if a value exist, you need to get unique values in O(n) (standard way with array is O(log n)) time.
• Example problem: Sum of two values
• Note: in C++ there is a set and an unordered_set.

Miscelaneous

Sometimes you're using the right approach but things still don't work. I that case you may try with these small fixes/optimizations.

Fast I/O

• Description: Adding these two lines will spead up the reading/writing of your program.

• Note: this only works with C++.

• Code:

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

Sources

• Wikipedia for some descriptions
• CSES, Codeforces, USACO for the problems
• Usaco Guide for th

Improvements?

If you feel like something is missing or you'd like to improve it, PR's are appreciated.