This is an attempt to write the guide I wished existed when I was starting out: not a collection of algorithm explanations, but a map of how to think. There is no shortage of resources that explain what Dijkstra’s algorithm does. There is a severe shortage of resources that explain how to recognize that Dijkstra’s algorithm is what a problem is asking for. That recognition - the act of looking at a problem and knowing which mental shelf to reach for - is the actual skill. Everything else is just details that can be looked up.

Competitive programming is pattern recognition under time pressure. A problem that seems novel almost never is. Underneath the story, the unusual characters, and the elaborate setup, it is one of about forty archetypal problems wearing a costume. The job is to see through the costume.

Before Anything Else: How to Read a Problem

Most wrong approaches begin with a misread problem. Read it three times with three different questions.

First read: what is the story? Get a rough picture. Do not try to solve anything.

Second read: what exactly am I computing? Strip the story away. The problem is a mathematical function from input to output. What is the input, precisely? What is the output, precisely? What counts as a valid answer? Work through each provided example by hand before reading further. If you cannot reproduce the expected output from the input using only the problem statement, your understanding is incomplete.

Third read: constraints. These are not footnotes. They are the most important part of the problem. Read: $n$, $m$, the range of values, the number of test cases, the time limit, the memory limit. These numbers tell you which algorithm to write before you understand the problem deeply.

A common mistake is jumping to implementation after the first read. The second common mistake is not working through examples manually. If you have not traced through an example by hand, you have not understood the problem.

The Constraint Table: The Algorithm Is Already Written

The time limit tells you how many operations are acceptable. A modern computer executes roughly $10^8$ to $10^9$ simple operations per second. A 2-second time limit allows roughly $2 \times 10^8$ operations. This means: given $n$, you can immediately determine what complexity class the intended solution lives in. This is the single most useful heuristic in competitive programming.

Constraint on $n$ Acceptable complexity What this suggests
$n \leq 10$ $O(n!)$ or $O(2^n \cdot n)$ Brute force all permutations or subsets
$n \leq 20$ $O(2^n)$ or $O(2^{n/2})$ Bitmask DP, or meet in the middle
$n \leq 100$ $O(n^3)$ Floyd-Warshall, 3-loop DP, matrix multiplication
$n \leq 1{,}000$ $O(n^2)$ or $O(n^2 \log n)$ 2D DP, $O(n^2)$ graph algorithms
$n \leq 10^5$ $O(n \log n)$ Sorting, segment tree, BFS/DFS, Dijkstra
$n \leq 10^6$ $O(n)$ or $O(n \log n)$ tight Two pointers, hashing, linear sieve
$n \leq 10^{18}$ $O(\log n)$ or $O(\sqrt{n})$ Binary search, fast exponentiation, trial division

When there are $T$ test cases with per-case work $f(n)$, the total is $T \cdot f(n)$. A constraint of $T \leq 10^5$ test cases and $n \leq 10^5$ per case with an $O(n)$ solution is fine; with an $O(n^2)$ solution it is not.

Memory: 256MB holds roughly 64 million integers or 32 million 64-bit integers. An $n \times n$ 2D array of integers with $n = 10^4$ uses $10^8$ bytes - too large. This catches many DP state designs before you even implement them.

Read the constraints before you think about the solution. The constraints collapse the solution space from infinite to roughly two or three candidates.

Categorizing the Problem

Before reaching for any algorithm, decide what category the problem belongs to. A wrong categorization sends you down the wrong path entirely. Categories are not mutually exclusive - many problems combine two.

Optimization: find the minimum or maximum of something. Suggests greedy, DP, or binary search on the answer.

Counting: how many ways / paths / configurations exist? Suggests DP or combinatorics.

Decision: is it possible? Can it be done? Suggests BFS/DFS for reachability, or DP for feasibility.

Construction: produce a valid answer, not just determine if one exists. Suggests greedy or careful construction.

Graph problem: nodes, edges, paths, connectivity, flow. Suggests graph algorithms directly.

String problem: operations on characters, substrings, patterns. Suggests hashing, KMP, Z-algorithm, Trie.

Geometric: points, lines, distances, areas. Suggests computational geometry.

Mathematical: number theory, combinatorics, algebra. Suggests math-specific techniques.

The category tells you which section of your mental toolkit to open. Once you are in the right section, the specific algorithm usually becomes apparent from the constraints.

The Algorithm Arsenal

What follows is every major technique, with the signal that tells you to use it and the core idea behind it. This is not meant to replace learning each algorithm deeply - it is a map of what exists and when to reach for it.

Greedy

When: you can make a locally optimal choice at each step and prove that local optima compose into a global optimum.

The signal: problems about scheduling, selecting a subset, ordering elements, interval coverage, or any problem where “always take the best available option” seems defensible.

The core idea: process elements in a deliberate order (often sorted), and at each step commit to the locally best choice. The crucial step is proving correctness, usually via an exchange argument: suppose the greedy did not match the optimal solution at some point. Show that you can swap the greedy choice with the optimal choice without making the solution worse - which means the greedy solution is at least as good as optimal.

Classic patterns:

  • Interval scheduling (select maximum non-overlapping intervals): sort by end time, always pick the interval that ends earliest.
  • Fractional knapsack: sort items by value/weight ratio, take the best ratio items first.
  • Activity selection with deadlines: sort by deadline, use a greedy priority queue.
  • Minimum number of coins/platforms/meeting rooms: think about what is “available” at each step.

The trap: greedy works when it works, and produces subtly wrong answers when it doesn’t. If you cannot construct an exchange argument proof, the greedy is likely wrong. Test it on adversarial inputs. The classic failure: 0/1 knapsack (you cannot take fractions, so the fractional greedy fails).

When: you need to find a value in a sorted structure, OR the answer has a monotonic property (if $X$ is achievable, then all values $\leq X$ or $\geq X$ are also achievable).

The signal:

  • “Find the minimum value such that condition $P$ holds” - binary search on the answer.
  • “Maximum of minimums” or “minimum of maximums” - almost always binary search on answer.
  • Sorted array, first/last occurrence of something.
  • Parametric search: you can check whether a given answer is feasible in $O(f(n))$, but computing the answer directly seems hard.

The core idea for binary search on answer: instead of computing the answer directly, ask: “is the answer $\leq m$?” for various $m$. If this question has a monotone structure (once the answer becomes “yes” it stays “yes” as $m$ increases), binary search over $m$ and solve the decision version. The decision version is often dramatically easier than the optimization version.

Example: “find the minimum rope length such that you can cut $k$ ropes of that length from $n$ ropes.” Directly optimizing is hard. But “can I cut $k$ ropes of length $m$?” is trivially answered by $\sum \lfloor r_i / m \rfloor \geq k$. Binary search on $m$.

Complexity: $O(\log(\text{range}) \cdot f(n))$ where $f(n)$ is the check cost.

Implementation: be careful with the boundary. The invariant is: maintain lo and hi such that the answer is always in $[\text{lo}, \text{hi}]$. Update mid = lo + (hi - lo) / 2 to avoid overflow. Know whether you want the first index where condition holds or the last.

Two Pointers and Sliding Window

When: you need to find a subarray or substring with some property, or count pairs that satisfy a constraint, in a sorted or structured array.

The signal:

  • “Find the longest/shortest subarray with sum $\leq k$.”
  • “Count pairs $(i, j)$ with $A[i] + A[j] = S$.”
  • “Minimum window substring.”
  • The constraint involves contiguous subarrays or the array is sorted and you are looking for pairs.

The core idea: instead of testing every pair $(l, r)$ in $O(n^2)$, maintain two pointers $l$ and $r$ and move them based on whether the current window is too large, too small, or just right. The key insight is that as you move one pointer forward, the other never needs to go backward - giving $O(n)$ total moves instead of $O(n^2)$.

Sliding window with a fixed size $k$: maintain a window of size $k$, slide it across, update the aggregate in $O(1)$ per step.

Variable-size sliding window: maintain l and r. Expand r to include the next element. If the window violates the constraint, advance l until it is valid again. If the window is valid, record the result.

Prefix Sums and Difference Arrays

When: you need range sum queries, or you need to apply range updates and then query point values.

The signal:

  • “Sum of elements from index $l$ to $r$” repeatedly.
  • “After applying $m$ range increment operations, what are the final values?”
  • “Count subarrays with sum equal to $k$.”

Prefix sum: precompute $P[i] = A[0] + A[1] + \ldots + A[i-1]$. Then $\text{sum}(l, r) = P[r+1] - P[l]$ in $O(1)$. 2D prefix sums allow $O(1)$ rectangle sum queries after $O(n^2)$ preprocessing.

Difference array: for range updates. If you want to add $v$ to all elements in $[l, r]$: set $D[l] += v$, $D[r+1] -= v$. After all updates, take the prefix sum of $D$ to recover the final array. This turns $m$ range updates + $n$ point queries from $O(mn)$ to $O(m + n)$.

“Count subarrays with sum $= k$": let $P[i]$ be the prefix sum up to index $i$. You want pairs $(j, i)$ with $P[i] - P[j] = k$, i.e., $P[j] = P[i] - k$. Walk left to right, maintain a hashmap of seen prefix sums. For each $i$, query the hashmap for $P[i] - k$. $O(n)$ total.

Hashing

When: you need $O(1)$ frequency counting, duplicate detection, or substring comparison.

The signal:

  • “Count how many times each value appears.”
  • “Find if any two elements are equal.”
  • “Compare two substrings efficiently.”

Rolling hash for strings: assign each character a value, compute the polynomial hash of each prefix. The hash of substring $[l, r]$ is computable in $O(1)$ after $O(n)$ preprocessing. Use two different hash bases and moduli to avoid collisions (birthday paradox: with one modulus around $10^9$, collisions become likely with large inputs).

The trap: hash collisions are rare but nonzero. In competitive programming, a deterministic approach is safer when the judge is adversarial. Use random bases or double hashing.

Graph Algorithms

Graphs are ubiquitous because many problems that appear unrelated to graphs can be modeled as one. The first skill is recognizing the graph. The second is picking the right algorithm.

Modeling as a graph: if the problem has “states” and “transitions” between states, it is a graph. States are nodes; valid transitions are edges. The question “what is the minimum number of moves from state A to state B?” is a shortest path problem. “Is state B reachable from state A?” is a connectivity problem.

BFS (Breadth-First Search):

  • Use when: finding the shortest path in an unweighted graph; any problem where you need minimum number of steps.
  • Core idea: explore nodes level by level. The first time you reach a node, you have found the shortest path to it.
  • 0-1 BFS: when edge weights are either 0 or 1, use a deque. Push weight-0 neighbors to the front, weight-1 neighbors to the back. Runs in $O(V + E)$ instead of Dijkstra’s $O((V+E) \log V)$.
  • Multi-source BFS: if you want the distance from any of a set of source nodes, push all sources into the queue simultaneously at the start.

DFS (Depth-First Search):

  • Use when: detecting cycles, finding connected components, topological ordering, tree traversals, problems where you explore all paths.
  • Core idea: go deep before going wide. DFS on undirected graphs colors nodes white → gray (in stack) → black (done). A back edge (gray → gray) means a cycle.
  • In directed graphs, DFS produces a discovery time and finish time per node, from which topological order and strongly connected components (Kosaraju’s, Tarjan’s) are derived.

Dijkstra’s Algorithm:

  • Use when: shortest paths in a graph with non-negative edge weights.
  • Core idea: greedily expand the closest unvisited node. Maintain a priority queue of (distance, node) pairs. When you pop a node, its distance is final.
  • Complexity: $O((V + E) \log V)$ with a binary heap.
  • The trap: fails with negative edges. The assumption is that the shortest path to a node cannot be improved by going through a later-discovered node - which breaks with negative weights.

Bellman-Ford:

  • Use when: negative edge weights exist; or detecting negative-weight cycles.
  • Core idea: relax all edges $V - 1$ times. After $k$ iterations, you know the shortest paths using at most $k$ edges. If running a $V$-th iteration still relaxes any edge, a negative cycle exists.
  • Complexity: $O(VE)$.

Floyd-Warshall:

  • Use when: all-pairs shortest paths; $V \leq 500$ or so.
  • Core idea: $dp[k][i][j]$ = shortest path from $i$ to $j$ using only nodes ${1, \ldots, k}$ as intermediates. Transition: $dp[k][i][j] = \min(dp[k-1][i][j],; dp[k-1][i][k] + dp[k-1][k][j])$.
  • Complexity: $O(V^3)$.

Topological Sort:

  • Use when: ordering tasks with dependencies; finding longest path in a DAG; any problem on a directed acyclic graph where processing order matters.
  • Core idea: Kahn’s algorithm (repeatedly remove nodes with zero in-degree) or DFS finishing order (nodes finish in reverse topological order).
  • Longest path in a DAG: process nodes in topological order, relax edges. $O(V + E)$.

Minimum Spanning Tree:

  • Kruskal’s: sort edges by weight, add each edge if it doesn’t create a cycle (use Union-Find to detect). $O(E \log E)$.
  • Prim’s: like Dijkstra but on a dense graph; use when $E \approx V^2$. $O(V^2)$ or $O(E \log V)$ with a heap.

Union-Find (Disjoint Set Union)

When: dynamic connectivity queries - “are $u$ and $v$ connected?” after a sequence of “merge $u$ and $v$” operations. Also: Kruskal’s MST, detecting cycles in undirected graphs, grouping elements.

The core idea: maintain a forest of trees where each tree is a connected component. Each node points to its parent. The root is the representative. Two nodes are connected iff they have the same root. Find: walk to root (with path compression: make every visited node point directly to root). Union: attach one root to the other (by rank: attach the smaller tree under the larger).

With path compression and union by rank, find and union are effectively $O(\alpha(n))$ where $\alpha$ is the inverse Ackermann function - essentially constant.

What you cannot do: split (undo a union) in the standard version. Offline rollback with a stack enables “union-find with undo” for some problems.

Dynamic Programming

DP is the hardest technique to learn because it is not a single algorithm but a problem-solving paradigm. The difficulty is not coding it - it is finding the right state.

When: the problem asks for an optimum or a count, and the problem has both:

  1. Optimal substructure: the solution to the full problem can be assembled from solutions to subproblems.
  2. Overlapping subproblems: the same subproblem is solved repeatedly in a naive recursive approach.

The four questions to design a DP:

  1. What is the state? What information do I need to uniquely describe a subproblem? The state must contain everything needed to compute the answer for that subproblem - and nothing more (excess state increases complexity exponentially).

  2. What is the base case? The smallest subproblem whose answer is known without recursion.

  3. What is the transition? How do I compute the answer for state $s$ from smaller states? Express $dp[s]$ as a function of $dp[s']$ for states $s'$ that are “before” $s$ in some ordering.

  4. What is the answer? Which state or combination of states contains the final answer?

The canonical DP patterns:

0/1 Knapsack: $n$ items, each with weight $w_i$ and value $v_i$; capacity $W$. Choose items to maximize value without exceeding capacity. State: $dp[i][j]$ = max value using first $i$ items with remaining capacity $j$. Transition: either skip item $i$ ($dp[i-1][j]$) or take it ($dp[i-1][j - w_i] + v_i$, if $j \geq w_i$). Optimization: 1D array, iterate $j$ from $W$ down to $w_i$.

Unbounded Knapsack: same but you can take each item multiple times. Iterate $j$ upward instead of downward.

Longest Common Subsequence (LCS): given strings $A$ and $B$, find the length of their LCS. State: $dp[i][j]$ = LCS length of $A[1..i]$ and $B[1..j]$. Transition: if $A[i] = B[j]$, then $dp[i][j] = dp[i-1][j-1] + 1$; else $\max(dp[i-1][j], dp[i][j-1])$.

Longest Increasing Subsequence (LIS): $O(n^2)$ DP is straightforward. The $O(n \log n)$ version maintains a “patience sorting” array: for each element, binary search for where it fits, replacing the existing element. The array length at the end is the LIS length. (The array does not contain an actual LIS, just its length.)

Interval DP: problems on a range of elements where the solution for $[l, r]$ depends on solutions for sub-ranges. Classic example: matrix chain multiplication, optimal polygon triangulation, burst balloons. State: $dp[l][r]$ = answer for the subproblem on range $[l, r]$. Transition: try every split point $k$ in $[l, r]$: combine $dp[l][k]$ and $dp[k+1][r]$ somehow. Order: iterate by length (short ranges before long ones).

DP on trees: process subtrees bottom-up. $dp[u][s]$ = something about the subtree rooted at $u$ with state $s$. Classic: find the maximum independent set on a tree. $dp[u][0]$ = max independent set in $u$’s subtree if $u$ is not selected; $dp[u][1]$ = if $u$ is selected (then none of its children can be).

Bitmask DP: when $n \leq 20$ and the state is a subset of elements. State: $dp[\text{mask}]$ = answer for having processed the subset represented by mask. Classic: Travelling Salesman Problem - $dp[\text{mask}][i]$ = minimum cost path visiting exactly the nodes in mask and ending at node $i$.

Digit DP: count numbers in $[L, R]$ satisfying some digit-level property. State: $dp[\text{position}][\text{tight}][\text{other relevant info}]$. tight is a boolean - are we still constrained to be $\leq$ the upper bound digit by digit? Standard pattern: build the number digit by digit from the most significant.

DP with transition optimization: when the naive transition is $O(n)$ and you need $O(\log n)$ or $O(1)$.

  • Monotone queue (deque) optimization: for transitions of the form $dp[i] = \min_{j \leq i - k} (dp[j] + \text{cost})$, if cost is linear in j, maintain a deque of useful states.
  • Divide and conquer DP: when the optimal $j$ for $dp[i]$ is monotonically non-decreasing in $i$.
  • Convex Hull Trick: when the transition looks like $dp[i] = \min_j (A[j] \cdot B[i] + C[j])$ - this is a family of linear functions in $B[i]$, and you want the minimum over all $j$. Maintain a convex hull of the lines; query in $O(\log n)$ or $O(1)$ if $B[i]$ is monotone.

Monotone Stack

When: “next greater element,” “previous smaller element,” “largest rectangle in histogram,” problems where you need to find, for each element, the nearest element to the left/right that is smaller/larger.

The core idea: maintain a stack of elements in monotonically increasing (or decreasing) order. When a new element arrives, pop elements from the stack that violate monotonicity - and as you pop, you have found the “next smaller” (or “next greater”) element for those popped elements.

This is $O(n)$ total because each element is pushed and popped at most once.

Classic problems:

  • Largest rectangle in histogram: for each bar, find the first bar to its left and right that is shorter. The rectangle extending left and right from bar $i$ has width determined by these bounds. Use monotone stack to find these bounds in $O(n)$.
  • Stock span problem.
  • Next greater element in a circular array.
  • Sum of subarray minimums (classic application with contribution technique).

Segment Trees and Fenwick Trees

When: you need to answer range queries (sum, min, max) and handle point or range updates, both efficiently.

Fenwick Tree (Binary Indexed Tree):

  • Supports: point update, prefix sum query.
  • Complexity: $O(\log n)$ per update and query.
  • Why it exists: simpler and smaller constant than a segment tree for prefix sum queries. The “responsible range” of each index is derived from its lowest set bit.
  • Extend to range updates + point queries by using a difference array under the hood.
  • Extend to range updates + range queries using two Fenwick trees (requires careful derivation).

Segment Tree:

  • Supports: any associative operation on ranges, with point or range updates.
  • Complexity: $O(\log n)$ per update and query.
  • Lazy propagation: for range updates, instead of updating every element in a range (which would be $O(n)$ per update), mark the node as “pending update” and push the lazy tag down only when you need to go deeper. Makes range updates $O(\log n)$.
  • When to use a segment tree over a Fenwick tree: when you need range updates, or when the operation is not a prefix sum (e.g., range minimum with updates).

Sparse Table:

  • Supports: range minimum/maximum queries in $O(1)$ after $O(n \log n)$ preprocessing.
  • Works only for idempotent operations (min, max, gcd) - you cannot use it for sum.
  • Suitable when there are no updates - the structure is static.

String Algorithms

KMP (Knuth-Morris-Pratt):

  • Use when: finding all occurrences of pattern $P$ in text $T$ in $O(|T| + |P|)$.
  • Core idea: precompute the “failure function” for $P$ - for each position $i$, the length of the longest proper prefix of $P[0..i]$ that is also a suffix. This lets you skip redundant comparisons when a mismatch occurs.
  • Also useful for: finding the period of a string, building the Z-array.

Z-algorithm:

  • Computes $Z[i]$ = length of the longest substring starting at position $i$ that matches a prefix of the string. $O(n)$.
  • Pattern matching: concatenate pattern + # + text. Positions in the text portion where $Z[i] = |P|$ are match positions.

Trie:

  • Use when: prefix queries, autocomplete, XOR maximization (with binary trie), multi-pattern matching.
  • A Trie stores strings as paths from root to leaf. Each node has up to 26 (or 2, for binary) children.
  • XOR maximization: build a binary trie of all numbers. For a query number $q$, greedily try to go down the opposite bit at each level - this maximizes XOR.

Rolling Hash:

  • Polynomial hash: $H(s) = \sum s[i] \cdot p^i \mod m$.
  • After preprocessing, compare any two substrings in $O(1)$.
  • Use when: checking if a substring matches a pattern, or in problems involving many substring comparisons.

Bit Manipulation

When: the problem involves subsets (bitmask DP), has small $n$ and you want to represent sets as integers, or arithmetic tricks are useful.

The essential operations:

  • Check if bit $k$ is set: (x >> k) & 1
  • Set bit $k$: x | (1 << k)
  • Clear bit $k$: x & ~(1 << k)
  • Lowest set bit: x & (-x) (two’s complement trick)
  • Count set bits: __builtin_popcount(x) in GCC
  • Enumerate all subsets of a mask: for (int sub = mask; sub > 0; sub = (sub - 1) & mask)

Sum over Subsets (SOS DP): compute for every mask $m$, the sum of $f[\text{sub}]$ over all submasks sub of $m$. Naive: $O(3^n)$ (each element is in the mask, in the submask, or absent). SOS DP reduces this to $O(n \cdot 2^n)$:

for (int i = 0; i < n; i++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask >> i & 1)
            dp[mask] += dp[mask ^ (1 << i)];

Divide and Conquer

When: the problem can be split into independent subproblems of the same form, solved recursively, and combined.

The signal: “closest pair of points,” “count inversions,” “maximum subarray sum” (Kadane’s is linear, but the divide-and-conquer version makes the pattern visible).

Key insight: the difficult part is usually the “combine” step - counting or optimizing contributions that cross the dividing boundary.

Counting inversions: split array in half, count inversions entirely in the left, entirely in the right, and crossing the midpoint. Crossing inversions are counted in $O(n)$ during the merge step of merge sort. Total $O(n \log n)$.

Mathematical Techniques

Modular arithmetic: almost every counting problem on Codeforces says “output the answer modulo $10^9 + 7$.” This is because the actual answer is astronomically large. Key operations: $(a + b) \mod m$, $(a \cdot b) \mod m$, $(a - b + m) \mod m$. Division modulo a prime $p$: use Fermat’s little theorem: $a^{-1} \equiv a^{p-2} \pmod{p}$, computed via fast exponentiation.

Fast exponentiation: compute $a^b \mod m$ in $O(\log b)$ by repeated squaring. Represent $b$ in binary: $a^b = a^{b_0} \cdot (a^2)^{b_1} \cdot (a^4)^{b_2} \cdots$. Multiply only the powers where the corresponding bit is 1.

Combinatorics: precompute factorials and inverse factorials mod $p$ to compute $\binom{n}{k} \mod p$ in $O(1)$ per query. Pascal’s identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ for small $n$.

Sieve of Eratosthenes: find all primes up to $N$ in $O(N \log \log N)$. Linear sieve: $O(N)$. Use the sieve to precompute smallest prime factors for $O(\log n)$ factorization.

GCD / LCM: $\gcd(a, b) = \gcd(b, a \mod b)$ (Euclidean algorithm). $\text{lcm}(a, b) = ab / \gcd(a, b)$. Compute gcd in $O(\log \min(a, b))$.

Matrix exponentiation: if a recurrence can be written as a matrix multiplication, $F(n) = M \cdot F(n-1)$, then $F(n) = M^n \cdot F(0)$, computable in $O(k^3 \log n)$ where $k$ is the matrix dimension. Use for Fibonacci-like recurrences where $n \leq 10^{18}$.

Inclusion-Exclusion: count elements satisfying at least one of several properties. $|A_1 \cup A_2 \cup \ldots| = \sum |A_i| - \sum |A_i \cap A_j| + \ldots$. Useful when direct counting is hard but counting intersections of constraints is manageable.

The “Whenever I See X, Think Y” Recognition Map

This is the most immediately practical section. It is a map built from patterns, not from derivations.

What I see in the problem What I reach for first
“Minimum of maximum” or “maximum of minimum” Binary search on the answer
“Can you do it in $k$ operations?” as a decision Binary search on $k$ if monotone
“Count subarrays with sum $= k$” Prefix sums + hashmap
“Number of subarrays with property $P$” Two pointers if $P$ is monotone; else prefix sum
“Shortest path, no weights” BFS
“Shortest path, positive weights” Dijkstra
“Shortest path, negative weights” Bellman-Ford
“Shortest path, all pairs, $n \leq 500$” Floyd-Warshall
“Is this graph connected?” or “same component?” Union-Find or DFS
“Minimum cost to connect all nodes” MST (Kruskal or Prim)
“Order tasks with dependencies” Topological sort
“Longest path in a DAG” Topological sort + DP
“Next greater / smaller element” Monotone stack
“Largest rectangle in histogram” Monotone stack
“Sliding window maximum” Monotone deque
“Range sum query + point update” Fenwick tree
“Range min/max query, no updates” Sparse table
“Range query + range update” Segment tree with lazy propagation
“Number of ways to do X” DP or combinatorics
“Select $k$ items to maximize / minimize” 0/1 Knapsack DP
“Subset with property, $n \leq 20$” Bitmask DP
“Longest increasing subsequence” Patience sort, $O(n \log n)$
“String matching: is $P$ in $T$?” KMP or Z-algorithm
“Compare substrings in $O(1)$” Polynomial hashing
“Prefix queries on strings” Trie
“XOR maximize / minimize over a set” Binary Trie
“Pattern matching, multiple patterns” Aho-Corasick
“Numbers with digit constraints, count in range” Digit DP
“Recurrence, $n \leq 10^{18}$” Matrix exponentiation
“Count with overlapping bad cases” Inclusion-exclusion
“All primes up to $N$” Sieve of Eratosthenes
“Interval scheduling, non-overlapping” Sort by end time, greedy
“Assign jobs to minimize max load” Binary search on load + greedy check
“Make array non-decreasing with min operations” DP or greedy depending on operations
“Graph problem that seems like search” Model states as nodes, transitions as edges, BFS/DFS
“Permutation / arrangement, $n \leq 8$” Bitmask DP
“Two arrays, find something about pairs” Sort one, binary search in the other
“Queries offline” Sort queries by some parameter (Mo’s algorithm, offline BFS)
“Multiple test cases, shared structure” Precompute; build offline; or preprocess in $O(n \log n)$ once

The Step-by-Step Protocol When You Are Stuck

This is what to do when you have read the problem and have no idea where to start - or when your first idea is not working.

Step 1 - Solve a tiny version. If $n \leq 100$ in the real problem, what if $n = 3$? Solve it by hand. Enumerate all possible answers. Understand the structure of the solution for a small case before worrying about efficiency.

Step 2 - Identify what changes between cases. In your small-case solutions, what information do you need to carry from one step to the next? This is the DP state, or the invariant maintained by a greedy, or the graph structure.

Step 3 - Think about what order to process elements. Many problems become solvable when elements are processed in the right order: sorted by value, sorted by deadline, in BFS level order, in topological order. Ask: “if I knew the right order, what would I do?”

Step 4 - Think about what to ignore. Many hard-seeming problems have a property that lets you eliminate candidates. “The optimal answer always uses the largest element” is one example. If you can argue that some subset of options is never optimal, you have simplified the problem.

Step 5 - Reformulate. Restate the problem in terms of a graph, or in terms of an array operation, or as a linear program. Sometimes the right reformulation immediately reveals the algorithm. “Finding the maximum number of non-overlapping intervals” sounds like a combinatorial problem until you realize it is exactly the interval scheduling problem with a known greedy solution.

Step 6 - Think about the complement. Instead of “count things that satisfy $P$”, try “total things minus things that don’t satisfy $P$.” Instead of “can I reach $t$?”, try “which nodes cannot reach $t$?” Duality and complementation unlock many problems.

Step 7 - Try the simplest algorithm that could possibly work. If the constraint allows $O(n^2)$ and you have an $O(n^2)$ idea that is correct, implement it. Do not prematurely optimize. The time penalty for submitting a correct $O(n^2)$ solution that times out is smaller than the time penalty for getting the wrong answer with an incorrectly-optimized solution.

Step 8 - If correct but slow, think about what is redundant. Which part of your $O(n^2)$ or $O(n^3)$ solution is doing repeated work? Can that repeated work be precomputed, stored in a data structure, or eliminated with a smarter ordering?

Dynamic Programming: The Harder Path Through the Design

DP deserves its own section because the recognition problem is harder than for any other technique. There is no single “DP signal” - it is the answer when greedy fails, when brute force is too slow, and when the problem asks for an optimum or count with a recursive structure.

The state is everything. The most common mistake is a state that is either too small (doesn’t capture necessary information, leading to wrong transitions) or too large (exponential state space). Ask: given this state, can I compute the answer uniquely? If not, the state is incomplete. Can I remove any component of the state and still compute correctly? If yes, the state is too large.

Think about what changes. In a DP, you are building up an answer incrementally. At each step, something changes: you include one more element, you move to the next position, you use one more unit of some resource. The state tracks everything that matters about what you have processed so far, and the transition encodes what happens at this step.

DP versus greedy. A greedy always knows the right local choice. A DP does not - it tries all choices and keeps the best. If you cannot prove that a local choice is always safe, try DP. The DP will subsume the greedy: if there is a greedy solution, the DP will also find it.

Proving correctness of a DP. The DP is correct if the optimal solution to the full problem can always be assembled from optimal solutions to subproblems. This is optimal substructure. Verify it: suppose the full optimal solution uses a particular solution to a subproblem. Can you replace that subproblem solution with a worse one and still get the full optimal? If yes, the subproblem solution must also be optimal - optimal substructure holds.

Memoization versus tabulation. Memoization (top-down): write the recursive function, cache results. Tabulation (bottom-up): fill a table in the right order. Both compute the same thing. Use memoization when: the dependency structure is complex or sparse (you do not need all subproblems). Use tabulation when: the dependency structure is clear and dense, or when stack overflow is a concern (deep recursion with $n = 10^6$ will overflow).

Debugging

A solution that produces wrong answers is not a failed attempt - it is an experiment. Debugging is diagnosis.

Wrong Answer (WA):

  • Re-read the problem statement. Is the output format exactly right? (Off-by-one on indexing, missing newline, extra space.)
  • Check edge cases: $n = 1$, all elements equal, all elements distinct, the minimum possible value, the maximum possible value, an empty set.
  • If the problem involves modular arithmetic, check that you never have negative values before taking modulo (use ((x % mod) + mod) % mod).
  • Check for integer overflow. If values can reach $10^9$ and you multiply two of them, the product is $10^{18}$, which overflows a 32-bit integer. Use 64-bit integers throughout.
  • Generate random small inputs and compare your output with a brute-force solution. This is called a stress test and catches bugs that adversarial examples miss.

Time Limit Exceeded (TLE):

  • Count your operations exactly. Is your solution actually within the complexity bound?
  • Are there hidden $O(n)$ operations inside a loop? (e.g., string concatenation inside a loop is $O(n^2)$; vector membership test inside a loop is $O(n)$ per test.)
  • Are you repeatedly recomputing something you could precompute?
  • Is there a faster algorithm? Check whether the constraints suggest a lower complexity bound.
  • Consider constant factor optimizations only after ruling out algorithmic improvements: use arrays instead of maps where possible; avoid unnecessary memory allocation inside loops.

Memory Limit Exceeded (MLE):

  • Calculate the memory your data structures use. An $n \times n$ integer array with $n = 10^4$ uses $4 \times 10^8$ bytes - 400MB.
  • Can you reduce DP table dimensions? Many 2D DPs only depend on the previous row and can be reduced to 1D.
  • Are you storing the entire path when you only need the path length?

Runtime Error (RE):

  • Array out of bounds: the most common cause. Check your index bounds, especially in DP tables where you access dp[i-1] without verifying $i > 0$.
  • Stack overflow: recursion too deep for large $n$. Convert to iterative.
  • Integer division by zero.
  • Accessing a null or uninitialized pointer.

The Framework in Action: One Problem Per Level

Words about a framework are cheap. The test is whether it actually collapses the solution space in practice. What follows is one representative problem from each Codeforces difficulty tier, walked through exactly the way the framework prescribes - from reading constraints to arriving at the implementation, with no hindsight.

Level A (~800) - Watermelon (CF 4A)

The problem: Given an integer $n$ (the weight of a watermelon), decide whether it can be split into two parts that are both even and both positive. Print YES or NO.

Read the constraints: $1 \leq n \leq 100$.

$n \leq 100$ means $O(n)$ or even $O(n^2)$ is fine - but this is a decision problem with no structure to iterate over. This should be $O(1)$.

Categorize: decision problem. “Is it possible?”

Think: two even positive integers sum to what? An even number that is at least $2 + 2 = 4$. So the answer is YES iff $n$ is even AND $n \geq 4$.

Is $n = 2$ impossible? Yes: the only split is $0 + 2$, but $0$ is not positive. Is $n = 4$ possible? $2 + 2$, yes.

Answer: n % 2 == 0 && n >= 4.

What the framework did: constraints ($n \leq 100$, decision problem) immediately told us the answer is $O(1)$ math. Categorizing as “decision” pointed at checking a condition rather than optimizing one. The “tiny case” analysis (what are the possible even splits?) took 30 seconds.

Level B (~1300) - Taxi (CF 158B)

The problem: $n$ groups of people want taxis. Each group has size $s_i \in {1, 2, 3, 4}$. A taxi holds exactly 4 people. Groups cannot be split across taxis. Find the minimum number of taxis.

Read the constraints: $1 \leq n \leq 10^5$, $1 \leq s_i \leq 4$.

$n \leq 10^5$ and $s_i \leq 4$ - very small value range. Count the frequency of each size. This should be $O(n)$.

Categorize: optimization (minimize number of taxis). The small domain of $s_i$ suggests we can handle each size class independently. This is greedy territory.

Think: groups of 4 fill a taxi exactly - they go alone. Groups of 3 go alone but leave one empty seat. The best thing to put in that seat is a group of 1. Groups of 2 pair together perfectly (two groups of 2 per taxi). Groups of 1 fill remaining space.

Work through the logic: let $c_1, c_2, c_3, c_4$ be the counts.

  • $c_4$ taxis used for groups of 4.
  • $c_3$ taxis used for groups of 3; each has one leftover seat, so we can fit $\min(c_1, c_3)$ groups of 1 in them. Remaining ones: $c_1' = c_1 - \min(c_1, c_3)$.
  • Groups of 2: pairs fill a taxi. $\lfloor c_2 / 2 \rfloor$ taxis. If $c_2$ is odd, one taxi has two empty seats which can fit up to two groups of 1. Remaining ones: $c_1'' = \max(0,; c_1' - 2 \cdot (c_2 % 2))$.
  • Remaining groups of 1: $\lceil c_1'' / 4 \rceil$ taxis.

Total = $c_4 + c_3 + \lfloor c_2 / 2 \rfloor + (c_2 % 2) + \lceil c_1'' / 4 \rceil$.

What the framework did: “minimize with tiny value domain” → greedy by matching. The thought “groups of 3 have one leftover seat; best fill it with size 1” is the exchange argument in one sentence. No code was written until the logic was complete.

Level C (~1700) - Counting Subarrays (prefix sums pattern)

The problem: given an array of $n$ integers and a target sum $k$, count the number of contiguous subarrays whose sum equals exactly $k$. (CF 560E / Leetcode 560 - this exact pattern appears at C level on Codeforces repeatedly.)

Read the constraints: $n \leq 10^5$, values can be negative or zero, $k$ can be any integer.

$n \leq 10^5$ → $O(n \log n)$ or $O(n)$. Brute force ($O(n^2)$) is marginal at best and likely TLE.

Categorize: counting. “How many subarrays…”

Look at the recognition table: “Count subarrays with sum $= k$” → prefix sums + hashmap. This is a direct match.

Think through it: the sum of subarray $[l, r]$ equals $P[r+1] - P[l]$ where $P$ is the prefix sum array. We want $P[r+1] - P[l] = k$, i.e., $P[l] = P[r+1] - k$. For each position $r$, how many previous positions $l$ had prefix sum equal to $P[r+1] - k$? Maintain a hashmap of prefix sum frequencies as you scan left to right. Initialize with ${0: 1}$ (the empty prefix).

count = 0, prefix = 0, freq = {0: 1}
for each element x:
    prefix += x
    count += freq[prefix - k]
    freq[prefix] += 1
return count

$O(n)$ time, $O(n)$ space.

What the framework did: constraints → $O(n)$ needed. Category → counting. Pattern table → prefix sums + hashmap as a direct lookup. Implementation followed immediately from the pattern.

Level D (~2100) - Constructing the Array (CF 1353D)

The problem: you have an array of $n$ zeros. At each step, find the subarray with the maximum length; if there are ties, pick the one with the smaller left index. Split it in half (left half if odd length). After $n - 1$ steps, read the values in the array. (Paraphrased from CF 1353D; the actual problem asks you to simulate this efficiently.)

Read the constraints: $n \leq 2 \times 10^5$ and up to $n - 1$ steps → brute force simulation is $O(n^2)$. Need $O(n \log n)$.

Categorize: simulation/construction. The question is: how do we efficiently maintain the “largest subarray” across many splits?

Think: each “subarray” is defined by its left and right endpoints. After a split, one subarray becomes two. The operation is: repeatedly extract the maximum subarray, split it, insert two new ones. This is a priority queue problem.

What goes in the priority queue? Each subarray, with a key that reflects the tiebreaking rule: first maximize length, then minimize left endpoint. A pair (-length, left) as the priority key achieves this with a min-heap (negate length to simulate max-heap behavior on length).

Each step: pop the max subarray $(l, r)$. If length 1, this position gets assigned the current fill value. Otherwise split: left half is $[l, \text{mid}]$, right half is $[\text{mid}+1, r]$ where $\text{mid} = (l + r - 1) / 2$ (left-biased midpoint). Push both back into the heap.

$n - 1$ steps, each $O(\log n)$: total $O(n \log n)$.

What the framework did: $n \leq 2 \times 10^5$ → $O(n \log n)$. “Extract maximum repeatedly” is the smell of a heap. Tiebreaking by a second criterion → encode both criteria in the heap key. The implementation is mechanical once the data structure is identified.

Level E (~2500) - Sereja and Suffixes (CF 380E) adjacent max pattern

The problem: given an array of $n$ integers, answer $m$ queries each of the form: among elements $a[l..r]$, how many distinct values appear that are the maximum of some contiguous subarray? (This pattern, associating queries with a structural property computed offline, is archetypal at E level.)

Read the constraints: $n, m \leq 10^5$.

$O((n + m) \log n)$ is the target.

Categorize: range query. But it is not a standard range query - the property (being a subarray maximum) is global, not per-element.

Key observation: which values are subarray maxima? An element $a[i]$ is the maximum of some subarray iff it is a local maximum or an endpoint, which (with some thought) simplifies to: $a[i]$ is a subarray maximum iff there is no adjacent element larger than it that “dominates” it from both sides. More precisely: keep only elements that are greater than all elements to their left up to the previous greater element. This is the set of elements that survive after removing those completely dominated - equivalently, build the sequence of “right-to-left maxima” and “left-to-right maxima.”

In practice the key insight is: precompute, for each index $i$, whether it is a “prefix maximum” from the right (i.e., $a[i] > a[j]$ for all $j > i$ up to the next larger element). The set of elements that can be subarray maxima is exactly the set that appears in the monotone stack during a left-to-right scan.

Now the query becomes: in range $[l, r]$, how many elements from the monotone-stack survivor set exist? This is a static range counting query on a precomputed set - answered with a sorted list + binary search in $O(\log n)$ per query.

What the framework did: $n, m \leq 10^5$ → $O(n \log n + m \log n)$. “Range query with precomputed structure” → offline precomputation + binary search. The key step is reducing “which elements are subarray maxima?” to a monotone stack computation, which is the E-level insight the constraints force you toward.

Level F (~3000) - Sum of XOR over All Pairs (contribution technique)

The problem: given an array of $n$ integers, compute the sum of $a[i] \oplus a[j]$ over all pairs $i < j$. $n \leq 3 \times 10^5$, values up to $10^{18}$.

Read the constraints: $n \leq 3 \times 10^5$, $O(n^2)$ is $9 \times 10^{10}$ - completely infeasible. Need $O(n \log(\max a))$.

Categorize: sum over all pairs. Bit operations.

Key insight at F level: XOR operates independently on each bit. For each bit position $b$, compute its contribution to the total sum separately. The contribution of bit $b$ is $2^b \times$ (number of pairs where bit $b$ of $a[i] \oplus a[j]$ is 1). Bit $b$ is 1 in $a[i] \oplus a[j]$ iff exactly one of $a[i], a[j]$ has bit $b$ set.

So for each bit $b$: let $z$ = count of numbers with bit $b$ = 0, and $o$ = count with bit $b$ = 1. The number of pairs where this bit is 1 in the XOR is $z \times o$. The contribution is $2^b \times z \times o$.

Sum over all bits: $\sum_{b=0}^{60} 2^b \times z_b \times o_b$.

$O(n \times 60) = O(n \log(\max a))$.

What the framework did: $n \leq 3 \times 10^5$ → $O(n \log n)$ or $O(n \log V)$. “XOR sum over pairs” → bit independence is the unlock. The “contribution technique” - computing each bit’s contribution independently - is the F-level insight that turns an infeasible $O(n^2)$ problem into a linear scan. The actual implementation is five lines once the observation is made.

The pattern of patterns: at every level, the framework does the same thing. Constraints collapse the complexity class. Category (decision/optimization/counting/construction) points at a family of tools. A specific signal in the problem points at a specific tool. The F-level insight is not that different from the A-level insight - both are observations about structure. The difference is that the F-level observation is harder to see, the encoding is subtler, and the implementation has more pieces. The framework works at every level. The reps are what scale it.

Reading Other People’s Solutions

After you have solved a problem (or given up), reading the editorial and high-rated participants' solutions is where you actually improve. But read them differently:

Read the editorial’s claim about the algorithm before reading the proof. Then try to reconstruct the proof yourself. Then read the actual proof. The act of attempting the reconstruction is the learning - not the reading.

Read high-rated participants' code for style and implementation patterns. The code for a segment tree written by a red-rated programmer will be shorter, cleaner, and contain patterns you can reuse. Copy the structure, understand each line, and make it yours.

Build a personal template library. Segment tree, Union-Find, Dijkstra, KMP, modular arithmetic utilities - these should be code you can write from memory or paste from a tested template. The goal is to never spend contest time debugging a segment tree implementation. Debug it once, put it in your template, and never debug it again.

On Building the Intuition Over Time

The patterns above are not things you memorize - they are things you absorb, problem by problem, until the recognition becomes automatic. Every competitive programmer who is good at pattern recognition got there the same way: by solving many problems, getting stuck, looking at the solution, understanding why that approach works, and then noticing it again next time.

The transition from “I know what a segment tree is” to “that problem needs a segment tree and I know it immediately” is not a matter of reviewing segment trees more carefully. It is a matter of having seen the segment tree applied in enough contexts that the smell of the problem triggers the recognition. There is no shortcut here. The cheat sheet above accelerates the early phase - it tells you what to look for before you have enough reps to see it automatically. But the reps themselves cannot be replaced.

Solve problems slightly above your comfort level. Struggling on a problem for an hour and then reading the editorial teaches you more than solving ten problems you already know how to solve. The discomfort is the point. The moment of “oh, I should have seen that” is the moment a pattern is acquired.

Keep a log of problems you got wrong and why. Pattern of wrong answers: misread the problem. Pattern of TLE: wrong complexity. Pattern of WA after getting the right idea: off-by-one, overflow. Your error patterns are personal and tell you where your practice should focus.

The ceiling is not fixed. The patterns are learnable. The recognition is trainable. The intuition accumulates.

This is a living document. I will keep adding patterns as I encounter them.