Competitive Programming

Before any algorithm: the complexity budget, fast I/O, and the language toolkit that decides a third of your rating.

• lessonThe 10⁸ rule: read constraints, pick the complexity that fitsplanned
• lessonFast I/O and the contest template (C++ & Python)planned
• lessonThe standard library is half the battle: what to reach forplanned

Binary search is not about sorted arrays — it is about monotone predicates. Two pointers and sliding windows turn O(n²) scans into O(n).

• readingReading — Binary Search15mmark done
• lessonBinary search on the answer: the single highest-yield trickplanned
• lessonTwo pointers & sliding window: the O(n) sweepplanned
• readingPractice — Three Sum (two-pointer on a sorted array)20mmark done
• readingPractice — Longest substring without repeating (window)20mmark done

BFS, DFS, and Dijkstra cover most contest graph problems. The skill is modeling: seeing the grid, the state machine, the implicit graph.

• readingReading — Breadth-First Search15mmark done
• readingReading — Depth-First Search15mmark done
• readingReading — Dijkstra's algorithm20mmark done
• readingReading — Topological Sort15mmark done
• lesson0-1 BFS and multi-source BFS: Dijkstra’s cheaper cousinsplanned
• lessonModeling: when the graph is hiding in the problemplanned

The single biggest rating divider. State design first, transitions second — then the classic shapes: knapsack, LIS, edit distance, and DP on structure.

• readingReading — Knapsack20mmark done
• readingReading — Longest Increasing Subsequence20mmark done
• readingReading — Edit Distance20mmark done
• lessonDesigning the state: the part nobody teaches8m·
• lessonBitmask DP: subsets as integers7m·
• lessonDP on trees: rerooting and subtree aggregates7m·
• lessonDigit DP: counting numbers with a property7m·

Greedy is easy to code and hard to trust. The skill is the proof — the exchange argument that tells you it is safe, and the counterexample when it is not.

• readingReading — Coin Change (where greedy fails, DP saves it)20mmark done
• lessonExchange arguments: proving a greedy choice is safeplanned
• lessonInterval scheduling, Huffman, and the greedy canonplanned

GCD, sieves, modular arithmetic, and counting under a prime modulus — the math half of competitive programming.

• readingReading — The Euclidean Algorithm15mmark done
• readingReading — Sieve of Eratosthenes15mmark done
• readingReading — Modular Exponentiation15mmark done
• lessonModular inverse and nCr mod p: counting under 10⁹+7planned
• lessonInclusion-exclusion: counting by overcounting on purposeplanned
• lessonCRT and linear Diophantine equationsplanned

Pattern matching in linear time, then hashing and the Z-function — the tools that make string problems tractable.

• readingReading — KMP (Knuth-Morris-Pratt)20mmark done
• readingReading — Rabin-Karp (rolling hash)20mmark done
• readingReading — Trie15mmark done
• lessonThe Z-function and prefix-function tricksplanned
• lessonString hashing: comparison in O(1), with the collision mathplanned
• lessonSuffix arrays in outline: when hashing is not enoughplanned

Answer "what is the sum/min over [l, r]?" faster than scanning — the family that separates blue from purple: prefix sums, sparse tables, Fenwick, segment trees.

• lessonPrefix sums & difference arrays: the O(1) range query6m·
• lessonSparse tables: idempotent queries in O(1)6m·
• lessonFenwick trees (BIT): the 12-line workhorse7m·
• lessonSegment trees: point update, range query8m·
• lessonLazy propagation: range update, range query8m·

Minimum spanning trees, all-pairs paths, connectivity decomposition, and ancestor queries — the heavier graph machinery.

• readingReading — Kruskal's MST20mmark done
• readingReading — Prim's MST15mmark done
• readingReading — Floyd-Warshall15mmark done
• readingReading — Bellman-Ford (negative edges)20mmark done
• lessonStrongly connected components: Tarjan & Kosarajuplanned
• lessonBridges & articulation pointsplanned
• lessonLCA by binary lifting: ancestor queries in O(log n)planned
• lessonMax flow / min cut: the modeling power and the intro algorithmplanned

The purple-and-up toolbox: linear recurrences by matrix power, convolution by FFT, game theory, and a first taste of geometry.

• lessonMatrix exponentiation: nth Fibonacci in O(log n)planned
• lessonFFT/NTT in outline: multiply polynomials in n log nplanned
• lessonGame theory: Sprague-Grundy and the nim-valueplanned
• lessonComputational geometry primer: orientation, hull, sweepplanned

The meta-skill: reading a set, estimating difficulty, stress-testing a suspect solution, allocating time — and the deliberate path up the rating ladder.

• lessonReading a problem set: difficulty estimation and order of attack6m·
• lessonStress testing: catch the WA before the judge does7m·
• lessonTime allocation and the psychology of a live contest5m·
• lessonThe rating ladder: a deliberate-practice plan for CodeChef & Codeforces7m·