Algorithms & data structures, by division
USACO problems are designed around a known set of techniques. Each division adds a small layer on top of the previous one. This page lists what to learn for each division, in roughly the order you'll meet it.
🥉 Bronze
Bronze problems read like wordy puzzles. They're solvable with loops, arrays, and careful case analysis. The win condition is reading carefully and handling edge cases, not algorithmic cleverness.
Complete search (brute force)
Try every possibility. When n ≤ 20 you can iterate over all 2ⁿ subsets; when n ≤ 8 you can try all n! permutations with next_permutation.
Drill: any "find the best assignment of k items" with k ≤ 20.
Simulation
Carefully model the rules of a process step by step. The bug is almost always in your understanding of the rule, not your code.
Drill: grid simulation, turn-based game state transitions.
Ad-hoc / case analysis
Break the problem into 3–5 cases and handle each. Write the cases on paper before you touch the keyboard.
Drill: "minimum operations to" type problems with small constraints.
Sorting + greedy
Sort by some key, then walk left-to-right making locally optimal choices. Prove the greedy works before submitting.
Drill: interval scheduling, "minimize sum of pairs".
Prefix sums (1D)
Precompute cumulative sums so range queries become O(1). Bronze rarely requires them, but they often turn an O(n²) brute force into an AC.
Drill: "sum of subarray with property X".
Basic recursion
Recursion with memoization is your bridge into Silver DP. Get comfortable with the call stack model before you need it.
Drill: count paths in a grid, recursive subset enumeration.
🥈 Silver
Silver is where "algorithms" actually start. Constraints rise to ~10⁵, so O(n²) brute forces TLE. You need at least one O(n log n) idea per problem.
Graph traversal: BFS & DFS
Connected components, flood fill, shortest path on unweighted graphs, cycle detection. Both iterative (stack/queue) and recursive forms.
Pitfall: recursive DFS can stack-overflow at n=10⁵ — bump the stack size with a thread or convert to iterative.
Flood fill on grids
Special case of BFS/DFS on 2-D grids. Almost every Silver round has one.
Drill: count islands, find largest region, "rotting oranges".
Binary search on the answer
When the answer is monotonic ("does a value ≥ X work?"), binary-search over X. Reduces an unknown to a feasibility check.
Drill: "minimum maximum X such that ...", "aggressive cows" classic.
Two pointers & sliding window
Maintain a window [l,r] that grows/shrinks as you scan. Works when expanding r monotonically lets l only move forward.
Drill: longest subarray with property; "subarrays with sum ≤ k".
Prefix sums (1D & 2D)
Sum / count over arbitrary ranges in O(1) after O(n) prep. 2-D version uses inclusion–exclusion.
Drill: "max sum rectangle ≤ k", "number of subarrays summing to s".
Sorting + ad-hoc
Sort by a clever key (start time, ratio, custom comparator), then do something linear. Most Silver greedy problems are this.
Drill: earliest-deadline-first, fractional knapsack.
Stacks & queues for monotonicity
Monotonic stack/deque solves "next greater element", "max in sliding window".
Drill: largest rectangle in histogram, sliding window maximum.
Set / map & multiset
std::set for ordered insertion + lower_bound queries; std::map for keyed counting; multiset for dynamic median / kth element tricks.
Drill: dynamic kth smallest, "how many ≤ x as I scan".
🥇 Gold
Gold is real competitive programming. Problems need a non-trivial idea and a clean implementation. This is the largest jump in difficulty in the whole season.
Dynamic programming
1-D, 2-D, DP on intervals, DP on trees, bitmask DP for n≤20. The bottleneck topic at Gold.
Mental model: define the state precisely first; transitions write themselves once the state is right.
Dijkstra & shortest paths
Dijkstra with priority queue for non-negative weights; Bellman-Ford for negative; 0-1 BFS for weights in {0,1}.
Drill: "shortest path with one edge halved", multi-source Dijkstra.
Union-Find (DSU)
Disjoint-set with path compression + union by rank/size. Used for MST (Kruskal), offline connectivity, "rollback" tricks.
Drill: Kruskal's MST, "Mr. President" style.
Topological sort & DAG DP
Kahn's algorithm or DFS-based. Lots of Gold DP problems are "DP on a DAG" in disguise.
Drill: longest path in DAG, "scheduling with prerequisites".
Segment / Fenwick trees
Point update + range sum/min/max in O(log n). Fenwick (BIT) for sums, segment tree for everything else. Lazy propagation when ranges are updated too.
Drill: range sum with point updates, inversions count.
Binary lifting / LCA
Precompute 2^k-th ancestor for trees. Lowest Common Ancestor in O(log n), kth ancestor queries.
Drill: LCA, "jump pointer" problems on trees.
Number theory & modular arithmetic
GCD, sieve of Eratosthenes, modular exponentiation, modular inverse via Fermat. Combinatorics modulo prime.
Drill: "count paths mod 10⁹+7", "nCk mod p".
String algorithms
KMP / Z-function for pattern matching, polynomial hashing for substring equality in O(1) after O(n) prep.
Drill: longest repeated substring, periodic strings.
💎 Platinum
Platinum is research-grade competitive programming. Each problem typically requires one clever observation combined with a heavy data structure or DP optimization. You will spend full sessions on a single problem here.
Heavy data structures
Lazy segment tree, segment tree beats, persistent segment tree, link-cut trees, wavelet trees, merge-sort tree.
Tree decomposition
Centroid decomposition (divide-and-conquer on trees), heavy-light decomposition (path queries via segtree).
Network flow
Max-flow / min-cut via Dinic's algorithm; min-cost max-flow; bipartite matching (Hopcroft-Karp).
DP optimizations
Convex Hull Trick (for "min/max c·x + d"), Divide-and-Conquer optimization, Knuth optimization, SOS DP.
Advanced graph
Strongly connected components (Tarjan/Kosaraju), 2-SAT, biconnected components, articulation points/bridges.
Suffix structures
Suffix array + LCP via Kasai; suffix automaton; Aho-Corasick for multi-pattern matching.
Math & geometry
Combinatorics with inclusion–exclusion, Burnside, Möbius; FFT for polynomial multiplication; computational geometry (convex hull, half-plane intersection).
Sqrt decomposition & Mo's algorithm
Block decomposition for range queries; Mo's for offline queries reordered by sqrt-bucket.
A complexity cheat sheet
| n up to | What can fit in 2 seconds |
|---|---|
| 10 | O(n!) ≈ 3.6M — permutations are fine |
| 20 | O(2ⁿ) ≈ 10⁶ — bitmask DP, subset enumeration |
| 100 | O(n³) ≈ 10⁶ — Floyd-Warshall, n³ DP |
| 2 000 | O(n²) ≈ 4·10⁶ — pairwise DP |
| 10⁵ | O(n log n) ≈ 10⁷ — sorting, segment tree, Dijkstra |
| 10⁶ | O(n) or O(n log log n) — linear scan, sieve |
| 10⁹ | O(log n) or O(√n) — math closed-form, binary search, sieve trick |
USACO judges allow ~2 seconds for C++. Aim for under 10⁸ simple operations to be safe.