Dynamic Programming
Bitmask DP, digit DP, interval DP, tree DP, and contribution techniques through 10 problems.
Lessons
1. Introduction to Advanced DP
What this section covers
2. DP Techniques Overview
The patterns ahead
3. Codeforces 16E Fish - Problem Statement
CF 16E - probability bitmask DP
4. Codeforces 16E Fish - Solution
State is surviving set
5. Codeforces 16E Fish - Implementation
Expected value over pairs
6. Codeforces 16E Fish - Example and Complexity Analysis
Exponential but feasible
7. Codeforces 580D Kefa and Dishes - Problem Statement
CF 580D - satisfaction with bonuses
8. Codeforces 580D Kefa and Dishes - Solution
Track set and last dish
9. Codeforces 580D Kefa and Dishes - Implementation
Iterate by population count
10. Codeforces 580D Kefa and Dishes - Example and Complexity Analysis
Standard bitmask bounds
11. Codeforces 453B Little Pony and Harmony Chest - Problem Statement
CF 453B - coprime sequence
12. Codeforces 453B Little Pony and Harmony Chest - Why Naive Fails
Too many combinations
13. Codeforces 453B Little Pony and Harmony Chest - Solution
Track used primes
14. Codeforces 453B Little Pony and Harmony Chest - Implementation
Enumerate candidate values
15. Codeforces 453B Little Pony and Harmony Chest - Example and Complexity Analysis
Large mask but sparse
16. Codeforces 1070A Find a Number - Problem Statement
CF 1070A - digit sum and divisibility
17. Codeforces 1070A Find a Number - Why Naive Fails
Infinite search space
18. Codeforces 1070A Find a Number - Solution
BFS on remainder and sum
19. Codeforces 1070A Find a Number - Implementation
BFS with path reconstruction
20. Codeforces 1070A Find a Number - Example and Complexity Analysis
Polynomial in d and s
21. Codeforces 461B Appleman and Tree - Problem Statement
CF 461B - partition into black-rooted subtrees
22. Codeforces 461B Appleman and Tree - Why Naive Fails
Exponential edge subsets
23. Codeforces 461B Appleman and Tree - Solution
DP on subtree state
24. Codeforces 461B Appleman and Tree - Implementation
DFS combining children
25. Codeforces 1312E Array Shrinking - Problem Statement
CF 1312E - merge equal neighbors
26. Codeforces 1312E Array Shrinking - Why Naive Fails
Operation order matters
27. Codeforces 1312E Array Shrinking - Solution
Two DP tables
28. Codeforces 1312E Array Shrinking - Implementation
Iterate by interval length
29. Codeforces 1312E Array Shrinking - Example and Complexity Analysis
Cubic in array size
30. Codeforces 1398D Colored Rectangles - Problem Statement
CF 1398D - maximize rectangle area sum
31. Codeforces 1398D Colored Rectangles - Solution
DP on pairs used
32. Codeforces 1398D Colored Rectangles - Implementation
Three nested loops
33. Codeforces 1398D Colored Rectangles - Example and Complexity Analysis
Product of pair counts
34. Codeforces 1467D Sum of Paths - Problem Statement
CF 1467D - contribution over all paths
35. Codeforces 1467D Sum of Paths - Why Naive Fails
Exponential paths
36. Codeforces 1467D Sum of Paths - Solution
Count paths through each cell
37. Codeforces 1467D Sum of Paths - Implementation
Build left and right tables
38. Codeforces 1467D Sum of Paths - Example and Complexity Analysis
Quadratic in n and k
39. Codeforces 1238E Keyboard Purchase - Problem Statement
CF 1238E - arrange letters to minimize cost
40. Codeforces 1238E Keyboard Purchase - Why Naive Fails
Permutation explosion
41. Codeforces 1238E Keyboard Purchase - Solution
Precompute transition costs
42. Codeforces 1238E Keyboard Purchase - Implementation
SOS DP for subset sums
43. Codeforces 1238E Keyboard Purchase - Example and Complexity Analysis
Exponential but tight
44. Codeforces 1542D Priority Queue - Problem Statement
CF 1542D - expected sum after deletions
45. Codeforces 1542D Priority Queue - Why Naive Fails
Exponential subsequences
46. Codeforces 1542D Priority Queue - Solution
Count survivals per value
47. Codeforces 1542D Priority Queue - Implementation
DP for each push operation
48. Codeforces 1542D Priority Queue - Example and Complexity Analysis
Quadratic overall
49. Quiz: Advanced DP Techniques
Test your understanding
50. Section Recap
What you've learned