Chapter A · Appendix
How to Read This Book
The two-pass method, what the badges mean, how to use the demos, and what to do when a proof does not land.
#The skeleton of every page
Every page has the same skeleton
- Front matter — difficulty, complexity badges, prerequisites, and the problems this page makes solvable,
- a framing paragraph: what question the page answers and what breaks without it,
- definitions → theorem → proof: the proof is written at the level of "the step that is not obvious", so fill in the algebra yourself — that is where the learning is,
- a comparison table when several methods exist (this is the part people skip and then regret in a contest),
- code — complete enough to type, not complete enough to paste blindly: variable names carry the invariants,
- warnings/traps — the bugs that come from knowing 80% of the algorithm,
- an interactive demo where one helps, and
- problems with the reason each was chosen.
#Two passes, not one
Pass 1 (a day): read the chapter leads and the tables only — every page's first screen. You are building an index, not understanding. When a table says "X vs Y", stop and guess which one the last problem you failed needed. Pass 2 (a week, interleaved with problems): read one chapter per sitting, implement its main algorithm from memory into a blank file, then compare against the page's snippet and note the difference. The difference is what you will forget in a contest; write it as a comment at the top of your template. Reading without implementing has a documented half-life of about three days.
#Using the demos
How to use the demos
Each demo is a stepper, not an animation. Three habits make them worth the minute they cost:
- predict the next frame before pressing Next (if you cannot, you do not yet know the invariant, which is the thing being tested),
- drive it to a worst case: a path, a star, a graph where the algorithm does no work at all — every demo has controls for this, and the failure mode you find there is the one in the problemset,
- then reimplement the demo's data structures, not the algorithm:
lvl/ptrarrays, theused-with-timestamp trick, the "emit then reverse" order — those are the parts that get subtly mangled under time pressure.
#When a proof does not land
When a proof does not land, do this
- State it for n = 1, 2, 3 by hand. If the base case is where the proof starts, most "understood" claims were never checked,
- find the invariant sentence (usually one paragraph, sometimes only in the code comment) and ask which step would fail without it — that step is what the proof is actually about,
- break the hypothesis and see where the proof dies: e.g. remove "non-negative weights" from Dijkstra and construct the counterexample (Dijkstra's Algorithm), which is the fastest way to know what a condition is for,
- implement the algorithm on a random instance against a brute force (the stress-test loop in Contest Template), and read the mismatching case — a 4-vertex counterexample explains a proof gap better than another hour of reading.
#A 10-day plan
Two pages a day, one implemented from memory per day. By day 10 you have written ~12 algorithms twice, which is how they survive contact with a clock.
#What this book is not
- not a reference for the fastest implementation of anything — the constant-factor craft lives in contest blogs and in reading the top submissions after you solve something,
- not a proof of the big theorems in full (the four-colour theorem, planar separator optimality, the blossom post-processing): where a result is quoted, the page says so explicitly and names what is missing,
- not a substitute for volume: the only reliable way to get good at graphs is to solve problems you cannot do, and every page here ends with those. If you read 78 pages and solved 5 problems, you have prepared a checklist, not a skill.
Feedback loop for the gaps I cannot fix
The site is generated from the markdown in this repository; if a page's claim is wrong, an invariant is stated incorrectly, or a "trap" list misses the bug you actually hit, open an issue with the counterexample — a 6-vertex graph is enough. Errata that come with a test case get fixed the same day, because they are the only kind of correction that can be verified.