Chapter 1: Essential Techniques

These are the techniques that solve most Div 2 A–C problems. Prefix sums, binary search, two pointers, greedy — these aren't fancy, but they're the workhorses you'll reach for hundreds of times. This chapter also teaches you how to think about problems: when to sort first, when to brute-force, and when a greedy approach works vs. when you need DP. Master these and you'll consistently solve 3–4 problems per contest.

Coming from: Chapter 0 — Fundamentals — C++ fluency, complexity analysis, and STL basics Going to: Chapter 2 — Data Structures — segment trees, DSU, and the data structures that power efficient algorithms Bridge: BRIDGE-to-data-structures.md — connecting techniques to the data structures that power them

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	How to Solve Problems	Beginner	"I don't know where to start"
02	Simulation	Beginner	"Do exactly what the problem says"
03	Sorting and Searching	Beginner	"Sort first, then decide"
04	Binary Search	Beginner	"Sorted array" + lookup, or monotonic predicate
05	Two Pointers	Beginner	"Find pair with sum = X" in sorted array
06	Sliding Window	Beginner	"Longest/shortest subarray with property P"
07	Prefix Sums	Beginner	"Range sum query" asked repeatedly
08	Difference Arrays	Beginner	"Add +k to range [l, r]" many times
09	Coordinate Compression	Intermediate	Huge value range but few distinct values
10	Greedy	Intermediate	"Maximize/minimize" + exchange argument works
11	Complete Search	Beginner	n ≤ 20 + "find best among all possibilities"
12	Constructive Algorithms	Intermediate	"Build an object satisfying these constraints"
13	Contribution Technique	Intermediate	"Sum over all pairs/subsets" → count each element's contribution
14	Divide and Conquer	Beginner	"Split, recurse, combine" (merge sort pattern)
15	Ternary Search	Beginner	"Find min/max of unimodal function"
16	Meet in the Middle	Intermediate	n ≤ 40 + "enumerate subsets" (too big for 2ⁿ, split in half)
17	Interactive Problems	Beginner	"Query the judge" + binary search on answer
18	Randomization Techniques	Intermediate	"Expected value trick" or "random sampling beats worst-case"

If You Only Read 3 Files

1. Prefix Sums — because O(1) range sum queries are the single highest-value technique per line of code. You'll use this in nearly every contest.
2. Binary Search — because "binary search on the answer" is a meta-technique that turns optimization problems into decision problems. Once you see it, it's everywhere.
3. Greedy — because knowing when greedy works (and when it doesn't, so you need DP) is the most important judgment call in competitive programming.

Cross-Chapter Connections

• Prefix Sums evolves into Fenwick Tree and Segment Tree when you also need updates
• Greedy vs. DP? See the DP vs Greedy Guide in Chapter 11
• Two Pointers generalizes into Mo's Algorithm for offline range queries
• Coordinate Compression is a prerequisite for Sweep Line problems in Chapter 9
• Meet in the Middle uses the same "split and merge" idea as DP — Bitmask but avoids full 2ⁿ enumeration

---

File Listing

File	Topic	Level
how-to-solve-problems	How to Solve Problems	⭐
simulation	Simulation	⭐
sorting-and-searching	Sorting and Searching	⭐
prefix-sums	Prefix Sums	⭐
difference-arrays	Difference Arrays	⭐
two-pointers	Two Pointers	⭐
sliding-window	Sliding Window	⭐
binary-search	Binary Search	⭐
ternary-search	Ternary Search	⭐
complete-search	Complete Search and Backtracking	⭐
divide-and-conquer	Divide and Conquer	⭐
interactive-problems	Interactive Problems	⭐
greedy	Greedy Algorithms	⭐⭐
constructive-algorithms	Constructive Algorithms	⭐⭐
contribution-technique	Contribution Technique	⭐⭐
coordinate-compression	Coordinate Compression	⭐⭐
meet-in-the-middle	Meet in the Middle	⭐⭐
randomization-techniques	Randomization Techniques	⭐⭐

Suggested Reading Order

1. Simulation — implement what the problem says, step by step
2. Sorting and Searching — sort first, then unlock many approaches
3. Prefix Sums — O(1) range queries with the highest value per line of code
4. Difference Arrays — O(1) range updates, the dual of prefix sums
5. Two Pointers — turn O(n²) brute force into O(n)
6. Sliding Window — maintain a moving window across input
7. Binary Search — halve the search space every step
8. Ternary Search — find extrema of unimodal functions
9. Complete Search — systematically explore all candidates
10. Divide and Conquer — split, recurse, combine
11. Interactive Problems — query the judge in real time
12. Greedy — locally optimal choices that yield global optima
13. Constructive Algorithms — build objects satisfying constraints
14. Contribution Technique — count each element's contribution
15. Coordinate Compression — map sparse values to dense indices
16. Meet in the Middle — reduce O(2^n) to O(2^(n/2))
17. Randomization Techniques — probabilistic methods and hashing
18. How to Solve Problems — the thinking framework from problem statement to correct code