Slope Trick
DP with absolute value costs creates piecewise linear functions. Slope Trick tracks only the slopes.
Lessons
1. Intro
Why Slope Trick exists
2. Piecewise Linear Functions
Shape of costs
3. Quiz: Piecewise Linear
Understanding the structure
4. Vocabulary - Slope-Change Points
Critical breakpoints
5. Heap Representation
Tracking breakpoints
6. Heap Representation - Walkthrough
Storing breakpoints efficiently
7. Quiz: Slope-Change Points
Knowledge check
8. Quiz: Why Two Heaps
Understanding the structure
9. Codeforces 713C Sonya and Problem Without a Legend - Problem Statement
CF 713C
10. Sonya - Transform Trick
Making it non-decreasing
11. Sonya - DP Formulation
Convex function
12. Sonya - Heap Operations
Double-push trick
13. Sonya - Implementation
Full solution
14. Sonya - Walkthrough
Tracing the heap operations
15. Challenge: Strictly Increasing
Variant with strict inequality
16. Codeforces 865D Buy Low Sell High - Problem Statement
CF 865D
17. Codeforces 865D Buy Low Sell High - The Idea
Retroactive decisions
18. Codeforces 865D Buy Low Sell High - Why It Works
Slope function analog
19. Codeforces 865D Buy Low Sell High - Implementation
Greedy with heap
20. Codeforces 865D Buy Low Sell High - Walkthrough
Tracing the greedy insight
21. Quiz: Regret Trick
Understanding the regret mechanism
22. CSES Increasing Array II - Problem Statement
CSES 2132
23. CSES - DP Function Shape
Convexity preservation
24. CSES - Heap Mechanics
Maintaining breakpoints
25. CSES - Implementation
Max-heap solution
26. CSES - Walkthrough
Increasing array variant
27. Prefix Min Operation
Advanced technique
28. Prefix Min Operation - Walkthrough
How prefix min affects the function
29. K-Increasing - Problem Statement
Generalized version
30. Jobs and Deadlines - Problem Statement
Scheduling variant
31. When to Use Slope Trick
Pattern recognition
32. Quiz: When Slope Trick
Recognizing the pattern
33. Common Mistakes
What to avoid
34. Common Mistakes - Walkthrough
Avoiding mistakes
35. Complexity Analysis
Why it's fast
36. Complexity Analysis - Walkthrough
Understanding the efficiency
37. Making Array Beautiful - Problem Statement
Another variant
38. Challenge: Three Heaps
Non-convex extensions
39. Lazy Propagation
Efficient global shifts
40. Potions - Problem Statement
IOI variant
41. Quiz: Slope Trick vs CHT
Comparing techniques
42. Practice Strategy
How to improve
43. Pattern - Slope Trick Recognition
Identifying applicable problems
44. Implementation Template
Reusable structure
45. Challenge: Online Queries
Query the function at points
46. What's Next
Preview of Broken Profile DP
47. Section Recap
What we learned
Practice Problems
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
THE canonical slope trick problem. Make array non-decreasing with minimum cost, using piecewise linear DP.
Stock trading with slope trick. Maintains optimal profit function as piecewise linear.
2D slope trick variant. Grid movement problem reduced to piecewise linear optimization.
Geometry + inversion counting. Foundation for understanding coordinate transformations in slope trick.
Slope trick for partition optimization. Maintaining optimal prefix/suffix with piecewise costs.
Binary search + absolute value. Foundation for slope trick piecewise linear intuition.
Difference array technique. Related slope analysis for piecewise cost functions.
Greedy with heap. Similar heap operations to slope trick slope maintenance.
Heap-based simulation. Understanding priority queue operations helps with slope trick heaps.