Practice Ladder: CF 1400 --> 1700

50 curated problems to build intermediate competitive-programming skills. Prerequisites: comfortable with the topics in the 1100 --> 1400 ladder.

Quick Revisit

• SKILL FOCUS: intermediate techniques -- segment tree, DP on sequences, graphs, number theory
• DIFFICULTY: 1200--2200
• PROBLEMS: 50
• PREREQUISITE: Ladder 1100-1400

Headline warning for this band: templates mask technique gaps. You know it's a segment tree problem. You paste your template. You get WA because the merge function is wrong for this problem's semantics. That is not a coding bug — it's not understanding what the template implements. At 1400-1700, "I have a template" and "I understand the technique" are different skills, and most plateaus live in that gap. Before submitting, ask: can I re-derive the merge / transition / invariant from scratch? If not, your template is a black box, and the next problem will catch you.

---

Contents

• Segment Tree / BIT
• DP on Sequences (LCS, LIS, Knapsack)
• Graph: Dijkstra, Bellman-Ford
• Graph: MST, Topological Sort
• Number Theory (Modular Inverse, Sieve Applications)
• Combinatorics (nCr, Counting)
• DSU (Disjoint Set Union)
• Binary Search on Answer
• Bitmask DP
• String Basics (Hashing, KMP)
• Divide and Conquer
• Contribution Technique
• Mental Traps
• What the Code Won't Teach You
• How to Use This Ladder
• Self-Test: Meta-Skills Checkpoint

 Topic Distribution Across the Ladder

 Segtree / BIT |############ 6
 DP Sequences |############ 6
 Graph: Shortest |######## 4
 Graph: MST/Topo |######## 4
 Number Theory |########## 5
 Combinatorics |######## 4
 DSU |######## 4
 BS on Answer |######## 4
 Bitmask DP |###### 3
 Strings (KMP) |######## 4
 Divide+Conquer |###### 3
 Contribution |###### 3
 +--+--+--+--+--+--+--->
 0 1 2 3 4 5 6

 ^ Segtree and DP are heaviest -- they appear everywhere at 1700+.

---

Segment Tree / BIT

#	Problem	Rating	Tags	Hint
1	Dynamic Range Sum Queries (CSES)	--	segtree, BIT	Point update + range query -- textbook BIT or segment tree.
2	Dynamic Range Minimum Queries (CSES)	--	segtree	Same as range-sum but store min in each node.
3	Range Update Queries (CSES)	--	BIT, diff	Range add + point query -- use a BIT over a difference array.
4	Static Range Minimum Queries (CSES)	--	sparse table	Build a sparse table for O(1) range-min queries after O(n log n) preprocessing.
5	Distinct Values Queries (CSES)	--	offline, BIT	Sort queries by right endpoint; use a BIT to track last occurrence of each value.
6	Inversion Count	--	BIT, merge sort	Count inversions using a BIT: process elements from left to right, query elements already placed that are larger.

DP on Sequences (LCS, LIS, Knapsack)

#	Problem	Rating	Tags	Hint
7	Edit Distance (CSES)	--	dp, string	Classic 2D DP: dp[i][j] = min ops to match first i chars of s with first j of t.
8	Money Sums (CSES)	--	dp, knapsack	0/1 knapsack over coin values; track which sums are reachable.
9	Two Sets II (CSES)	--	dp, knapsack	Count subsets summing to total/2; divide by 2 for symmetry.
10	Increasing Subsequence (CSES)	--	dp, binary search	Patience-sorting / binary-search approach for O(n log n) LIS.
11	Flowers	1700	dp	Let dp[n] = ways to tile length n with blocks of size 1 (white) or k (red); use prefix sums for range answers.
12	Pillars	1900	dp, segtree	LIS-variant with absolute difference >= d; use a segment tree to speed up transitions.

Graph: Dijkstra, Bellman-Ford

#	Problem	Rating	Tags	Hint
13	Shortest Routes I (CSES)	--	dijkstra	Standard Dijkstra from node 1; use a priority queue with (dist, node).
14	Shortest Routes II (CSES)	--	floyd-warshall	Floyd-Warshall for all-pairs shortest paths on small n.
15	Flight Discount (CSES)	--	dijkstra, layered	Run Dijkstra on a two-layer graph: one layer before using the coupon, one after.
16	Cycle Finding (CSES)	--	bellman-ford	Run Bellman-Ford for n rounds; if the n-th round still relaxes, a negative cycle exists -- trace it back.

Graph: MST, Topological Sort

#	Problem	Rating	Tags	Hint
17	Road Reparation (CSES)	--	MST, kruskal	Sort edges by weight, union-find to build the MST; check connectivity.
18	Course Schedule (CSES)	--	topo sort	Kahn's algorithm (BFS with in-degree) to produce a valid ordering.
19	Longest Flight Route (CSES)	--	topo sort, dp	Topological sort + DP to find the longest path in a DAG.
20	Game Routes (CSES)	--	topo sort, dp	Count paths from 1 to n in a DAG using topological order and DP.

Number Theory (Modular Inverse, Sieve Applications)

#	Problem	Rating	Tags	Hint
21	Exponentiation II (CSES)	--	math, mod	Use Fermat's little theorem: a^(p-1) === 1 (mod p), so reduce the exponent mod p-1 first.
22	Sum of Divisors (CSES)	--	math, harmonic	Each d contributes d x floor(n/d); group by blocks where floor(n/d) is constant.
23	Noldbach Problem	1000	sieve, math	Sieve primes up to n; for each prime p <= n check if p = q + r + 1 for primes q, r.
24	Divisor Analysis (CSES)	--	math	From the prime factorisation, derive count, sum, and product of divisors using standard formulas.
25	Binomial Coefficients (CSES)	--	math, mod inverse	Precompute factorials and inverse factorials mod 10^9+7.

Combinatorics (nCr, Counting)

#	Problem	Rating	Tags	Hint
26	Bracket Sequences I (CSES)	--	combinatorics, catalan	The answer is the n-th Catalan number: C(2n, n) / (n+1).
27	Distributing Apples (CSES)	--	combinatorics	Stars and bars: C(n + m - 1, m - 1).
28	Christmas Party (CSES)	--	combinatorics, derangements	Count derangements with the inclusion-exclusion formula: D(n) = (n-1)(D(n-1) + D(n-2)).
29	Grid Paths (CSES)	--	combinatorics	Paths in a grid from (1,1) to (n,n) avoiding traps -- inclusion-exclusion over blocked cells.

DSU (Disjoint Set Union)

#	Problem	Rating	Tags	Hint
30	Road Construction (CSES)	--	DSU	Maintain component count and max component size with union-find.
31	New Roads Queries (CSES)	--	DSU, offline	Process edges in order; for each query binary-search on the time two nodes first became connected.
32	Ice Skating	1200	DSU	Each drift connects points sharing an x or y coordinate -- count connected components.
33	Cthulhu	1500	DSU, graph	The graph is "Cthulhu" iff it is connected and has exactly one cycle (n edges, n nodes).

Binary Search on Answer

#	Problem	Rating	Tags	Hint
34	Factory Machines (CSES)	--	binary search	Binary search on time T; check if total products made in T >= target.
35	Array Division (CSES)	--	binary search	Binary search on the maximum subarray sum; greedily partition to verify.
36	Multiplication Table	1800	binary search	Binary search on value v; count entries <= v in the nxn multiplication table row by row.
37	Aggressive Cows (SPOJ AGGRCOW)	--	binary search, greedy	Binary search on minimum distance; greedily place cows to check feasibility.

Bitmask DP

#	Problem	Rating	Tags	Hint
38	Hamiltonian Flights (CSES)	--	bitmask dp	dp[mask][v] = ways to reach v having visited exactly the nodes in mask.
39	Elevator Rides (CSES)	--	bitmask dp	dp[mask] = (rides, remaining capacity) for the best partition of people in mask.
40	SOS DP (CSES: Bit Problem)	--	bitmask, SOS	Sum-over-subsets: iterate over bits, include/exclude each dimension.

String Basics (Hashing, KMP)

#	Problem	Rating	Tags	Hint
41	String Matching (CSES)	--	KMP, hashing	KMP failure function or polynomial hashing to count occurrences.
42	Finding Borders (CSES)	--	KMP	Use the KMP failure function: chase fail[n-1] to list all border lengths.
43	Finding Periods (CSES)	--	KMP	Period p exists iff the string has a border of length n - p; enumerate via fail array.
44	Password (CSES)	--	KMP	The longest proper border (from fail array) is the longest prefix that is also a suffix.

Divide and Conquer

#	Problem	Rating	Tags	Hint
45	Merge Sort Inversions (CSES)	--	merge sort, D&C	Count inversions during the merge step of merge sort.
46	Towers (CSES)	--	greedy, multiset	Greedily place each block on the tower with the smallest top > block (use a multiset).
47	K-th Smallest in Segments	2200	D&C, merge sort tree	Build a merge-sort tree; count elements <= mid in a range to binary-search for the k-th element.

Contribution Technique

#	Problem	Rating	Tags	Hint
48	Imbalanced Array (CF 817D)	1900	contribution, stack	Sum of (max - min) over all subarrays. For each element, count the subarrays where it is the max (and where it is the min) using monotone stacks; sum the contributions.
49	Sum of Subarray Minimums (LeetCode 907)	--	contribution, stack	For each element, find how many subarrays it is the minimum of using a monotone stack; multiply by the value.
50	Pashmak and Parmida's Problem (CF 459D)	1900	contribution, BIT	Reduce to counting pairs (i, j) where freq-prefix(i) > freq-suffix(j); BIT over frequencies.

---

Mental Traps

Drawn from the companion reflection.

"I need to know more algorithms before I can go higher." At 1400-1700, the bottleneck is almost never knowing more algorithms. It's one of: (1) you don't recognize when to apply algorithms you already know, (2) you can't model the problem correctly before applying the algorithm, (3) your implementations have bugs under pressure. None of these are fixed by learning new algorithms. They're fixed by solving more problems at your ceiling, analyzing every WA, and building pattern-recognition through productive struggle.

Recognizing the technique from the editorial but not from the problem. The editorial says "binary search the answer." You read it and think "oh, obviously." But during the solve you had no idea. This is the recognition gap. To close it: before reading the editorial, write down "what property of this problem would have led me to binary search?" Then verify against the editorial. Build the trigger explicitly.

Template reliance masking technique gaps. You know it's a segment tree problem. You paste your template. You get WA because the merge function is wrong for this problem's semantics. This means you understand templates but not the techniques they implement. Go back and understand each template line by line.

Avoiding hard problems within the ladder. "I'll come back to this 1650-rated problem after I do more 1500-rated ones." Three months later, you've dodged all the 1600+ problems. Avoidance of difficult problems within your target range is avoidance of the growth mechanism itself.

 How 1400-1700 Topics Build on 1100-1400

 1700 +---------+----------+---------+--------+
 | Bitmask | Lazy | SOS DP | Suffix |
 | DP | Segtree | | Array |
 1600 +----+----+----+-----+----+----+--------+
 | | | |
 v v v v
 1500 +----+----+----+-----+----+----+--------+
 | Basic | Segtree | Dijkstra| KMP / |
 | DP ext | / BIT | / BF | Hash |
 1400 +----+----+----+-----+----+----+--------+
 | ^ ^ ^
 | | | |
 + Knapsack Prefix BFS/DFS
 + Coin DP Sums Basics
 +----------+-----------+---------+------>
 (1100-1400 prerequisite layer)

 ^ Each technique extends what you learned before.
 Gaps in the bottom layer cause collapse above.

What the Code Won't Teach You

Practice the full pipeline, not just the algorithm. For each problem: (1) identify the mathematical structure, (2) determine the technique, (3) implement correctly, (4) test edge cases, (5) submit. At 1100-1400, step 2 was the hard part. Here, step 1 -- modeling the problem -- becomes equally critical. Write down your problem model before coding.

Study in thematic blocks. Spend a week on "segment tree problems 1500-1700," then a week on graph problems, then DP. Thematic blocks build pattern recognition faster than random order. The repetition within a theme teaches you to spot the triggering conditions for each technique.

Extract the lesson from every WA. The most valuable learning comes from wrong answers. For each WA: what was wrong -- algorithm, model, or implementation? What would have caught the bug faster? This analysis outweighs moving to the next problem.

Differentiate modeling errors from technique errors. Your solution is wrong. Is it because you applied the wrong technique, or the right technique to the wrong model? Technique error --> study the technique. Modeling error --> practice problem abstraction (read, strip the story, find the math structure).

Don't grind the same rating band. 70% of practice should be at or above your current rating; 30% at or below for speed and fluency. If you're doing 100% at or below, you're comfort-practicing.

---

How to Use This Ladder

1. Attempt each problem for 45-60 minutes before looking at hints.
2. After each section, identify your weakest topic and supplement with 3-5 extra problems from that tag.
3. Implement cleanly -- practice writing modular code with helper functions.
4. Aim for >= 40/50 solves before moving to the 1700 --> 2100 ladder.
5. Re-solve any problem you needed the editorial for after a 1-week gap.

Self-Test: Meta-Skills Checkpoint

Before advancing to the 1700 --> 2100 ladder, honestly verify these meta-skills:

• [ ] I can solve 1500-rated problems consistently in under 40 minutes with a single submission
• [ ] I can correctly implement from memory: lazy segment tree, Dijkstra, tree DP, binary search on answer
• [ ] I have upsolving notes on at least 15 problems with explicit pattern-trigger extraction
• [ ] My virtual contest performance: regularly solving A, B, C and occasionally D (Div 2)
• [ ] I have attempted at least 5 problems rated 1650-1700, regardless of outcome
• [ ] I can distinguish modeling errors from technique errors in my own wrong submissions
• [ ] I keep a problem journal and review it at least weekly

 Expected Rating Progression

 1700 | *------->
 | *--/
 1650 | *--/
 | *--/
 1600 | *--/
 | *-/
 1550 | *---/
 | *--/
 1500 | *--/
 | /
 1400 +*
 +----+----+----+----+----+----+----+----+---->
 0 5 10 15 20 25 30 35 40
 Problems Solved

 * = expected progress -------> = ready for next ladder
 The plateau around ~1550 is real. Everyone hits it.
 Push through with thematic deep-dives, not random grinding.

---

The headline lesson

1700 is where "what algorithm?" becomes "what's the model?"

The jump from 1400 to 1700 is about problem modeling. Translating the story into the right algorithmic framework — graph, DP, greedy, contribution — is the actual skill being trained. The trap looks like this: problem D says "arrange objects to minimize cost." You try greedy for 25 minutes and get WA. It was interval DP all along, and "arrange" should have been the trigger. At this band, pattern recognition is the bottleneck, not algorithm knowledge.

Three diagnostic questions to ask before coding any problem in this ladder:

1. If the problem doesn't look like a standard algorithm, what hidden structure (graph, DP graph, lattice, multiset) does the story describe?
2. If N <= 2000, am I targeting O(n^2) DP or pushing for O(n log n)? The constraint is a hint about the intended model.
3. If I'm caught between greedy and DP, can I exhibit a counterexample to greedy in two minutes? If not, greedy probably isn't safe.

---

Previous: 1100-1400 | Next: 1700-2100 | Topic drills: DP Ladder, DS Ladder | Contest practice: Mock Contest 2