Technique Layering: When One Technique Isn't Enough

Quick Revisit

• USE WHEN: single algorithm solves part of problem but not all — need two+ techniques composed together
• INVARIANT: decompose into outer structure (search/traversal) and inner structure (query/decision)
• TIME: product of component complexities | SPACE: sum of component spaces
• CLASSIC BUG: applying techniques in wrong order — outer technique must "call" the inner one, not vice versa
• PRACTICE: 08-ladder-mixed

Most Codeforces 1800+ problems aren't about a single algorithm. They're about recognizing that the problem decomposes into two or three known techniques stacked together. The skill isn't knowing segment trees or binary search -- it's seeing that you need a segment tree inside a binary search.

Difficulty: [Advanced]CF Rating Range: 1800-2400 Prerequisites: Problem Pattern Recognition, familiarity with techniques from Chapters 1-9

Contents

• Why Problems Layer Techniques
• The Combination Catalog
• How to Spot a Layered Problem
• Worked Example: BFS on a Product Graph
• Worked Example: Euler Tour + BIT
• Practice Problems

---

Why Problems Layer Techniques

A 1400-rated problem says: "Find the shortest path." You run BFS. Done.

An 1800-rated problem says: "Find the shortest path, but you have $k$ keys to collect and doors only open with the right key." Now BFS alone isn't enough -- you need BFS on a state graph where each state is (position, key bitmask). That's BFS + DP (bitmask).

The jump from 1400 to 1800 is rarely about knowing a harder algorithm. It's about combining two algorithms you already know. Here's a systematic catalog.

The combination catalog

For each combination, name four things: the outer layer (the loop or search structure), the inner layer (the per-step engine), the state passed between them, and the total complexity they yield together.

#	Combination	Outer	Inner	State passed	Total	Aha moment
1	BFS / Dijkstra + bitmask DP	BFS over an expanded state graph	edge relaxation	(node, mask)	$O((V\cdot 2^k)+(E\cdot 2^k))$	"I need to revisit nodes" → more dimensions in the state
2	Binary search + greedy/DP feasibility	binary search on the numeric answer	greedy or DP feasibility check	candidate answer $M$	$O(\log A\cdot \text{check})$	"Minimize the max / maximize the min" → "is $M$ achievable?"
3	DSU + sorted-edge greedy	sweep edges in sorted order	DSU unite / find	current component partition	$O(E\log E+E\alpha (n))$	"merge components in cost order" → Kruskal pattern (and its cousins)
4	Monotonic stack + DP / direct formula	one pass with the stack	the formula evaluated at each pop	left/right boundary of each element	$O(n)$	"I need boundaries defined by ordering" → monotonic stack
5	Monotonic stack + sparse table	stack gives a range $[L,R]$ for each element	$O(1)$ RMQ inside that range	the range itself	$O(n\log n)$ preprocess, $O(n)$ queries	"stack gives ranges, but I need aggregate info inside"
6	Trie + XOR	one query per number	walk binary trie MSB→LSB	partial XOR prefix	$O(n\log V)$	"XOR is bit-independent" → process bits in a trie
7	Euler tour + BIT / segment tree	DFS to flatten tree	1D point-update / range-sum on flattened array	half-open range [tin[v], tout[v])	$O((n+q)\log n)$	"subtree operation" → flatten, then use a 1D structure
8	Heavy-light decomposition + segment tree	path decomposition	segment tree per chain	chain index + chain offset	$O((n+q){\log }^{2}n)$	"path query/update on a tree" → cut into $O(\log n)$ chains
9	Mo's algorithm + frequency counter	sorted query order	add/remove pointers around window	left, right, current answer	$O((n+q)\sqrt{n})$	"offline range queries with no clean structure"

Every entry follows the same shape: the outer layer iterates / searches; the inner layer answers a fast question; state flows from outer to inner.

When recognizing the layering lets you collapse it

The most interesting cases are the ones where, after you spot the layering, you realize the two layers can be fused into one.

• Binary search + segment-tree query → walk the segment tree. "Find the smallest prefix index where $\text{sum}\ge X$" looks like $O({\log }^{2}n)$ per query: binary search the index, query the segment tree at each step. But the segment tree already encodes the search structure. Walk it directly — at each node, descend into the left child if its sum already reaches $X$, otherwise subtract and go right. One $\log n$ instead of two. Same idea: "$k$-th 1 in a 0/1 array", "first index with value $\ge X$".

• Two pointers + prefix sums → a single pass. A naive layering tracks a window with two pointers and queries a prefix-sum array inside the loop. When the window invariant is monotone, the prefix sum reduces to a running total maintained alongside the pointers — no array needed.

• Sort + binary-search-the-answer → greedy on sorted input. A common 1800–2100 trap: binary searching the answer when sorting plus a single greedy pass already settles it. Always pause and ask: if I sort, does the answer become a one-pass scan?

The lesson: layering is a hypothesis. Implement the obvious two-layer solution mentally, then look for a fusion before you actually code.

How to Spot a Layered Problem

Three signals that a problem needs more than one technique:

1. Multiple constraints. "Shortest path" (BFS) + "with at most $k$ stops" (state DP). Two constraints often mean two techniques.

2. Preprocessing step implied. The problem's inner loop is expensive, but a different structure (sorted order, tree flattening, sparse table) makes each iteration cheap. If you think "if only I could answer X in $O(1)$..." -- that's the second layer.

3. "For each X, compute Y." The phrase "for each node / for each query / for each element" suggests the outer structure, while "compute Y" suggests the inner technique. Example: "for each node, find the sum of values in its subtree" -> Euler tour (outer) + BIT (inner).

Worked Example: BFS on a Product Graph

Problem: Given an $n\times m$ grid with $k\le 6$ keys (labeled a-f) and corresponding locked doors (labeled A-F), find the shortest path from start to goal.

#include <bits/stdc++.h>
using namespace std;

int bfs_keys(vector<string>& grid, int n, int m) {
    // State: (row, col, keys_bitmask)
    int full = 0;
    int sr, sc;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '@') sr = i, sc = j;
            if (grid[i][j] >= 'a' && grid[i][j] <= 'f')
                full |= 1 << (grid[i][j] - 'a');
        }

    // dist[r][c][mask] = shortest distance
    vector dist(n, vector(m, vector<int>(1 << 6, INT_MAX)));
    queue<tuple<int,int,int>> q;
    dist[sr][sc][0] = 0;
    q.push({sr, sc, 0});
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

    while (!q.empty()) {
        auto [r, c, mask] = q.front(); q.pop();
        if (mask == full) return dist[r][c][mask];
        for (int d = 0; d < 4; d++) {
            int nr = r+dx[d], nc = c+dy[d];
            if (nr<0||nr>=n||nc<0||nc>=m||grid[nr][nc]=='#') continue;
            char ch = grid[nr][nc];
            if (ch>='A' && ch<='F' && !(mask & (1<<(ch-'A')))) continue;
            int nmask = mask;
            if (ch>='a' && ch<='f') nmask |= 1<<(ch-'a');
            if (dist[nr][nc][nmask] > dist[r][c][mask]+1) {
                dist[nr][nc][nmask] = dist[r][c][mask]+1;
                q.push({nr, nc, nmask});
            }
        }
    }
    return -1;
}

Two techniques: BFS (shortest path on unweighted graph) + bitmask DP (tracking which keys are held). Neither alone solves the problem.

Worked Example: Euler Tour + BIT

Problem: Rooted tree, support "add $x$ to node $v$" and "query sum of subtree of $v$."

#include <bits/stdc++.h>
using namespace std;

int timer = 0;
vector<int> tin, tout;
vector<vector<int>> adj;
int bit[200005];
int n;

void dfs(int v, int p) {
    tin[v] = ++timer;
    for (int u : adj[v]) if (u != p) dfs(u, v);
    tout[v] = timer;
}

void update(int i, int delta) {
    for (; i <= n; i += i & (-i)) bit[i] += delta;
}

int query(int i) {
    int s = 0;
    for (; i > 0; i -= i & (-i)) s += bit[i];
    return s;
}

// Add x to node v:       update(tin[v], x)
// Query subtree sum of v: query(tout[v]) - query(tin[v] - 1)

Euler tour maps subtrees to contiguous ranges; BIT answers range-sum queries. The combination turns a tree problem into an array problem.

Practice Problems

Problem	Techniques	CF Rating
CF 877D - Olya and Energy Drinks	BFS + Deque (0-1 BFS variant)	2100
CF 1354D - Multiset	Segment Tree + Binary Search (walk on tree)	1900
CF 1095F - Make It Connected	DSU + Greedy (Kruskal-style)	1900
CF 1760G - SlavicG's Favorite Problem	BFS + XOR state	1900
CF 1700E - Serega and Segment Tree	Segment Tree + analysis	2300
CF 706D - Vasiliy's Multiset	Trie + XOR	1800
CF 838B - Diverging Directions	Euler Tour + Segment Tree	2200
CF 1555E - Boring Segments	Binary Search + Segment Tree	2200

---