ENCYCLOPEDIA
Concepts
Short cards you can reopen mid-problem. Each one names the idea, when it applies, and the usual way it WA's.
Novice
Time complexity
A coarse bound on how the number of primitive operations grows with input size. In contests it is a filter: illegal algorithms are rejected before they are written.
Novice
Space complexity
How much extra memory the solution allocates. Typical limits are 256 MB — a few 2e5 arrays of 64-bit ints are fine; an n×n table at n = 2e5 is not.
Novice
Off-by-one
The most common WA: iterating one index too far, dropping the last element of a reverse, or mixing 0-based code with 1-based statements.
Novice
Contest I/O
Problems specify a rigid input format. In a real contest you parse stdin exactly. In this MVP the arena calls a JavaScript function with parsed arguments instead.
Pupil
Prefix sums
Precompute running totals so any contiguous sum is a subtraction. Works for any invertible combine: +, XOR, occurrence counts.
Pupil
Two pointers
Walk two indices with a monotonic invariant so each element is processed O(1) times. Linear after a possible sort.
Pupil
Sliding window
Two pointers plus a payload (sum, frequencies, deque of maxima). Expand the right end, shrink the left while illegal.
Pupil
Binary search
Halve a monotone search space. Either the array is sorted, or the answer is a number whose feasibility predicate flips once.
Pupil
Hashing
Expected O(1) lookup by value. The usual replacement for an enormous array when keys are up to 1e9, and the usual Two Sum companion.
Specialist
Graph representation
Nodes and edges. Store adjacency lists for sparse graphs; treat grids and 'next state' problems as implicit graphs you never fully materialize.
Specialist
Breadth-first search
Explore layer by layer with a queue. First hit on an unweighted graph is a shortest path. Also the engine of flood fill when you want a wavefront.
Specialist
Depth-first search
Dive along one path with a stack or recursion. Best for connectivity, cycles, topological finishing times, and search trees — not unweighted shortest paths.
Novice
Greedy
Commit to the locally best choice and never revise. Legal only with a proof: exchange argument, matroid, or an obvious stay-ahead.
Expert
Dynamic programming
Solve overlapping subproblems with a named state and a transition. Rank 4 is knapsack/LIS/grids; Rank 9 adds masks, intervals, and digits.
Legendary
Integer overflow
C++ int is 32-bit. Products of two 1e9 values, prefix sums of 2e5 × 1e9, and n(n+1)/2 at n = 1e9 all need 64-bit.
Expert
Knapsack
Choose items under a capacity budget to optimize value (or coin count). 0/1 allows each item once; unbounded allows unlimited copies — the rolling-array loop direction is the switch.
Expert
Longest increasing subsequence
Longest strictly increasing subsequence (order preserved, not necessarily contiguous). O(n²) DP ends at each index; patience/tails with binary search is O(n log n) for the length.
Specialist
Minimum spanning tree
A minimum-total-weight set of n-1 edges that connects an undirected graph. Kruskal sorts and unions; Prim grows a cut. Disconnected input means no MST.
Candidate Master
Monotonic stack
A stack kept increasing or decreasing so each index is pushed and popped once. Answers next-greater / next-smaller in linear time.
Candidate Master
Heap / priority queue
Insert and extract-min (or max) in O(log n). Dijkstra, Prim, Huffman, and 'always merge the two smallest' are the contest uses.
Candidate Master
Fenwick tree
Point add and prefix sum in O(log n) via lowest-set-bit jumps. Range sum is two prefixes. Needs an invertible combine.
Candidate Master
Segment tree
A binary tree over the array. Each node combines its interval. Point update and range query walk O(log n) nodes. Works for min, gcd, and other non-invertible ops.
Master
GCD / LCM
gcd(a,b)=gcd(b,a mod b) in O(log a). Linear combinations are multiples of the gcd. lcm(a,b)=a/gcd*b — divide first.
Master
Sieve of Eratosthenes
Mark composites up to n in O(n log log n). A smallest-prime-factor table then factors any k ≤ n in O(log k).
Master
Modular arithmetic
Reduce after every multiply. Binary exponentiation is O(log e). Inverse of a mod a prime p is a^{p-2}. JS Number cannot hold (1e9+7)².
Master
Binomial coefficients
C(n,k)=n!/(k!(n-k)!). Mod a prime, multiply by inverses. Precompute fact and invFact when n ≤ 1e6 and you have many queries.
International Master
Rolling hash
Prefix polynomial hashes make substring equality O(1). Collisions are a designed-for WA: use two moduli or 2^64 plus a prime.
International Master
KMP prefix function
π[i] is the longest proper border of the prefix s[0..i]. Matching and period checks become linear. Deterministic — no hash collisions.
International Master
Z-algorithm
Z[i] is the LCP of s and s[i..]. A rightmost window [l,r] makes the whole array O(n). Cousin of the prefix function.
Grandmaster
Trees
A connected acyclic graph: n nodes, n-1 edges, unique path. Root it to talk about parents, depth, and subtrees. Diameter is a two-sweep, not n BFS.
Grandmaster
Lowest common ancestor
Deepest common node on two root-paths. Binary lifting answers it in O(log n) after O(n log n) setup. Distance is depth[u]+depth[v]-2·depth[lca].
Grandmaster
Euler tour
DFS timestamps turn a subtree into a contiguous array segment. Then Fenwick/segtree do subtree updates and queries.
Grandmaster
DP on trees
State lives on a subtree, maybe with a flag (matched / not). Reroot with a second DFS when every node must be the root once.
International Grandmaster
Bitmask DP
n ≤ 20: the used set is an integer. 2^n states, often times n. Iterate masks so subsets finish first.
International Grandmaster
Interval DP
dp[l][r] on a contiguous segment. Grow by length, try splits. O(n²) states × O(n) = O(n³); n≤400 in C++.
International Grandmaster
Digit DP
Count numbers ≤ n with a digit property by walking digits. State is (pos, tight, small flags). n=10^18 is 18 steps.
Legendary
Max flow / min cut
Maximum s-t flow equals minimum s-t cut. Augmenting paths on the residual graph find the flow. Matching and 'disconnect t from s' are reductions.
Legendary
Computational geometry
The 2-D cross product is the signed turn. Hulls, intersections, and point-in-polygon all start there. Prefer integer math over atan2.