Convex Hull Trick
You know QI-based optimizations. Now meet recurrences as lines and query minimum/maximum with CHT.
Lessons
1. Intro
The Goal
2. A Different Pattern
The problem
3. Vocabulary - Linear Function
The building block
4. Rewriting the DP
The transformation
5. Quiz: Linear Form Recognition
Identifying CHT applicability
6. The Key Observation
Lines in a plane
7. Vocabulary - Lower Envelope
The structure
8. Quiz: Lower Envelope
Understanding the geometry
9. Why Most Lines Don't Matter
The pruning
10. What Is the Convex Hull Trick?
Core idea
11. When Queries Are Sorted
The simple case
12. The Deque Approach
Data structure
13. Deque Operations - Walkthrough
Tracing the deque maintenance
14. Adding a New Line
Maintaining the hull
15. Quiz: Deque Invariant
Why we pop from back
16. Querying the Minimum
Finding the best line
17. CHT Query - Walkthrough
Tracing a query
18. Why O(n) Total
Amortized analysis
19. Visualizing CHT
Mental model
20. Codeforces 319C Kalila and Dimna - Problem Statement
CF 319C
21. Codeforces 319C Kalila and Dimna - The DP
State and transition
22. Codeforces 319C Kalila and Dimna - CHT Form
The transformation
23. Codeforces 319C Kalila and Dimna - Why It Works
The conditions
24. Codeforces 319C Kalila and Dimna - Implementation
The code
25. Codeforces 319C Kalila and Dimna - Walkthrough
Tracing the full solution
26. Lessons from CHT
summary
27. Challenge: Non-Sorted Slopes
Handling arbitrary order
28. When Queries Aren't Sorted
The general case
29. Binary Search on the Hull
O(log n) queries
30. Vocabulary - Li Chao Tree
Alternative structure
31. Li Chao Tree - Walkthrough
Understanding the structure
32. Quiz: Li Chao vs Deque
Choosing the right structure
33. Common Mistakes
What to avoid
34. Commando - Problem Statement
Classic CHT problem
35. Commando - Implementation
Handling maximization
36. Covered Walkway - Problem Statement
Another classic
37. Quiz: Covered Walkway Algebra
Deriving the linear form
38. Challenge: 2D CHT
Higher dimensions
39. Pattern - Convex Hull Trick
Recognition
40. Pattern - CHT Recognition
When to apply CHT
41. Implementation Tips
Practical advice
42. What's Next
Preview of Monotonic Queue
43. Section Recap
What we learned
Practice Problems
Covered with full walkthrough in this section.
The canonical CHT problem. Optimal substructure where cost depends linearly on previous state, perfect for convex hull optimization.
Requires CHT in both directions. Tests understanding of when slopes are monotonic vs need Li Chao tree.
Elegant geometry problem reducible to CHT. Requires insight to transform rectangle selection into linear DP.
CHT on trees with small-to-large merging. Combines convex hull with tree DP and DSU-on-tree.
Multi-dimensional DP with CHT optimization. Teaches how to reduce O(n²k) to O(nk log n).
Geometry + CHT combination. Requires translating projection constraints into convex hull queries.
Dijkstra + CHT combination. Models flight costs as linear functions requiring convex hull queries.
Classic DP with quadratic cost. Natural introduction to CHT before harder variants.
Simpler jump optimization. Good warmup for understanding optimal substructure in CHT problems.
DP with binary search. Understanding interval DP optimization leads naturally to CHT ideas.
Frog jumping with quadratic cost - the canonical convex hull trick problem.