Appearance
Practice Ladder: CF 1700 --> 2100
50 curated problems for advanced competitive programming. Prerequisites: solid command of all topics in the 1400 --> 1700 ladder.
Quick Revisit
- SKILL FOCUS: advanced techniques -- advanced DP, SCC, flows, suffix arrays, FFT
- DIFFICULTY: 1200--2500
- PROBLEMS: 50
- PREREQUISITE: Ladder 1400-1700
Contents
- Advanced DP (Digit, Interval, Trees, SOS)
- Advanced Graphs (Bridges, SCC, Flows, Centroid Decomposition)
- Advanced Strings (Suffix Array, Aho-Corasick)
- Math (FFT, Matrix Exponentiation, Game Theory)
- Range Queries (Lazy Segtree, Persistent Segtree)
- Offline Techniques (Mo's Algorithm, CDQ)
- Geometry (Convex Hull, Sweep Line)
- Advanced Greedy / Constructive
- Sqrt Decomposition
- Meet in the Middle
- Interactive
- Mental Traps
- What the Code Won't Teach You
- How to Use This Ladder
- Self-Test: Meta-Skills Checkpoint
Topic Distribution Across the Ladder
Advanced DP |################ 8
Adv. Graphs |################ 8
Adv. Strings |######## 4
Math (FFT/Mat) |############ 6
Range Queries |########## 5
Offline (Mo's) |######## 4
Geometry |###### 3
Adv. Greedy |######## 4
Sqrt Decomp |###### 3
Meet in Middle |#### 2
Interactive |###### 3
+--+--+--+--+--+--+--+--+--->
0 1 2 3 4 5 6 7 8
^ DP and Graphs dominate -- they are the backbone of 1900+ problems.Advanced DP (Digit, Interval, Trees, SOS)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 1 | Counting Numbers (CSES) | -- | digit dp | Digit DP with state tracking the previous digit to forbid consecutive equal digits. |
| 2 | Removal Game (CSES) | -- | interval dp | dp[l][r] = best score difference for the subarray l..r; both players play optimally. |
| 3 | Empty String (CF 1731E) | 2400 | interval dp, combinatorics | Count ways to remove the string by always erasing palindromic adjacent pairs; dp[l][r] over intervals counting sequences of removals. |
| 4 | Tree Matching (CSES) | -- | tree dp | dp[v][0/1] = max matching in subtree of v where v is unmatched/matched. |
| 5 | Tree Distances I (CSES) | -- | tree dp, rerooting | Two DFS passes: first find farthest in subtree, then reroot to get farthest overall. |
| 6 | Tree Distances II (CSES) | -- | tree dp, rerooting | Compute sum of distances from one root, then reroot: when moving to child, n-sz nodes get closer, sz get farther. |
| 7 | SOS DP (Bit Problem, CSES) | -- | SOS dp | Iterate over each bit position; dp[mask] accumulates contributions from all submasks. |
| 8 | AND Closure | 2100 | SOS dp, bitmask | Use SOS-DP to determine which masks can be produced by AND-ing subsets of the given set. |
Advanced Graphs (Bridges, SCC, Flows, Centroid Decomposition)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 9 | Flight Routes Check (CSES) | -- | SCC | Find SCCs; the graph is strongly connected iff there is exactly one SCC. |
| 10 | Planets and Kingdoms (CSES) | -- | SCC, kosaraju | Run Kosaraju's or Tarjan's algorithm to assign each node to its SCC. |
| 11 | Coin Collector (CSES) | -- | SCC, DAG dp | Condense SCCs into a DAG, then DP for longest path (sum of coins). |
| 12 | Giant Pizza (CSES) | -- | 2-SAT, SCC | Model constraints as implications; solve 2-SAT via SCC. |
| 13 | Critical Edges | -- | bridges | Tarjan's bridge-finding: edge (u,v) is a bridge iff low[v] > disc[u]. |
| 14 | Download Speed (CSES) | -- | max flow | Edmonds-Karp (BFS-based Ford-Fulkerson) for max flow from source to sink. |
| 15 | Police Chase (CSES) | -- | min cut | Max-flow = min-cut; find the cut edges by BFS on the residual graph. |
| 16 | Fixed-Length Paths I (CSES) | -- | centroid decomp | Centroid decomposition: count paths of length k through each centroid. |
Advanced Strings (Suffix Array, Aho-Corasick)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 17 | Substring Order I (CSES) | -- | suffix array, LCP | Build suffix array + LCP array; walk through suffixes counting distinct substrings until you reach the k-th. |
| 18 | Substring Order II (CSES) | -- | suffix array, LCP | Like Substring Order I but substrings counted with multiplicity -- use the same SA + LCP framework. |
| 19 | Substring Distribution (CSES) | -- | suffix array, LCP | For each length l, the number of distinct substrings can be derived from the LCP array. |
| 20 | Pattern Matching | 2200 | aho-corasick | Build an Aho-Corasick automaton of the pattern set, then feed the text through it. |
Math (FFT, Matrix Exponentiation, Game Theory)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 21 | Fibonacci Numbers (CSES) | -- | matrix expo | Matrix exponentiation: [[1,1],[1,0]]^n gives the n-th Fibonacci. |
| 22 | Throwing Dice (CSES) | -- | matrix expo | Build a 6x6 transition matrix for the dice-sum recurrence; exponentiate. |
| 23 | Polynomial Multiplication (CSES) | -- | FFT | Multiply two polynomials using FFT in O(n log n). |
| 24 | Stick Game (CSES) | -- | game theory, grundy | Compute Grundy values: dp[i] is "losing" iff all dp[i - p_k] are "winning." For Sprague-Grundy, XOR the per-pile Grundy numbers. |
| 25 | Nim Game I (CSES) | -- | game theory, nim | Standard Nim: first player wins iff XOR of pile sizes is non-zero. |
| 26 | Graph Paths I (CSES) | -- | matrix expo, graph | The number of paths of length k equals the (s,t) entry of the adjacency matrix raised to the k-th power. |
Range Queries (Lazy Segtree, Persistent Segtree)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 27 | Range Updates and Sums (CSES) | -- | lazy segtree | Support both range-add and range-set with lazy propagation; set overrides add. |
| 28 | Polynomial Queries (CSES) | -- | lazy segtree | Adding 1,2,3,...,k to a range can be decomposed into a linear function; maintain sum-of-constants and sum-of-slopes lazily. |
| 29 | Range Queries and Copies (CSES) | -- | persistent segtree | Each copy creates a new root sharing most of the old tree's nodes. |
| 30 | Salary Queries (CSES) | -- | segtree, coord compress | Coordinate-compress salaries; use a BIT/segtree to answer range-count queries with point updates. |
| 31 | Distinct Values Queries (CSES) | -- | offline, BIT | Offline: sort queries by right endpoint; for each value, only count its latest occurrence. |
Offline Techniques (Mo's Algorithm, CDQ)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 32 | Distinct Values Queries (CSES) | -- | Mo's, offline | Classic Mo's: maintain a frequency array; add/remove elements as the window slides. |
| 33 | D-query (SPOJ) | -- | Mo's | Count distinct values in a range -- identical structure to Mo's algorithm template. |
| 34 | XOR and Favorite Number | 2100 | Mo's, prefix xor | Maintain XOR prefix counts; Mo's with add/remove updates frequency of each prefix XOR. |
| 35 | Points and Distances | 2100 | CDQ, D&C | CDQ divide and conquer: split updates and queries by time, merge spatially. |
Geometry (Convex Hull, Sweep Line)
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 36 | Convex Hull (CSES) | -- | convex hull | Andrew's monotone-chain algorithm: build upper and lower hulls separately. |
| 37 | Point in Polygon (CSES) | -- | geometry, ray casting | Cast a ray rightward; count edge crossings -- odd = inside. |
| 38 | Line Segment Intersection (CSES) | -- | geometry | Use cross products to check orientation of triplets; handle collinear overlap. |
Advanced Greedy / Constructive
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 39 | Tasks and Deadlines (CSES) | -- | greedy, scheduling | Sort by duration; reward = deadline - finish time; shorter tasks first maximizes total reward. |
| 40 | Stick Lengths (CSES) | -- | greedy, median | The optimal target is the median -- minimizes total absolute deviation. |
| 41 | Movie Festival II (CSES) | -- | greedy, multiset | Generalized interval scheduling for k members; assign each movie to the member who finished earliest before it. |
| 42 | Reading Books II | 2100 | greedy, constructive | Schedule reading so two people never read the same book simultaneously; think about the longest book vs the rest. |
Sqrt Decomposition
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 43 | Mo's Algorithm Template (CSES Distinct Values) | -- | sqrt, Mo's | Block size sqrtn; sort queries by (l/sqrtn, r); add/remove elements at block boundaries. |
| 44 | Ynoi-style Range Distinct | 2100 | sqrt, heavy-light | Sqrt decomposition on the tree: preprocess blocks, answer queries by combining. |
| 45 | Holes | 2500 | sqrt decomp | Maintain next-escape and step-count for each block; rebuild a block in O(sqrtn) on update. |
Meet in the Middle
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 46 | Meet in the Middle (CSES) | -- | meet in middle | Split array in half; enumerate all subset sums of each half; two-pointer or binary search to count pairs summing to x. |
| 47 | Two Sets III (CSES, meet-in-the-middle variant) | -- | meet in middle, subset sum | When n is too large for a single bitmask DP, split into halves, enumerate subset sums of each, and combine via sort + two-pointer. |
Interactive
| # | Problem | Rating | Tags | Hint |
|---|---|---|---|---|
| 48 | Bake-Off (CF 1407D / Bouncing Boomerangs CF 1428D) | 1700 | interactive, binary search | Most "guess a number / find the index" problems reduce to binary search with O(log n) queries; verify the response format and flush after each query. |
| 49 | Chocolate Bunny (CF 1393B) | 1700 | interactive, ordering | Each query (i, j) returns max(p_i mod p_j, p_j mod p_i); the smaller of the two is identified by the larger response. Eliminate one element per query. |
| 50 | Guess the K-th Largest (CF 1486C2) | 2100 | interactive, binary search | Binary search on the index of the maximum, leveraging O(log n) queries that compare segments of length two. |
Mental Traps
Drawn from the companion reflection.
"At this level, I should be able to see solutions quickly." No. At 1900-2100, even specialists struggle for 30-60+ minutes on individual problems. The difference between 1700 and 2100 isn't solution speed -- it's what you do while stuck. A 2100-rated player makes better guesses, tries more promising approaches, and abandons dead ends faster. Being stuck for 45 minutes on a 1900-rated problem is expected and correct. What you do during those 45 minutes -- actively hypothesizing, testing ideas, connecting to known structures -- is the training.
Reading editorials without implementing. "I understand how this works" said without running code is almost always wrong at this level. Implementation at 1800+ requires handling subtle invariants and edge cases that only surface when you write the code. If you read 10 editorials and implement 2, you're building editorial-reading skill, not problem-solving skill.
Optimizing solved count instead of depth. You'd rather solve 5 "manageable" 1750-rated problems than struggle with 1 problem rated 1950 and fail. The failed 1950 attempt -- with proper post-analysis -- produces more growth than the 5 ACs. Track depth (how hard was this?) alongside breadth (how many?).
Treating hard problems as "not for me." "This uses FFT, I haven't studied that." A problem with a technique you don't know is a research prompt: you now know what to study next. Don't skip it -- mark it, study the technique, return.
Technique Mastery Depth
Level 3 | * Implement under pressure in <40 min
(own it) | |
| v
Level 2 | * Solved 3-5 problems, understand edge cases
(know it)| |
| v
Level 1 | * Read about it, solved 1 problem with help
(seen it)|
+--+----------+----------+----------+------->
CHT / Centroid Suffix Flows
Li Chao Decomp Array (MCMF)
^ "I've read about it" != "I know it."
Move every technique from Level 1 --> Level 3.
The gap between levels is ~5 full implementations each.What the Code Won't Teach You
Time-box aggressively with a layered editorial protocol. 1700-rated: 60 min. 1800-rated: 75 min. 1900-rated: 90 min. After the timer: do not immediately read the editorial. Write down your hypothesis and what you think you're missing. Then read only the editorial's first two sentences. Attempt again. Only then read in full. This protocol maximizes "almost-right" moments -- the most valuable learning stage.
Upsolving is mandatory, not optional. Every problem you fail in a contest is worth 1-2 hours of focused work. The problems are hard enough that even understanding the editorial requires effort. That effort is the learning. Treat failed contest problems as the core of your practice.
Read other people's solutions. After AC (or reading a full editorial), look at the top-5 fastest solutions from the contest. They're often shorter and reveal idioms you haven't internalized. Reading clean code from experienced competitors builds vocabulary you can recognize and adapt.
Diagnose your plateau specifically. If your rating is flat for three months, one of these is blocking you: (1) slow technique identification, (2) implementation bugs on specific techniques, (3) inability to model 1800+ problems, (4) poor time management in contests. Don't just "practice more" -- identify which lever to pull.
Stop treating advanced topics as a checklist. "I've read about centroid decomposition. Checked." Reading is not knowing. The real check: "I've solved 5 problems requiring centroid decomposition, getting AC on each within 90 minutes using my own implementation."
How to Use This Ladder
The unified protocol per problem:
- Budget 60-90 minutes. 1700-rated → 60 min; 1800 → 75 min; 1900+ → 90 min.
- Attempt. Note the structures the problem reminds you of and your initial hypothesis (one sentence).
- At the timer, write down what you tried and what failed. This is the failed-attempt log — the artifact, not just an exercise. Keep it.
- Reveal a minimal editorial sketch only (first two sentences). Try again for 15-30 minutes.
- Read the full editorial. Implement from scratch — no template paste.
- Compare against the top 5 fastest accepted solutions for idioms you don't yet have.
- Upsolve contest problems alongside this ladder for maximum growth. Aim for >= 35/50 — the last 10-15 problems are deliberately hard stretches.
A miniature failed-attempt log looks like this:
Problem: Empty String (CF 1731E)
Hypothesis 1 (12 min): "Pair palindromic chars greedily, count permutations."
Failed because: greedy pairing loses cases where two valid pairings differ in which pairs come first.
Hypothesis 2 (28 min): "Interval DP over which characters can be matched first."
Stuck on: how to count *orderings* of removals, not just whether a removal is possible.
Editorial sketch revealed: dp[l][r] counts orderings; multinomial coefficient combines independent intervals.
Re-attempt (40 min): coded interval DP + multinomial; AC.
Lesson: when the question is "how many orderings," DP returns counts, and orderings combine via multinomials.That log is the source of growth. The AC is just confirmation.
Self-Test: Meta-Skills Checkpoint
At this level, there's no clean "next ladder." Verify these to confirm you're through the structured phase:
- [ ] I can identify the correct technique for most 1800-rated problems within the first 15 minutes
- [ ] I have full implementation experience (not just reading) for: CHT/Li Chao, centroid decomp, HLD, Mo's, CDQ, at least one suffix structure
- [ ] My virtual contest performance: consistently reaching D in Div 2, occasionally E
- [ ] I have a specific diagnosis of what limits my ceiling -- not "I need to study more"
- [ ] I have upsolving notes for at least 20 problems with explicit pattern-trigger extraction
- [ ] I've read at least 30 editorial solutions and extracted the "key observation" from each
- [ ] I see recurring structural patterns in 1900-2000 rated problems across different topics
Expected Rating Progression
2100 | *--->
| *--/
2000 | *--/
| *--/
1900 | *---/
| *--/
1850 | *---/
| *--/
1800 | *---/
| *-/
1700 +*
+----+----+----+----+----+----+----+----+---->
0 5 10 15 20 25 30 35 40+
Problems Solved / Attempted
* = expected progress ---> = self-directed phase
Growth slows. That is normal. Depth > breadth here.
After ~35 problems, the ladder becomes self-directed:
identify your ceiling, practice at it, analyze, iterate.The headline lesson
2100 is combining known techniques in unknown ways.
At this band, problems rarely require a technique you've never seen. They require decomposing a hard problem into two or three standard subproblems and connecting them — segment tree under a binary search, DP optimized by CHT, SOS-DP layered onto a DAG counting problem. The classical failure mode is recognizing the DP formulation, finding it's O(n^3), and spending 35 minutes optimizing the wrong dimension. The trick was usually a transform you already knew, just not in this context.
The diagnostic question, every time you're stuck: "What standard subproblem does this reduce to once I fix the right state?"