Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 63 ยท Practice and Review

Competitive Programming Cheat Sheet

A one-page competitive programming cheat sheet: complexity limits by input size, Python templates, modular math formulas, graph and DP patterns, and debugging checklist.

This page is a reference you can keep open during practice. It does not teach anything new; it collects the numbers, templates and formulas from the whole track in one place, so that you can check a complexity limit or copy a snippet in seconds. Every item links to the lesson that explains it.

Two of the snippets below are runnable so you can confirm they behave as claimed. Everything else is a read-only block meant to be copied into your own template.

Complexity limits

The table assumes roughly one second and a compiled language doing about 10^8 simple operations. For Python, divide the budget by 10 to 50 and prefer built-ins that run in C.

Largest input n Target complexity Typical techniques
up to 10 O(n!) permutations, brute force
up to 20 O(2^n), O(n ยท 2^n) subsets, bitmask DP, meet in the middle
up to 100 O(n^4) small DP, Floyd-Warshall (n^3)
up to 500 O(n^3) Floyd-Warshall, interval DP
up to 5,000 O(n^2) 2D DP, all pairs
up to 10^5 to 2 ยท 10^5 O(n log n) sorting, heaps, binary search, segment tree
up to 10^6 O(n) or O(n log n) with a small constant sieve, prefix sums, two pointers
up to 10^7 O(n) linear sieve, single pass
up to 10^18 O(log n) or O(1) fast power, binary search, formulas

See Estimating Time and Memory and Reading a Problem Statement.

flowchart LR
    A["Read n"] --> B{"n <= 20?"}
    B -->|yes| C["bitmask or brute force"]
    B -->|no| D{"n <= 5000?"}
    D -->|yes| E["O(n^2) DP or pairs"]
    D -->|no| F{"n <= 10^6?"}
    F -->|yes| G["O(n log n): sort, heap, tree"]
    F -->|no| H["O(n) or O(log n) math"]

A quick path from the largest input size to a family of algorithms.

Python template

Python
import sys
from sys import stdin

def main():
    data = stdin.buffer.read().split()          # read everything once
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    out = []
    # ... solve, append strings to out ...
    sys.stdout.write("\n".join(out) + "\n")      # print once

main()                                           # locals are faster than globals

Deep recursion needs sys.setrecursionlimit(10**6) plus an explicit stack for depth beyond a few thousand; prefer iterative DFS. More habits are in Templates and Habits and Python for Contests.

Standard formulas

Topic Formula or rule
Sum 1..n n(n+1)/2
Sum of squares 1..n n(n+1)(2n+1)/6
Arithmetic series count * (first + last) / 2
gcd, lcm gcd(a, b), a // gcd(a, b) * b
Modular inverse (prime p) pow(a, -1, p) or pow(a, p-2, p)
Binomial n! / (k! (n-k)!), Pascal: C(n,k) = C(n-1,k-1) + C(n-1,k)
Stars and bars non-negative solutions of x1+...+xk = n: C(n+k-1, k-1)
Catalan C(2n, n) / (n+1)
Inclusion-exclusion `
Euler totient phi(n) = n * product(1 - 1/p) over prime factors
Number of divisors product(e_i + 1) over prime powers p_i^e_i
Expected value E[X + Y] = E[X] + E[Y] always
Bit tricks x & -x lowest set bit; x & (x-1) clear it; x ^ x = 0
Subset enumeration s = (s - 1) & mask loops over submasks

Details: Modular Arithmetic, Counting and Combinatorics, Number Theory Toolkit, Probability and Expected Value and Bit Tricks and XOR Problems.

Under a modulus, never use // for division and always reduce after every multiplication. In languages with fixed-width integers, multiply two residues in a 64-bit type.

Common patterns

Statement says Think
"minimize the maximum" / "maximize the minimum" binary search on the answer
"count subarrays with property" prefix sums plus hashing, or two pointers
"k-th smallest", "median of stream" heap, sorted structure, binary search
"next greater/smaller" monotonic stack
"range sum with updates" Fenwick tree
"range min/max, static" sparse table; with updates, segment tree
"connected components, merge groups" union-find
"shortest path, unit weights" BFS (0-1 BFS for weights 0/1)
"shortest path, weights >= 0" Dijkstra
"number of ways modulo 998244353" DP or combinatorics with factorials
"choose subset, n <= 20" bitmask
"optimal, locally best" greedy plus proof or brute-force check
"two players, perfect play" win/lose DP or Sprague-Grundy
"compare substrings" hashing, Z-function, prefix function

See Binary Search on Answer for Contests, Two Pointers and Sliding Windows in Practice, Monotonic Stacks, Heaps and Deques in Contests, Fenwick and Segment Trees for Contests, Shortest Paths in Practice and DP Speedups.

Snippets worth memorizing

Fast power and Dijkstra with heapq:

Python
import heapq

def dijkstra(adj, src):
    dist = [float("inf")] * len(adj)
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                    # stale entry (lazy deletion)
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Four-direction grid moves and a Fenwick tree:

Python
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)
    def add(self, i, delta):            # 1-based index
        while i < len(self.t):
            self.t[i] += delta
            i += i & -i
    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s
Python Check the memorized snippets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Debugging checklist

  1. Re-read the statement: constraints, indexing (0 or 1 based), output format.
  2. Run the samples, then n = 1, all equal, sorted, reversed, maximum size.
  3. Write a brute force and compare on random small inputs with a fixed seed.
  4. Check overflow, negative % and //, float comparisons and the recursion limit.
  5. Measure the worst case you can build, not just the samples.

More in Verdicts and Debugging, Stress Testing with a Brute Force and Edge Cases and Common Pitfalls.

Python Numbers every contest programmer should feel

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 3 questions

of 3 answered You scored / 3 ยท perfect!

  1. 1. n is at most 10^6 and the time limit is 1 second. Which complexity is safest?

    10^6 squared is 10^12 operations, far too many. Linear or n log n fits.
  2. 2. Which expression clears the lowest set bit of x?

    x & (x - 1) removes the lowest set bit. x & -x isolates it instead.
  3. 3. A statement asks to minimize the largest value. What is the first technique to consider?

    Minimizing a maximum is a classic monotone feasibility question, so binary search on the answer fits.

Summary

  • Map n to a complexity first: 20 means subsets, 5000 means nยฒ, 10^5 means n log n, 10^18 means math.
  • Keep a short template: read all input at once, write the output once, use local functions.
  • Learn the formulas for sums, binomials, inverses, totient and bit tricks, and always reduce under a modulus.
  • Match statement phrases to techniques with the pattern table before you write any code.
  • Debug in a fixed order: statement, samples, edge cases, brute force, limits.

Ready to plan your practice? Continue with Training Plans and Virtual Contests.