Greedy
Exchange arguments, two-pass greedy and reachability.
5 notes · 22 min total
Questions0 of 33 done
Warm up with these before Phase 1.
Patterns
- 1Greedy Overview & Exchange ArgumentRecognize when a locally best choice is globally best, prove it with an exchange argument, and know when to fall back to DP.6 min
- 2Two-Pass GreedySatisfy constraints that point both left and right by sweeping once in each direction and combining the results.3 min
- 3Sort, Then Place or PairUse sorting to put extremes where you can reason about them, then pair smallest with largest or place items in a safe order.4 min
- 4Counting & Bound ArgumentsReplace a simulation with a count or a bound: the stranded largest pile, an open-bracket range, and why the top bit dominates.5 min
- 5Reachability: Jump Game & Gas StationTrack the furthest point you can reach, count jumps in BFS-like levels, and find a valid start for a circular route.4 min