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

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 you 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

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

• Pseudocode:

  # Source: https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure
  
  function binary_search(A, n, T) is # A: array, n: length, T: target
   L := 0
   R := n − 1
   while L ≤ R do
       m := floor((L + R) / 2)
       if A[m] < T then
           L := m + 1
       else if A[m] > T then
           R := m − 1
       else:
           return m
   return unsuccessful
  
  

Depth-first search

• Description: this is an algorithm which traverses a graph by searching into all reachable nodes, while keeping track of visited ones.

• Problems: this is used in problems where you need to traverse a graph.

• Time complexity: O(n)

• Example problem: Closing the farm

• Code:

  // c++
  // Source: Competitive programmer's handbook, Chapter 12
  vector adj[N];
  bool visited[N];
  
  void dfs(int s) {
    if (visited[s]) return;
    visited[s] = true;
    // process node s
    for (auto u: adj[s]) {
      dfs(u);
    }
  }
  

Breadth-first search

• Description: this is an algorithm which traverses a graph by searching into all nodes in increasing order of their distance from the starting node.

• Problems: this is used in problems where you traverse a graph while keeping track of the distance between nodes.

• Time complexity: O(n)

• Code:

  // c++
  // Source: Competitive programmer's handbook, Chapter 12
  queue q;
  bool visited[N];
  int distance[N];
  
  visited[x] = true;
  distance[x] = 0;
  q.push(x);
  while (!q.empty()) {
    int s = q.front(); q.pop();
    // process node s
    for (auto u : adj[s]) {
      if (visited[u]) continue;
      visited[u] = true;
      distance[u] = distance[s]+1;
      q.push(u);
    }
  }
  

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(n * log n) time.
• Example problem: Sum of two values
• Note: in C++ there is a set and an unordered_set.

Graphs

• Problems: this is used in problems where you need to be able to connect nodes in a cycle.
• Note: this can be represented in many ways, such as, adjacency list representation, adjacency matrix representation, edge list representation...

Trees

• Problems: this is used in problems where you need to be able to connect some parent node with child nodes.

Miscellaneous

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

Fast I/O

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

• Note: this only works with C++.

• Code:

  // c++
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  

Integer overflow

• Description: some problems require using a long long type instead of an int. If you experience some kind of int overflow, try with a long long.

Sources

• Wikipedia for some descriptions
• CSES, Codeforces, USACO for the problems
• Usaco Guide for the problem selection and some explanations

Improvements?

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