🐬 Classic Problems

Famous problems collected in one place, each with the idea that solves it and the note that treats it. Puzzles get full write-ups in 25. Puzzles; algorithms by name are in 🐬 Named Algorithms.

Problem	Key idea	Note
Egg dropping ($k$ eggs, $n$ floors)	DP on (eggs, moves): floors covered $={\sum }_{i\le k}\left(\genfrac{}{}{0ex}{}{m}{i}\right)$	Classic DP
0/1, unbounded, bounded knapsack	DP over capacity; monotone deque for bounded	Knapsack
Coin change (count / minimum)	unbounded knapsack; greedy fails in general	Knapsack
Longest increasing subsequence	patience sorting $O(n\log n)$	Sequence DP
Longest common subsequence, edit distance	DP, Hirschberg, bit-parallel	Sequence DP
Matrix chain, optimal BST, stone merging	interval DP, Knuth, Garsia–Wachs	Interval DP
Travelling salesman, Hamiltonian path	Held–Karp bitmask DP	Hamiltonian Paths and TSP
Domino / tromino tilings	profile DP, transfer matrix	Profile DP
Counting numbers with digit constraints	digit DP	Digit DP
Maximum subarray, max circular subarray	Kadane	Classic Array Problems
Trapping rain water, largest rectangle in histogram	two pointers, monotonic stack	Monotonic Stack
Sliding window maximum	monotonic deque	Two Pointers
Majority element, Dutch national flag	Boyer–Moore voting, 3-way partition	Classic Array Problems
Activity selection, interval scheduling	earliest finish first	Interval Problems
Job sequencing with deadlines, Johnson’s rule	exchange arguments	Scheduling
Huffman coding	merge the two smallest	Greedy
Josephus problem	recurrence; $k=2$ by bit rotation	Classic Puzzles
Tower of Hanoi	recursion, $2^n-1$ moves	Tower of Hanoi
Water jugs	BFS on states; gcd condition	Water Jug
Wolf, goat, cabbage; missionaries and cannibals	BFS on a small state space	Wolf, Goat, Cabbage
Bridge and torch	greedy over two strategies	Bridge and Torch
100 prisoners	follow the permutation cycles	100 Prisoners
Monty Hall	conditional probability, switch	Monty Hall
Secretary problem	reject the first $n/e$	Secretary Problem
Poisoned wine	binary encoding of testers	Poisoned Wine
Celebrity problem	$O(n)$ elimination	Celebrity Problem
Two envelopes paradox	no proper prior gives $\frac{1}{2}$ for every amount; Cover’s random threshold	Two Envelopes
Boy or girl, Bertrand’s box, three prisoners	Bayes with the protocol that produced the information	Boy or Girl
St. Petersburg paradox	infinite expectation; capped bank, log utility	St. Petersburg Paradox
Buffon’s needle	integral over position and angle; $\frac{2\ell }{\pi d}$	Buffon’s Needle
Blue-eyed islanders, muddy children	induction on the count; common knowledge	Blue-Eyed Islanders
Rope burning, hourglasses	search over event times; gcd invariant	Rope Burning
Chomp, Hex	strategy stealing; Hex has no draws	Chomp and Hex
Mutilated chessboard, strip tilings	colouring arguments; profile DP counts	Mutilated Chessboard
15 puzzle (optimal solving)	parity solvability; IDA* with Manhattan + linear conflicts	Fifteen Puzzle
Rubik’s cube group order	Schreier–Sims on sticker permutations	Rubik’s Cube
Peg solitaire	rule-of-three invariant; memoized search	Peg Solitaire
Sudoku	bitmask backtracking with MRV; exact cover	Sudoku
Magic squares	Siamese, doubly even, LUX	Magic Squares
Euler’s 36 officers	orthogonal Latin squares; none of order 6	Latin Squares
Kirkman’s schoolgirls	resolvable Steiner triple systems	Kirkman’s Schoolgirls
Fair cake cutting	cut and choose, Even–Paz, Selfridge–Conway	Cake Cutting
Wheat and chessboard	$2^{64}-1$; overflow	Wheat and Chessboard
Ant on a rubber rope	covered fraction; harmonic series diverges	Ant on a Rubber Rope
Zebra puzzle (Einstein’s riddle)	permutation CSP with backtracking	Zebra Puzzle
Knights and knaves, three gods	boolean formulas; embedded question lemma	Knights and Knaves
Bulgarian solitaire	energy on diagonals; rotation and CRT	Bulgarian Solitaire
Gold chain payment	complete sequences; $(k+1)2^{k+1}-1$	Gold Chain
Instant Insanity	two edge-disjoint 2-regular subgraphs	Instant Insanity
Jeep problem (desert crossing)	fuel flux bound; harmonic depots	Jeep Problem
Icosian game	Hamiltonian cycles, bitmask DP	Icosian Game
Pigeonhole classics (socks, handshakes, divisible block)	choose the boxes	Pigeonhole Puzzles
Fitch Cheney five-card trick	pigeonhole on suits; permutation encodes $\mathrm{1..6}$	Fitch Cheney Trick
N-queens, Sudoku, knight’s tour	backtracking, exact cover, Warnsdorff	Backtracking
8 / 15 puzzle	A*, parity invariant	Informed Search
Subset sum, partition, 4-sum	meet in the middle, bitset DP	Meet in the Middle
Nim, Wythoff, Bash game, staircase nim	Sprague–Grundy, golden ratio	Combinatorial Games
Coupon collector, birthday paradox	linearity, $\sqrt{n}$ threshold	Probability
Gambler’s ruin, pattern waiting time (ABRACADABRA)	martingales, optional stopping	Probability
Stable marriage, stable roommates	Gale–Shapley, Irving	Stable Matching
Assignment problem	Hungarian	Assignment Problem
Project selection, densest subgraph	min cut, closure	Flow Modeling
Chinese postman	odd vertices + min-weight matching	Euler Tours
Königsberg bridges, de Bruijn sequences	Euler paths	Euler Tours
Graph colouring, chromatic number	inclusion–exclusion $O(2^{n}n)$	Graph Colouring
Closest pair of points	divide and conquer / sweep	Closest Pair
Smallest enclosing circle	Welzl	Minimum Enclosing Circle
Art gallery, polygon area, point in polygon	shoelace, ray casting	Polygons
Range minimum / sum queries	sparse table, Fenwick, segment tree	8. Range Queries
Count inversions	merge sort or Fenwick	Sorting
Trailing zeros of $n!$, divisors of $n!$	Legendre	Factorials mod p
Frobenius coin problem (McNugget)	$ab-a-b$	Congruences and CRT
Derangements, ménage problem	inclusion–exclusion	Inclusion-Exclusion
Necklaces and bracelets	Burnside	Burnside and Pólya
Ballot problem, Dyck paths	reflection principle	Catalan and Lattice Paths
Fibonacci $n$-th term for huge $n$	matrix power, fast doubling	Matrix Exponentiation DP
Longest palindromic substring	Manacher	Palindromes
Number of distinct substrings	suffix array / automaton	Suffix Automaton
Word break	$d{p}_i$ from valid breaks of a dictionary-matched prefix	Classic DP
Running median, median maintenance	two heaps balanced in size	Heaps
Skyline / building silhouette	sweep line with a multiset of active heights	Sweep Line
Gas station (circular tour)	greedy restart after the tank goes negative	Gas Station
Cryptarithmetic (SEND + MORE = MONEY)	backtracking over digit assignments, pruned by partial column sums	Backtracking