Algorithm design · Free problems
Reason about a guarantee. Then try to break it.
Work from counterexamples to code, with an adversary testing your rule and an editorial explaining the proof.
The Tutoring Rota
Pair tutors with students at the least total travel time, then prove no rota is shorter with potentials from the dual linear program. Write an assignment solver whose answers are checked by their certificate, not by re-solving.
assignment problem · LP duality · Hungarian method · complementary slackness · certificateseasy → medium → hard → researchThe Turnstile Counter
A binary counter costs 2 bit flips per increment on average, until it also has to count down. Find the sequence that makes it expensive, then design a counter whose increments and decrements both cost O(1) amortized writes.
amortized analysis · potential method · binary counter · redundant number systemseasy → medium → hard → researchThe Coat Check
Pile every coat on one hook by choosing ticket numbers, find the exact collision chance of the Carter-Wegman family, then write a hash family that an adversary who reads your code still cannot beat.
hashing · universal hashing · collisions · adversaries · hash floodingeasy → medium → hard → researchThe Pipeline Detours
How many augmentations can Ford-Fulkerson take? Count them on the classic four-junction network, design a small network that forces a bad rule into hundreds, then compute a maximum flow and prove it with a minimum cut.
network flow · Ford-Fulkerson · Edmonds-Karp · max-flow min-cut · certificateseasy → medium → hard → researchThe Product Audit
Check a claimed matrix product with a random vector instead of multiplying again. Work out how often the check misses, see why the vector's range matters more than repeating, and write an audit that catches errors built to fool shortcuts.
Freivalds' algorithm · randomized algorithms · Schwartz-Zippel lemma · polynomial identity testing · matrix multiplicationeasy → medium → hard → researchThe Radio Masts
Cover every village with the fewest radio masts. Find where greedy builds twice as many as needed, then write a weighted greedy that returns a lower bound proving it is within H(k) of the best.
set cover · greedy algorithms · approximation algorithms · dual fitting · LP dualityeasy → medium → hard → researchThe Ledger of Ranges
Add to a whole range of accounts and total any range, thousands of times. Count how many tree nodes a range needs, then write lazy propagation on a segment tree whose every field read is counted.
segment tree · lazy propagation · range update · range query · data structureseasy → medium → hard → researchThe Pivot from Group Medians
Build the inputs that push the median-of-medians pivot as far off-centre as it can go, count exactly how far, and find which group sizes still give a linear-time selection algorithm.
selection · median of medians · recurrences · worst-case inputseasy → medium → hard → researchThe Lightest and the Heaviest
Find the lightest and heaviest of n parcels with a balance scale in as few weighings as possible, then write the adversary that proves no method can do better.
lower bounds · adversary arguments · comparisons · minimum and maximumeasy → medium → hardThe Night Bus Contracts
Schedule night buses that must meet route minimums, respect road limits and cost as little as possible. Price a small network, prove another impossible with a crowded set of stops, then write a solver whose answers carry their own proof.
minimum-cost flow · circulations · lower bounds · potentials · certificateseasy → medium → hard → researchThe Shelf of Binders
A shelf of binders, a cost for every binder you reach past, and a rule for reordering after each request. Break Transpose, measure move-to-front against its cruellest sequence, and write a rule that stays within twice the best fixed order.
online algorithms · list update · move-to-front · competitive analysis · amortized analysiseasy → medium → hard → researchThe Lab Partners
Pair lab students when a pair may share a bench for part of the term. Find where triangles beat every real pairing, pin down a fractional vertex, cut it off with odd-set constraints, then compute a fractional matching that carries its own proof.
matching · linear programming · integrality · odd-set constraints · LP duality · vertex covereasy → medium → hard → researchThe Dictionary Shelf
Given how often each key is looked up, build the binary search tree with the fewest total comparisons. See why putting the most popular key at the root fails, then write the dynamic program and return the tree itself.
dynamic programming · optimal binary search tree · interval DP · Knuth's optimizationeasy → medium → hard → researchMatching Fingerprints
Make polynomial fingerprints collide: for one base, for as many random bases as possible, and for every odd base at once when the arithmetic wraps around mod 2^64.
hashing · Rabin-Karp · string matching · polynomials · anti-hash tests · Thue-Morseeasy → medium → hardThe Committee's Wishes
Meet as many weighted yes-or-no wishes as possible. Price fair coins, build the instance where the LP overpromises, then round any fractional solution so that it expects at least 3/4 of the LP, and prove why.
approximation algorithms · randomized rounding · MAX-SAT · linear programming · integrality gapeasy → medium → hard → researchThe Forecast and the Lighting Rig
Rent or buy with a forecast that may be wrong. Break the rule that trusts it, find the price of trust, and write a rule that an adversary grades for consistency, robustness and graceful degradation.
online algorithms · competitive analysis · learning-augmented algorithms · ski rental · lower boundseasy → medium → hardThe Fibre Run
Join a few sites with fibre under the cheapest streets, using any junction on the way. Beat the shortest-path heuristic by hand, build a town where it does badly, then write the dynamic program over sets of sites that is exponential only in their number.
dynamic programming · Steiner tree · subset DP · parameterized algorithms · approximationeasy → medium → hard → researchThe Merging Clubs
Build the tallest trees that naive linking and union by size allow, then write a union-find that stays within a few cell reads and writes per operation on sequences built to break the simpler versions.
union-find · disjoint sets · union by rank · path compression · amortized analysiseasy → medium → hard → researchThe Weather Panel
Forecast rain from a panel of forecasters with no knowledge of the weather. See why any fixed rule can be forced into twice the best forecaster's mistakes, then write a randomized forecaster within 2 sqrt(T ln n) of the best.
multiplicative weights · weighted majority · Hedge · online learning · regreteasy → medium → hardThe Night Guard
A thief picks a room to rob and a guard a room to watch. Find the value of a two-room game by hand, the guard's best mix for three rooms, then solve any zero-sum game with strategies that prove the value from both sides.
game theory · zero-sum games · minimax theorem · linear programming · LP duality · mixed strategies