Dense notes for competitive programming, from the first contest to ICPC World Finals: every topic with tested C++ code, the ideas that make it work, and a collapsed proof for each claim. Code assumes the template in 馃惉 Templates (ll, sz, all).
Start here
- General: C++ for CP, fast I/O and constant factor, complexity, debugging, interactive problems, contest and ICPC team strategy, implementation
- 馃惉 Named Algorithms: every named algorithm and where it lives
- 馃惉 Classic Problems: famous problems and the idea behind each
- 馃惉 Complexity Cheat Sheet: time and space of everything
- 馃惉 Formula 路 馃惉 Abbreviations 路 馃惉 Resources 路 馃惉 References 路 馃惉 About 路 馃惉 Rules
- 馃惉 Paradigms 路 馃惉 Techniques 路 馃惉 Algorithms 路 馃惉 Data Structures
Chapters
1. Problem Solving
i. Attacking a Problem 路 ii. Invariants, Parity and Extremal Arguments 路 iii. Contribution and Complementary Counting 路 iv. Proof Techniques 路 v. Constructive Algorithms 路 vi. Classic Puzzles 路 vii. Observation Toolkit 路 viii. When the Answer Is Small 路 ix. Sorting and Ordering Observations 路 x. Parity, Coloring and Mod Observations 路 xi. Operations and Reachable States 路 xii. Ad Hoc on Arrays and Strings 路 xiii. Ad Hoc Problem Set 路 xiv. Permutation Constructions 路 xv. Graph Constructions 路 xvi. Grid and Matrix Constructions 路 xvii. Sequence and Number Constructions 路 xviii. Invariant-Based Constructions 路 xix. Greedy Constructions 路 xx. Interactive and Output-Only Constructions 路 xxi. Problem Reduction and Modeling
2. Searching and Sorting
i. Binary Search 路 ii. Ternary and Golden-Section Search 路 iii. Sorting, Selection and Inversions
3. Array Techniques
i. Prefix Sums and Difference Arrays 路 ii. Two Pointers and Sliding Window 路 iii. Monotonic Stack 路 iv. Classic Array Problems 路 v. Subarray Aggregates and Mex
4. Greedy
i. Greedy and Exchange Arguments 路 ii. Matroids 路 iii. Interval Problems 路 iv. Scheduling and Partitioning
5. Divide and Conquer and Offline
i. Divide and Conquer 路 ii. CDQ Divide and Conquer 路 iii. Offline Techniques 路 iv. Parallel Binary Search
6. Bit Manipulation
i. Bit Tricks and XOR 路 ii. Gray Code 路 iii. Submasks, Supermasks and SOS DP 路 iv. Bitwise Convolutions 路 v. XOR Basis 路 vi. Bitset 路 vii. Bitset and Word-Level Parallelism
7. Data Structures
i. Containers, Hashing and Choosing a Structure 路 ii. Ordered Set and PBDS 路 iii. Heaps 路 iv. Disjoint Set Union 路 v. Treaps and Balanced BSTs 路 vi. Chtholly Tree (Interval Map) 路 vii. Binary Trie 路 viii. Fast Set and Integer Structures 路 ix. KD-Tree and Spatial Structures 路 x. Persistent Data Structures 路 xi. Data Structure Catalog
8. Range Queries
i. Sparse Table 路 ii. Range Minimum Query 路 iii. Fenwick Tree 路 iv. Segment Tree 路 v. Lazy Propagation 路 vi. Dynamic and Persistent Segment Trees 路 vii. Segment Tree Beats and Historic Values 路 viii. Li Chao and Kinetic Segment Trees 路 ix. Segment Tree Merging and Splitting 路 x. Range Order Statistics and Wavelets 路 xi. Sqrt Decomposition 路 xii. Mo鈥檚 Algorithm 路 xiii. Offline and 2D Range Queries 路 xiv. Permutation Tree 路 xv. Range LIS
9. Dynamic Programming
i. DP Foundations 路 ii. Knapsack and Subset Sum 路 iii. Classic DP Problems 路 iv. LIS, LCS and Edit Distance 路 v. Interval DP 路 vi. Bitmask DP 路 vii. Broken Profile DP 路 viii. Digit DP 路 ix. Tree DP and Rerooting 路 x. Dynamic DP 路 xi. DAG and Expected-Value DP 路 xii. Counting DP Techniques 路 xiii. Matrix Exponentiation DP 路 xiv. Convex Hull Trick 路 xv. Divide and Conquer Optimization 路 xvi. Knuth-Yao Optimization 路 xvii. Monotone Queue, 1D1D and SMAWK 路 xviii. Aliens Trick 路 xix. Slope Trick
10. Graphs
i. Graph Basics and Modeling 路 ii. BFS, DFS and Grids 路 iii. Cycles and Functional Graphs 路 iv. Bipartite Graphs 路 v. DAGs and Topological Sort 路 vi. Shortest Paths 路 vii. Shortest Path Techniques 路 viii. K Shortest and Disjoint Paths 路 ix. SCC and 2-SAT 路 x. Bridges and Biconnectivity 路 xi. Dominator Tree 路 xii. Dynamic Connectivity 路 xiii. Minimum Spanning Trees 路 xiv. Directed MST 路 xv. Matrix-Tree Theorem 路 xvi. Euler Tours 路 xvii. Hamiltonian Paths and TSP 路 xviii. Special Graph Classes 路 xix. Graph Coloring
11. Flows and Matching
i. Maximum Flow 路 ii. Push-Relabel 路 iii. Flow Modeling 路 iv. Minimum Cut 路 v. Global Minimum Cut 路 vi. Gomory-Hu Tree 路 vii. Min-Cost Flow 路 viii. Assignment Problem 路 ix. Bipartite Matching 路 x. General Matching 路 xi. Weighted General Matching 路 xii. Matroid Intersection 路 xiii. Stable Matching
12. Trees
i. Tree Basics, Diameter and Center 路 ii. Tree Isomorphism and Pr眉fer Codes 路 iii. Lowest Common Ancestor 路 iv. Euler Tour, Subtree and Path Queries 路 v. Heavy-Light and Long-Path Decomposition 路 vi. Centroid Decomposition 路 vii. Small to Large (DSU on Tree) 路 viii. Virtual Tree 路 ix. Kruskal Reconstruction Tree 路 x. Link-Cut Tree 路 xi. Euler Tour Tree 路 xii. Top Trees
13. Mathematics
i. Modular Arithmetic 路 ii. Barrett and Montgomery Reduction 路 iii. Probability and Expectation 路 iv. Contest Mathematics
14. Number Theory
i. GCD and Extended Euclid 路 ii. Linear Congruences and CRT 路 iii. Primes and Sieves 路 iv. Primality Testing and Factorization 路 v. Arithmetic Functions and M枚bius 路 vi. Harmonic Lemma and Floor Sums 路 vii. Sublinear Sieves and Prime Counting 路 viii. Factorials and Binomials mod p 路 ix. Primitive Roots and Discrete Log 路 x. Quadratic Residues and Modular Roots 路 xi. Continued Fractions and Pell Equations 路 xii. Number Theory Miscellany
15. Combinatorics
i. Counting Fundamentals 路 ii. Binomial Identities 路 iii. Inclusion-Exclusion and Derangements 路 iv. Catalan Numbers and Lattice Paths 路 v. Stirling, Bell and Partition Numbers 路 vi. Burnside and P贸lya 路 vii. Generating Functions 路 viii. Counting Graphs and Trees 路 ix. Young Tableaux and RSK
16. Linear Algebra
i. Matrices and Matrix Power 路 ii. Gaussian Elimination, Rank and Inverse 路 iii. Determinants and Permanents 路 iv. Characteristic Polynomial 路 v. Sparse and Structured Matrices
17. Polynomials and FFT
i. Fast Fourier Transform 路 ii. Number-Theoretic Transform 路 iii. Convolution Variants 路 iv. Online Convolution 路 v. Power Series Operations 路 vi. Multipoint Evaluation and Interpolation 路 vii. Composition and Taylor Shift 路 viii. Polynomial GCD and Resultant 路 ix. Counting with Power Series 路 x. Linear Recurrences 路 xi. Polynomial Factorization
18. Strings
i. String Basics and Parsing 路 ii. String Hashing 路 iii. Prefix Function and Z-Function 路 iv. Trie and Aho-Corasick 路 v. Other Pattern Matching 路 vi. Suffix Array and LCP 路 vii. Suffix Automaton 路 viii. Suffix Tree 路 ix. Burrows-Wheeler Transform 路 x. Palindromes and Manacher 路 xi. Eertree and Palindromic Factorization 路 xii. Lyndon Words and Minimal Rotation 路 xiii. Runs and Periodicity
19. Geometry
i. Points, Vectors and Orientation 路 ii. Lines and Segments 路 iii. Triangles 路 iv. Polygons 路 v. Convex Hull 路 vi. Dynamic Convex Hull 路 vii. Rotating Calipers 路 viii. Convex Polygon Queries and Tangents 路 ix. Half-Plane Intersection 路 x. Minkowski Sum 路 xi. Polygon Clipping and Union 路 xii. Circles and Inversion 路 xiii. Circle Union and Angular Sweep 路 xiv. Minimum Enclosing Circle 路 xv. Sweep Line and Segment Intersections 路 xvi. Closest Pair 路 xvii. Manhattan Geometry 路 xviii. Point Location and Point Counting 路 xix. 3D Geometry and 3D Hull 路 xx. Delaunay and Voronoi 路 xxi. Planar Graphs and Faces
20. Game Theory
i. Combinatorial Games and Nim 路 ii. Sprague-Grundy 路 iii. Hackenbush and Partizan Games 路 iv. Loopy Games and Retrograde Analysis 路 v. Game DP, Minimax and Game Search 路 vi. Games on Graphs and Matchings
21. Complete Search
i. Backtracking and Pruning 路 ii. Meet in the Middle 路 iii. A*, IDA* and Branch and Bound 路 iv. Exact Cover and Dancing Links 路 v. Maximum Clique and Independent Set 路 vi. Satisfiability 路 vii. Steiner Tree
22. Randomized and Heuristics
i. Randomized Algorithms 路 ii. Heuristic Optimization
23. Numerical Methods
i. Floating Point 路 ii. Big Integers and Fractions 路 iii. Root Finding and Integration 路 iv. Linear Programming
24. Theory and Beyond CP
i. Complexity Theory and NP-Hardness 路 ii. Approximation Algorithms 路 iii. Theoretical Algorithms Catalog
25. Puzzles
i. Tower of Hanoi 路 ii. Water Jug 路 iii. Wolf Goat Cabbage 路 iv. Bridge Crossing 路 v. 100 Prisoners 路 vi. Monty Hall 路 vii. Secretary Problem 路 viii. Poisoned Wine 路 ix. Celebrity Problem 路 x. Puzzle Index by Technique 路 xi. Josephus Problem 路 xii. Counterfeit Coin and 12 Coins 路 xiii. Egg Dropping 路 xiv. Lights Out 路 xv. Prisoners and Hats 路 xvi. River Crossings 路 xvii. Knight鈥檚 Tour and N Queens 路 xviii. Coupon Collector 路 xix. Birthday Problem 路 xx. Gambler鈥檚 Ruin 路 xxi. Two Envelopes Paradox 路 xxii. Boy or Girl and Bertrand鈥檚 Box 路 xxiii. St. Petersburg Paradox 路 xxiv. Buffon鈥檚 Needle 路 xxv. Ballot Problem 路 xxvi. Stable Marriage 路 xxvii. Blue-Eyed Islanders and Muddy Children 路 xxviii. Pirates and Gold 路 xxix. 100 Doors (Lockers) 路 xxx. Rope Burning and Hourglasses 路 xxxi. Bachet鈥檚 Weights 路 xxxii. Chicken McNugget (Frobenius Coin Problem) 路 xxxiii. Bachet鈥檚 Game and the 21 Game 路 xxxiv. Wythoff鈥檚 Game 路 xxxv. Chomp and Hex 路 xxxvi. Seven Bridges of K枚nigsberg 路 xxxvii. Mutilated Chessboard and Tilings 路 xxxviii. Fifteen Puzzle 路 xxxix. Rubik鈥檚 Cube and Permutation Puzzles 路 xl. Peg Solitaire 路 xli. Sudoku 路 xlii. Magic Squares 路 xliii. Latin Squares and Euler鈥檚 36 Officers 路 xliv. Kirkman鈥檚 Schoolgirl Problem 路 xlv. Party Problem (Ramsey R(3,3) = 6) 路 xlvi. Cake Cutting and Fair Division 路 xlvii. Pancake Sorting 路 xlviii. Collatz (3n + 1) 路 xlix. Wheat and Chessboard 路 l. Fibonacci Rabbits 路 li. Ant on a Rubber Rope 路 lii. Sum and Product Puzzle and Cheryl鈥檚 Birthday 路 liii. Zebra Puzzle (Einstein鈥檚 Riddle) 路 liv. Knights and Knaves 路 lv. 100 Prisoners and a Light Bulb 路 lvi. Bulgarian Solitaire 路 lvii. Chameleons 路 lviii. Gold Chain 路 lix. Bags of Coins in One Weighing 路 lx. Tromino Tiling 路 lxi. Coins in a Row 路 lxii. Instant Insanity 路 lxiii. Jeep Problem 路 lxiv. Monkey and Coconuts 路 lxv. Icosian Game 路 lxvi. 24 Game and Countdown 路 lxvii. Chinese Rings (Baguenaudier) 路 lxviii. Gas Station Circuit 路 lxix. Socks, Handshakes and Pigeonhole Puzzles 路 lxx. Fitch Cheney Five-Card Trick