When One Technique Isn't Enough

You are here: Ch 4 (Dynamic Programming) --> Advanced Chapters (Ch 5-10) | Core Path

What You've Learned

You've now mastered the core toolkit: techniques (Ch 1), data structures (Ch 2), graphs (Ch 3), and DP (Ch 4). From 1D recurrences to bitmask DP, from knapsack to tree DP, you can define states, write transitions, and trust the recurrence.

You can solve most CF problems rated 1000-1700. But look at the leaderboard -- the 1800+ problems don't use one technique. They use two or three, woven together.

This is the wall. And it's not a knowledge wall -- it's a recognition wall.

Four Problems That Break Single Techniques

1. Shortest Path With State

The problem: Find the shortest path from A to B, but you have a "fuel" resource that refills at certain nodes and limits how far you can travel in one stretch.

Why Dijkstra alone fails: Plain Dijkstra tracks dist[node], but here two arrivals at the same node with different fuel levels lead to different futures. The node alone doesn't capture enough state.

Why DP alone fails: The graph has cycles. You can't define a clean DAG ordering for recurrence.

The combination: Build a layered graph where each state is (node, fuel_level) and run Dijkstra on this expanded graph. Dijkstra provides the shortest-path machinery; DP-style state expansion provides the memory of past decisions.

-> Chapter 6: Advanced Graphs -- layered graphs, Dijkstra on states, 0-1 BFS variants.

2. Count Distinct Substrings

The problem: Given a string of length 200,000, count the number of distinct substrings.

Why brute force fails: There are O(n^2) substrings. Hashing them all takes O(n^2) time and memory -- too slow for n = 200k.

Why a set alone fails: Even with a hash set, inserting 2*10^10 substrings is orders of magnitude too slow.

The combination: Build a suffix array with its LCP array in O(n log n). The total number of distinct substrings is n(n+1)/2 minus the sum of the LCP array. A string structure provides the organization; the data structure query provides the count.

-> Chapter 5: Strings -- suffix arrays, LCP arrays, suffix automata.

3. Range DP, But O(n^2) Is Too Slow

The problem: You have n items on a line. Merging adjacent items has a cost that depends on their values. Minimize total cost. Classic interval DP -- but n = 500,000.

Why standard interval DP fails: The classic O(n^3) recurrence (or even O(n^2) with Knuth optimization) can't handle n above ~5,000.

Why greedy fails: Locally cheapest merges don't produce globally optimal costs. The dependencies between merge decisions are too tangled.

The combination: Reformulate the DP transition as adding lines to a set and querying for the minimum. The Convex Hull Trick turns O(n^2) DP into O(n log n) by maintaining a convex hull of linear functions. DP defines the problem structure; a geometric data structure accelerates the transitions.

-> Chapter 4 Advanced (Convex Hull Trick, D&C Optimization) + Chapter 2 (data structures for hull maintenance).

4. Range Queries With Updates -- But Offline

The problem: You receive 300,000 queries on an array: some are range sum queries, some are point updates. But you're allowed to process them in any order.

Why segment tree alone fails: A persistent segment tree handles this online, but with large constant factors and complex implementation. Under tight time limits, it might TLE -- and the code is fragile.

Why brute force fails: Processing each query in O(n) gives O(nq) = 910^10 operations.

The combination: Mo's algorithm reorders queries into blocks of size sqrt(n), so consecutive queries differ by at most sqrt(n) elements. A lightweight data structure (a BIT or even a plain array with rollback) handles the local updates within each block. Offline ordering provides the query structure; a simple DS provides efficient local computation.

-> Chapter 9: Offline Techniques -- Mo's algorithm, sqrt decomposition, CDQ divide and conquer.

The Pattern

Notice what happened in every example:

Problem Shape	Technique A	Technique B	Why Neither Works Alone
Shortest path + resource	Dijkstra	DP state	Cycles kill DP; state kills Dijkstra
Count distinct substrings	Suffix array	LCP query	Brute force too slow; sets too slow
DP with large n	DP recurrence	Convex hull	O(n^3) too slow; greedy is wrong
Offline range queries	Mo's ordering	BIT / array	Segment tree too heavy; brute force too slow

1800+ problems live at the intersection of techniques. That's why the advanced chapters exist.

Before You Move On

Can you confidently:

[ ] Define DP states and transitions for a new problem from scratch?
[ ] Implement knapsack, LCS, and interval DP without looking up the recurrence?
[ ] Use bitmask DP for subset-based problems with n <= 20?
[ ] Write tree DP by rooting an arbitrary tree and processing children?
[ ] Recognize whether a problem needs DP, greedy, or graph search?
[ ] Combine a data structure with a technique (e.g., priority queue + greedy)?

If not, revisit Chapter 4. The advanced chapters assume you're fluent with all core techniques.

Choose Your Path

Not all advanced chapters are equal for your goals. Pick based on what you want next:

                         +-- String problems keep beating you?
                         |   -> Ch 5: Strings (hashing, KMP, suffix arrays)
                         |
                         +-- Graphs with extra constraints?
                         |   -> Ch 6: Advanced Graphs (flows, LCA, bridges, SCC)
                         |
                         +-- "Use math" in editorial frustrates you?
 You finished Ch 0-4 ---+   -> Ch 7: Mathematics (NT, combinatorics, FFT)
                         |
                         +-- Geometry problems are free rating?
                         |   -> Ch 8: Geometry (convex hull, half-planes)
                         |
                         +-- Offline tricks + sqrt magic?
                         |   -> Ch 9: Offline Techniques (Mo's, CDQ, sweep)
                         |
                         +-- Want a playbook of reusable patterns?
                             -> Ch 10: Patterns & Recipes (rerooting, small-to-large)

There's no wrong order among Ch 5-10. They're largely independent -- pick whichever solves the problems you're currently failing.

The Real Skill

The jump from 1700 to 2100 isn't about learning more algorithms. It's about learning to see which algorithms a problem needs, and how they fit together.

Every 2100-rated problem is, at its core, a 1400-rated problem wearing a disguise. The disguise is a combination of two techniques, an unusual constraint, or a transformation that makes the standard approach break. Your job is to strip the disguise.

The Decision Engine and Trigger Phrases help with recognition. The advanced chapters give you the combinations. Practice welds them into instinct.

Advanced Chapter Quick Links

Chapter	README
Ch 5: Strings	05-strings/README.md
Ch 6: Advanced Graphs	06-graph-advanced/README.md
Ch 7: Mathematics	07-mathematics/README.md
Ch 8: Geometry	08-geometry/README.md
Ch 9: Offline Techniques	09-offline-techniques/README.md
Ch 10: Patterns & Recipes	10-patterns-and-recipes/README.md

Practice: Ladder: 1700-2100 | Ladder: Mixed

When One Technique Isn't Enough ​

What You've Learned ​

Four Problems That Break Single Techniques ​

1. Shortest Path With State ​

2. Count Distinct Substrings ​

3. Range DP, But O(n^2) Is Too Slow ​

4. Range Queries With Updates -- But Offline ​

The Pattern ​

Before You Move On ​

Choose Your Path ​

The Real Skill ​

Advanced Chapter Quick Links ​

You know the moves. Time to learn the combinations. ​