AtCoder Educational DP Contest
Welcome to the AtCoder Educational DP Contest section! This comprehensive collection covers 26 dynamic programming problems designed to teach and reinforce various DP techniques from basic to advanced.
Overview
The AtCoder Educational DP Contest is a curated set of problems that progressively build your understanding of dynamic programming. Each problem is labeled from A to Z and covers different DP patterns and techniques.
Problem Categories
Basic DP (Problems A-E)
1D Linear DP
- A - Frog 1 - 1D DP with linear transitions
- B - Frog 2 - 1D DP with k-step transitions
- Z - Frog 3 - Advanced DP with convex hull trick
State Machine DP
- C - Vacation - State machine DP with constraints
Knapsack Problems
- D - Knapsack 1 - Classic 0/1 knapsack
- E - Knapsack 2 - Value-based DP (state inversion)
Graph & Grid DP (Problems G-H)
- G - Longest Path - DP on Directed Acyclic Graphs (DAGs)
- H - Grid 1 - 2D grid DP with obstacles
Probability & Game Theory (Problems I-K)
- I - Coins - Probability DP
- J - Sushi - Expectation DP with state compression
- K - Stones - Game theory DP
Advanced DP Patterns (Problems L-M)
- L - Deque - Interval DP
- M - Candies - DP with prefix sum optimization
Interval & Bitmask DP (Problems N-O)
- N - Slimes - Interval DP with merging
- O - Matching - Bitmask DP
Tree DP (Problems P-V)
- P - Independent Set - Tree DP
- Q - Flowers - DP with segment tree
- V - Subtree - Tree DP with rerooting
Advanced Techniques (Problems R-Z)
- R - Walk - Matrix exponentiation
- S - Digit Sum - Digit DP
- T - Permutation - Insertion DP
- U - Grouping - Subset DP with bitmask
- W - Intervals - Interval covering DP
- X - Tower - Box stacking DP
- Y - Grid 2 - Inclusion-exclusion DP
- Z - Frog 3 - Convex hull trick
Learning Path
Beginner Level (A-C)
Start with these fundamental problems:
- Frog 1 - Learn basic 1D DP
- Frog 2 - Extend to multiple transitions
- Vacation - Understand state machine DP
Intermediate Level (D-M)
Build on fundamentals:
- Knapsack 1 & 2 - Master knapsack variants
- Grid 1 - Learn 2D DP
- Longest Path - DP on graphs
- Coins, Sushi - Probability and expectation DP
- Deque, Slimes - Interval DP
Advanced Level (N-Z)
Challenge yourself with advanced techniques:
- Matching - Bitmask DP
- Tree DP problems - Independent Set, Subtree
- Matrix Exponentiation - Walk
- Digit DP - Digit Sum
- Convex Hull Trick - Frog 3
Key DP Techniques Covered
1. Basic DP Patterns
- 1D Linear DP: Frog 1, Frog 2
- 2D Grid DP: Grid 1, Grid 2
- State Machine DP: Vacation
2. Optimization Techniques
- Space Optimization: Rolling arrays, state compression
- Time Optimization: Prefix sums, segment trees
- State Inversion: Knapsack 2
3. Advanced DP Types
- Interval DP: Deque, Slimes, Intervals
- Bitmask DP: Matching, Grouping
- Tree DP: Independent Set, Subtree
- Digit DP: Digit Sum
- Probability DP: Coins, Sushi
4. Optimization Algorithms
- Matrix Exponentiation: Walk
- Convex Hull Trick: Frog 3
- Inclusion-Exclusion: Grid 2
Problem Difficulty Guide
| Difficulty | Problems | Key Concepts |
|---|---|---|
| ⭐ Beginner | A, B, C, D, H | Basic DP, 1D/2D DP |
| ⭐⭐ Intermediate | E, G, I, J, K, L, M, N | Advanced patterns, optimization |
| ⭐⭐⭐ Advanced | O, P, Q, R, S, T, U, V, W, X, Y, Z | Complex techniques, specialized algorithms |
Practice Recommendations
Week 1: Foundation
- Complete problems A, B, C, D, H
- Focus on understanding DP state definitions
- Practice writing recurrence relations
Week 2: Patterns
- Complete problems E, G, I, J, K, L, M
- Learn different DP patterns
- Practice optimization techniques
Week 3: Advanced
- Complete problems N, O, P, Q, R, S, T, U, V, W, X, Y, Z
- Master advanced techniques
- Challenge yourself with complex problems
Resources
Official Contest
- AtCoder Educational DP Contest - Original contest page
Related Problems
- Check each problem’s analysis page for related CSES and LeetCode problems
Tips for Success
- Start with Basics: Don’t skip the easy problems - they build essential foundations
- Understand State: Clearly define what your DP state represents
- Practice Transitions: Master writing recurrence relations
- Optimize Gradually: First make it work, then optimize
- Study Patterns: Recognize common DP patterns across problems
Ready to start? Begin with Frog 1 and work your way through the problems systematically!