D&C and Knuth Optimization
Your DP is too slow. Learn D&C optimization and Knuth optimization based on the quadrangle inequality.
Lessons
1. Intro
What you'll learn
2. When Naive DP Fails
The problem
3. Vocabulary - Quadrangle Inequality
The condition
4. Quiz: Quadrangle Inequality
Testing the concept
5. Why QI Implies Monotonicity
The proof
6. Quiz: Monotonicity Implication
Why QI helps
7. D&C and Knuth Overview
Two techniques
8. What Is D&C Optimization?
Core idea
9. The D&C Recursion
Step by step
10. D&C Recursion - Walkthrough
Tracing the divide and conquer
11. Why D&C Is O(n log n)
The analysis
12. Quiz: D&C Complexity
Why O(n log n)
13. Visualizing D&C
Mental model
14. Codeforces 321E Ciel and Gondola - Problem Statement
Codeforces 321E
15. Codeforces 321E Ciel and Gondola - The DP
State and transition
16. Codeforces 321E Ciel and Gondola - Why QI Holds
The proof
17. Codeforces 321E Ciel and Gondola - Implementation
The code
18. Codeforces 321E Ciel and Gondola - Walkthrough
Tracing the optimization
19. Lessons from D&C Optimization
summary
20. Challenge: Proving QI
Verification techniques
21. What Is Knuth's Optimization?
Core idea
22. The Double Bound
Why it works
23. The Iteration Order
Processing by length
24. Knuth's Optimization - Walkthrough
Tracing the double bound
25. Why O(n²) Total
The amortized analysis
26. Visualizing Knuth
Mental model
27. Optimal BST - Problem Statement
Classic application
28. Optimal BST - The DP
State and transition
29. Optimal BST - Why QI Holds
The proof
30. Optimal BST - Implementation
The code
31. Optimal BST - Walkthrough
Tracing the classic example
32. Lessons from Knuth's Optimization
summary
33. Breaking a String - Problem Statement
Classic Knuth problem
34. Breaking a String - Implementation
Handling the edge cases
35. Printing Neatly - Problem Statement
Line breaking optimization
36. Server Allocation - Problem Statement
Partitioning with cost
37. Server Allocation - Implementation
Computing costs efficiently
38. D&C vs Knuth
When to use which
39. Quiz: Knuth vs D&C
Choosing the right one
40. Common Mistakes
What to avoid
41. Challenge: When QI Fails
Recognizing inapplicable cases
42. Challenge: Combining with Other Techniques
Advanced applications
43. Pattern - Quadrangle Optimizations
Core idea
44. Implementation Checklist
Avoiding common bugs
45. Practice - Identify the Optimization
Pattern recognition exercise
46. What's Next
Preview of Convex Hull Trick
47. Section Recap
What we learned
Practice Problems
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Partition people into k groups minimizing cost. Classic D&C optimization.
Split array into k segments minimizing sum of squared frequencies. D&C DP.
Minimize cost of k partitions. D&C optimization with segment tree.
Maximize distinct values across k segments. D&C DP with segment tree.
Minimum fuel tank for all trips. D&C optimization with monotonicity.
Minimum cost to cut trees. Convex hull trick / D&C applicable.
Process queries on dynamic graph. Offline D&C with DSU.
Schedule jobs over d days. Can optimize with D&C or monotonic stack.
Split into k palindromes with min changes. DP with precomputed costs.
Paint houses forming target neighborhoods. 3D DP with optimization potential.