Algorithm Map

Click a box to see what it solves and when to reach for it. Pick a route to step through what to learn first. Blue labels open the notes.

Algorithm map: what to write in interviews, what to skim, what to master for contests Green = interview core, write it right and fast; grey = skim, know what it solves and when to reach for it; blue = main line of the contest focus, top to bottom; yellow = side branch, picked up when the main line reaches its arrow. Blue labels = notes on this site: A1, B1, ... are the posts of this track; NT = Number Theory, C = Combinatorics, M = Matrix are earlier notes. Prerequisites across lanes are in the box details. Interview core: write it right and fast (HFT / tech interviews, easy contest problems) Skim: what it solves, what it costs, when to reach for it Contest focus: mathematics. Derive the formula and state the idea under contest pressure Number theory Counting Linear algebra (matrices) Complexity · STL Limits pick the bound Know container costs A1 §1 Binary search Boundaries in sorted data Search on the answer A1 §2 Two pointers Both ends only move right O(n) in total A1 §3 Prefix sums O(1) range sum O(1) range add A1 §4 Monotonic stack Next greater element Deque: window max Heap · hash map Top-K, running max Membership and counts Sorting · greedy Sort, then pick locally Prove by exchange Bit tricks lowbit, subset loops XOR identities Search BFS: fewest steps DFS: enumerate + prune Trees Traversal, diameter, LCA Design the return value Shortest paths Dijkstra, topological sort Negative: Bellman-Ford Union-find Online connectivity Kruskal's MST DP: linear, knapsack Define the state first Then transitions, bases DP: tree, bitmask Interval, subtree, set Bitmask: n up to ~20 Strings KMP, hashing, trie 0/1 trie: max XOR Design LRU, order book, limiter Choosing the structure Segment trees Fenwick and segment tree Range ops in O(log n) Balanced BST k-th element, rank Prefer pb_ds in contests Advanced trees HLD, rerooting, centroid Path ops, every root Connectivity Tarjan, condensation 2-SAT: pick-one rules Flows · matching Max flow, min-cost flow Modelling is the hard part Advanced strings Aho-Corasick, SAM Manacher: palindromes Geometry Cross product, hull Half-planes, precision Games Nim, Sprague-Grundy Brute force for a pattern Divide and conquer CDQ, parallel bin. search Offline, drop a dimension Offline tricks Mo's algorithm, sweep Reorder the queries Li Chao · Cartesian Convex hull trick DP Range min as a tree Stress testing Check against brute force Randomised hashing Fast power · gcd · exgcd Where modular work starts NT #1 GCD · CRT Inverses · CRT · Euler Division mod p; merging NT #1 GCD · CRT Sieves Linear sieve, plus φ, μ, d NT #3 sieve → Möbius Multiplicative · Dirichlet How φ, μ, d, σ relate NT #2 multiplicative Möbius · floor blocks The route for sums over gcd NT #2-ex Möbius NT #1.1 floor blocks Du's sieve · Min_25 Prefix sums up to 1e10 NT #4 Min_25 · Du Primitive roots · BSGS Discrete log; NTT moduli C #2.2 roots · NTT Miller-Rabin · rho Primality, factoring to 1e18 NT #4 Miller-Rabin · rho Square roots · Lucas √ mod p; big binomials NT #4 Miller-Rabin · rho Handy facts Legendre's formula; divisors NT #0 common formulae Binomials mod p Precompute factorials C #1.1 binomials C #0 formulae Inclusion-exclusion Trade "at least" for "exactly" C #1.2 inclusion-exclusion Binomial inversion Exactly k ↔ at least k Generating functions OGF: choose; EGF: arrange C #3.1 OGF FFT · NTT Convolution in O(n log n) C #2.1 FFT C #2.2 roots · NTT Polynomial toolkit Inverse, ln, exp, D&C NTT C #3.2 power series Balls into boxes Stirling, Catalan, partitions Pólya · Burnside Counting up to symmetry Probability · expectation Linearity; work backwards FWT · SOS AND / OR / XOR convolutions Matrix fast power Recurrences in O(k³ log n) M #1 fast power · Kitamasa DP semirings (min, +): exactly k steps M #1 fast power · Kitamasa Gaussian elimination Reals, mod p, and XOR M #2 Gaussian elimination Determinants Triangularise; Euclid for any mod Matrix-tree · LGV Spanning trees; disjoint paths BM · Kitamasa Recover the recurrence M #1 fast power · Kitamasa Matrix problems Matrices in segment trees M #4 problems Linear basis Max XOR, k-th XOR M #3 linear basis L2 §1 The map grows with the study: boxes gain links to posts as they are covered.