Chapter 10: Patterns and Recipes

This chapter is about meta-skills, not new algorithms. By now you know segment trees, DP, BFS, exchange arguments. The harder skill is choosing which one before you've written a line of code, and combining two of them when neither alone suffices.

The chapter mixes two kinds of file. Reasoning tools — pattern recognition, exchange arguments, amortized analysis, invariants, contribution counting, binary search on answer, transform-and-conquer — are ways of thinking about a problem. Recipes — small-to-large merging, rerooting DP, technique layering, harmonic loops — are concrete patterns you slot in once recognition has fired. Most files lean toward one mode but touch both.

Coming from: Chapter 9 — Offline Techniques  ·  Going to: Chapter 11 — Contest Craft

Files

#	Topic	Mode	Trigger phrase
01	Small-to-Large Merging	recipe	"merge sets while keeping info" — always merge smaller into larger
02	Rerooting (Tree DP)	recipe	"answer for every node as root" in O(n) total
03	Problem Pattern Recognition	reasoning	"n ≤ X → what complexity?"
04	Technique Layering	recipe	"this needs BFS and DP" — combine 2–3 techniques
05	Exchange Arguments	reasoning	"prove greedy is correct" — swap adjacent, show no worse
06	Advanced Contribution Counting	reasoning	"sum over all pairs/subarrays" — count each element's contribution
07	Amortized Analysis	reasoning	"looks O(n²), actually O(n)" — count total work
08	Harmonic Series Pattern	recipe	"nested loop over multiples" → O(n log n)
09	Invariant Technique	reasoning	"apply operations until impossible" → find what doesn't change
10	Binary Search on Answer	reasoning	"minimize X" → "can we achieve X?" + bsearch
11	Transform and Conquer	reasoning	compress, complement, reframe

If you only read three

1. Problem Pattern Recognition — the highest-leverage file in the notebook. Maps n to plausible complexities and a small set of algorithms. Use it before thinking about the solution at all.
2. Rerooting — "tree DP for every root" shows up constantly in CF 1600+. The two-pass trick turns O(n²) into O(n).
3. Small-to-Large Merging — merging the smaller side into the larger gives O(n log n) total. It powers DSU, set/map merges on trees, and DSU-on-tree.

How files connect

• Pattern recognition (03) references techniques across every chapter; use it as a decision tree when you're stuck.
• Rerooting (02) builds on DP on Trees in Ch 4 and DFS in Ch 3.
• Small-to-large (01) is the same amortization that powers DSU on Tree in Ch 6 — that file is the contest implementation; this one is the principle and proof.
• Technique layering (04) catalogs how Ch 1–9 techniques compose for harder problems.
• Exchange arguments (05) extend Greedy with proof skeletons.
• Contribution counting (06) builds on the basic Contribution Technique from Ch 1.
• Amortized analysis (07) explains why small-to-large, DSU, and monotonic stacks are fast.
• Together with the Data Structure Selection Guide and DP vs Greedy Guide in Ch 11, this chapter forms the recognition spine of the book.

Suggested order

03 → 01 → 02 → 04 → 05 → 06 → 07 → 08 → 09 → 10 → 11.

Recognition first, then the two big recipes, then layering, then proofs and reframings.