Sweep and Invariants
Greedy from Structure
Here's something that takes a while to click: some problems don't need sorting, exchange arguments, or any proof machinery at all. The greedy answer falls directly out of the structure of the input — difference arrays, parity constraints, modular invariants, digit decompositions. The trick is seeing the structure, and once you do, the solution is usually a few lines of code.
This lesson covers six problems that share this DNA. The first two — Grand Garden and Make Them Even — deserve the deepest treatment because the techniques (difference arrays and parity sweeps) appear constantly in competitive programming.
Example 1: ABC116C — Grand Garden
Problem. A garden has \(n\) flowers, all starting at height 0. The target heights are \(h_1, h_2, \ldots, h_n\). One operation: choose a contiguous range \([l, r]\) and increase every flower in that range by 1. Find the minimum number of operations.
The Greedy Choice: Count the rising edges. Each position where the height increases from the previous one requires a new operation — falling edges are free.
The Wrong Approach
Your first instinct might be: "Which flowers need the most watering? Water those first, covering as much ground as possible." This leads you toward interval scheduling — figuring out which ranges to water in which order. You'll burn 20 minutes building something complicated for a 300-point problem.
Instead of asking "which intervals should I water?", ask: "what does each operation look like in the difference array?"
The Difference Array Insight
Define the difference array \(d[i] = h[i] - h[i-1]\), where we set \(h[-1] = 0\) (ground level).
Each operation "add 1 to range \([l, r]\)" does exactly two things in the difference array:
- \(d[l]\) increases by 1 (the height rises at position \(l\))
- \(d[r+1]\) decreases by 1 (the height drops back after position \(r\))
So every operation creates exactly one positive unit in \(d\) and one negative unit. The minimum number of operations is the total number of positive units we need to create — the sum of all positive values in \(d\).
Formula:
where \(d[0] = h[0]\) and \(d[i] = h[i] - h[i-1]\) for \(i \geq 1\).
Since \(d[0] = h[0] - 0 = h[0]\) is always non-negative, this simplifies to:
Step-by-Step Trace
Stare at this table. Take \(h = [3, 5, 2, 4, 1]\).
First, compute the difference array:
| \(i\) | \(h[i]\) | \(h[i-1]\) | \(d[i] = h[i] - h[i-1]\) | \(\max(0, d[i])\) |
|---|---|---|---|---|
| 0 | 3 | 0 | 3 | 3 |
| 1 | 5 | 3 | 2 | 2 |
| 2 | 2 | 5 | -3 | 0 |
| 3 | 4 | 2 | 2 | 2 |
| 4 | 1 | 4 | -3 | 0 |
Answer \(= 3 + 2 + 0 + 2 + 0 =\) 7 operations.
Manual verification. Here are 7 operations that achieve \([3, 5, 2, 4, 1]\):
| Operation | Range | Heights after |
|---|---|---|
| 1 | \([0,3]\) | [1,1,1,1,0] |
| 2 | \([0,3]\) | [2,2,2,2,0] |
| 3 | \([0,1]\) | [3,3,2,2,0] |
| 4 | \([1,3]\) | [3,4,3,3,0] |
| 5 | \([1,3]\) | [3,5,4,4,0] |
| 6 | \([3,3]\) | [3,5,4,5,0] |
| 7 | \([4,4]\) | [3,5,2,4,1] |
The exact construction isn't the point — what matters is that 7 is the minimum. Every "rising edge" in the height profile forces a new operation to start, while "falling edges" are free (existing operations just stop earlier).
Visual intuition. Imagine the heights as a skyline drawn on graph paper. Each operation is a horizontal bar of thickness 1. You're stacking bars to fill the skyline.
(Heights: \(h = [3, 5, 2, 4, 1]\). Each # is one unit of height at that position.)
At position 0, you start 3 new bars (rise from 0 to 3). At position 1, you need 2 more (rise from 3 to 5). At position 2, height drops to 2 — no new bars needed (3 bars stop). At position 3, height rises to 4 — 2 new bars start. At position 4, height drops to 1 — 3 bars stop. Total new starts \(= 3 + 2 + 2 = 7\).
What Breaks If You Think "Top Down"
Here's where almost every first implementation breaks. You think: "The tallest flower is 5. Let me water range \([0,4]\) five times, then fix up the differences." That gives you 5 operations just to cover position 1, but you've over-watered positions 2 and 4. Now you need to undo work — but you can't subtract height. You're stuck.
The difference array reframes the question. Instead of asking "which ranges do I water?", you ask "how many times does the profile rise?" That's a one-pass scan.
The Code
int minOperations = flowerHeights[0];
for (int i = 1; i < numFlowers; i++) {
if (flowerHeights[i] > flowerHeights[i - 1]) {
minOperations += flowerHeights[i] - flowerHeights[i - 1];
}
}
cout << minOperations << "\n";
\(O(n)\) time, \(O(1)\) extra space. The difference array doesn't even need to be materialized — we compute it on the fly.
Example 2: ABC109D — Make Them Even
Problem. An \(H \times W\) grid where each cell contains some coins. One operation: move one coin from a cell to an adjacent cell (up/down/left/right). Make every cell's coin count even. Minimize the number of moves and output the sequence of moves.
What Should You Think First?
Before reaching for any algorithm, ask yourself: can this always be done?
Moving a coin between two cells flips both cells' parities. If cell A has an odd count and cell B has an even count, after moving one coin from A to B, A becomes even and B becomes odd.
Key invariant: The total number of odd cells changes by 0 or 2 with each operation. If the total number of coins is odd, at least one cell must remain odd — you cannot make all cells even. If the total is even, all cells can be made even.
Predict before continuing: Given a \(3 \times 3\) grid where the total coin count is 15, what's the minimum number of odd cells in any final configuration?
The Snake Order Trick
Here's the construction that makes this problem elegant. Process cells in snake order: left-to-right on row 0, right-to-left on row 1, left-to-right on row 2, and so on.
This traces a Hamiltonian path through the grid — every cell is visited exactly once, and consecutive cells in the path are always adjacent.
The algorithm: Walk the snake path. When you encounter an odd cell (and it's not the last cell), move one coin to the next cell in the path. This costs exactly 1 operation, makes the current cell even, and changes the next cell's parity.
Why it works. After processing cell \(k\), cells 1 through \(k\) are all even. If moving a coin makes the next cell odd, that's fine — we'll fix it when we reach it. The invariant holds: all processed cells are even.
What about the last cell? If the total coin count is odd, the last cell in the snake path will remain odd — unavoidable. If the total is even, the last cell will also be even (since we've passed an even number of parity flips along the path).
What Breaks If You Don't Use Snake Order?
Suppose you process cells in normal row-major order (left-to-right, top-to-bottom). When you hit an odd cell at the end of a row, the "next" cell in row-major order is the start of the next row — which is not adjacent. You'd need multiple moves to push a coin that far. Snake order guarantees every consecutive pair is adjacent, so every fix costs exactly 1 move.
Trace on a Small Grid
Consider a \(2 \times 3\) grid with coins:
Snake order: (0,0)=3, (0,1)=2, (0,2)=1, (1,2)=2, (1,1)=1, (1,0)=4. Total = 13 (odd), so one cell must remain odd.
| Step | Cell | Coins | Odd? | Action | Coins after |
|---|---|---|---|---|---|
| 1 | (0,0) | 3 | Yes | Move 1 to (0,1) | (0,0)=2, (0,1)=3 |
| 2 | (0,1) | 3 | Yes | Move 1 to (0,2) | (0,1)=2, (0,2)=2 |
| 3 | (0,2) | 2 | No | Skip | — |
| 4 | (1,2) | 2 | No | Skip | — |
| 5 | (1,1) | 1 | Yes | Move 1 to (1,0) | (1,1)=0, (1,0)=5 |
| 6 | (1,0) | 5 | Yes | Last cell, can't fix | — |
Final grid:
Cells (0,0) through (1,1) are all even. Cell (1,0) = 5 is odd — unavoidable since total is 13. We used 3 moves.
Verify it yourself: go back and count the odd cells in the original grid. There were 3 odd cells (3, 1, 1). We fixed 2 of them with 3 moves, and the last one is stuck. Does the parity invariant check out?
The Code
int numRows, numCols;
cin >> numRows >> numCols;
vector<vector<int>> coinGrid(numRows, vector<int>(numCols));
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
cin >> coinGrid[i][j];
}
}
vector<tuple<int, int, int, int>> coinMoves;
for (int i = 0; i < numRows; i++) {
if (i % 2 == 0) {
for (int j = 0; j < numCols - 1; j++) {
if (coinGrid[i][j] % 2 == 1) {
coinGrid[i][j]--;
coinGrid[i][j + 1]++;
coinMoves.push_back({i, j, i, j + 1});
}
}
if (i + 1 < numRows && coinGrid[i][numCols - 1] % 2 == 1) {
coinGrid[i][numCols - 1]--;
coinGrid[i + 1][numCols - 1]++;
coinMoves.push_back({i, numCols - 1, i + 1, numCols - 1});
}
} else {
for (int j = numCols - 1; j > 0; j--) {
if (coinGrid[i][j] % 2 == 1) {
coinGrid[i][j]--;
coinGrid[i][j - 1]++;
coinMoves.push_back({i, j, i, j - 1});
}
}
if (i + 1 < numRows && coinGrid[i][0] % 2 == 1) {
coinGrid[i][0]--;
coinGrid[i + 1][0]++;
coinMoves.push_back({i, 0, i + 1, 0});
}
}
}
\(O(H \times W)\) time, one pass through the grid.
Example 3: ABC173D — Chat in a Circle
Problem. \(N\) players arrive one by one and form a circle. The first player gets 0 comfort. Each subsequent player stands between two existing adjacent players, and their comfort equals the minimum friendliness of those two neighbors. Maximize total comfort.
Structural insight. Sort friendliness values in descending order: \(f[0] \geq f[1] \geq \ldots \geq f[n-1]\). The first player has friendliness \(f[0]\) and gets 0 comfort. Each subsequent player's comfort is determined by the minimum of their two neighbors.
Here's the key observation: each player (once seated) can act as a neighbor for at most two future arrivals (one on their left side, one on their right side). So each friendliness value appears at most twice in the sum of comforts.
Formula. Answer \(= \sum_{i=0}^{n-2} f\left[\lfloor(i+1)/2\rfloor\right]\).
What would happen if you didn't sort? Try \(f = [1, 5, 3]\). Unsorted, the first player with friendliness 1 constrains every future neighbor. Sorted descending \([5, 3, 1]\): player 5 enters first (0 comfort), player 3 sits next to 5 (comfort = 5), player 1 sits between 5 and 3 (comfort \(= \min(5,3) = 3\)). Total = 8. Any other order gives less.
auto descendingCompare = [](int a, int b) {
return a > b;
};
sort(friendliness.begin(), friendliness.end(), descendingCompare);
long long totalComfort = 0;
for (int i = 0; i < numPlayers - 1; i++) {
totalComfort += friendliness[(i + 1) / 2];
}
Example 4: CF515C — Drazil and Factorial
Problem. Given a number a (as a string of digits), find the largest number x (no 0s or 1s among its digits) such that the product of digit factorials of x equals the product of digit factorials of a.
Structural insight. Each digit's factorial can be decomposed into products of smaller digit factorials:
| Digit | Decomposition |
|---|---|
| 0, 1 | Contribute nothing (\(0! = 1! = 1\)) |
| 2 | 2 (prime, irreducible) |
| 3 | 3 (prime, irreducible) |
| 4 | 3, 2, 2 (since \(4! = 24 = 3! \times 2! \times 2!\)) |
| 5 | 5 (prime, irreducible) |
| 6 | 5, 3 (since \(6! = 720 = 5! \times 3!\)) |
| 7 | 7 (prime, irreducible) |
| 8 | 7, 2, 2, 2 (since \(8! = 40320 = 7! \times 2! \times 2! \times 2!\)) |
| 9 | 7, 3, 3, 2 (since \(9! = 362880 = 7! \times 3! \times 3! \times 2!\)) |
Digits 2, 3, 5, 7 are "factorial primes" — they cannot be decomposed further. The solution: decompose every digit of a, collect the resulting digits, sort descending to form the largest possible number.
Try it yourself: What does the digit 8 decompose into? Verify that \(8! = 7! \times 2! \times 2! \times 2! = 5040 \times 2 \times 2 \times 2 = 40320\). Check.
map<char, string> digitDecomposition = {
{'2', "2"}, {'3', "3"}, {'4', "322"}, {'5', "5"},
{'6', "53"}, {'7', "7"}, {'8', "7222"}, {'9', "7332"}
};
string maxNumberResult;
for (char digit : originalNumberStr) {
if (digit >= '2') {
maxNumberResult += digitDecomposition[digit];
}
}
auto charDescendingCompare = [](char a, char b) {
return a > b;
};
sort(maxNumberResult.begin(), maxNumberResult.end(), charDescendingCompare);
Example 5: CF1348A — Phoenix and Balance
Problem. Coins with weights \(2^1, 2^2, \ldots, 2^n\) (\(n\) is even). Split into two piles of exactly \(n/2\) coins each. Minimize \(|\text{sum}_A - \text{sum}_B|\).
Structural insight. The largest coin, \(2^n\), dominates all smaller coins combined: \(2^n > 2^1 + 2^2 + \ldots + 2^{n-1} = 2^n - 2\). Since \(2^n\) must go in one pile, that pile will be heavier no matter what. To minimize the difference, pair \(2^n\) with the smallest \(n/2 - 1\) coins, leaving all the medium coins in the other pile.
Predict before reading the code: If \(n = 6\), which coins go in pile A?
long long pileAWeight = (1LL << numCoins);
long long pileBWeight = 0;
for (int i = 1; i < numCoins / 2; i++) {
pileAWeight += (1LL << i);
}
for (int i = numCoins / 2; i < numCoins; i++) {
pileBWeight += (1LL << i);
}
cout << abs(pileAWeight - pileBWeight) << "\n";
Example 6: ABC416B — 1D Akari
Problem. String of . and #. Place o on . positions to maximize count. Two os must have at least one # between them.
Structural insight. The # characters partition the string into independent segments of consecutive .s. Within each segment, you can place at most one o. The answer is simply the number of maximal runs of .s that contain at least one ..
Recognizing Structural Problems
Here's something that takes a while to click — these problems look hard until you find the right lens. Look for these signals:
- The answer is a simple formula of the input (sum of differences, max frequency, etc.)
- Parity or modular arithmetic constrains the answer
- A natural sweep order exists (grid traversal, left-to-right scan)
- The problem feels hard but constraints suggest \(O(N)\) — that's a hint the answer is structural
- Digit decomposition — factorials or prime factorizations of individual digits
- One element dominates all others — powers of 2, geometric sequences
The Trap: Overcomplicating It
The biggest mistake on structural problems is reaching for heavy machinery. If you find yourself building a segment tree or writing a DP for a problem rated 300-400 points, stop. Step back. Draw the difference array. Check parities. Count rising edges. The \(O(N)\) answer is staring at you.
Try It
Warm-up 1: Grand Garden Variants
Compute the answer for each height array by hand. Predict first, then verify.
A. \(h = [1, 2, 3, 4, 5]\)
Rising edges: \(1 + 1 + 1 + 1 + 1 = 5\). Every position rises by 1 from the previous. Five operations, each extending one position further: \([0,0], [0,1], [0,2], [0,3], [0,4]\).
B. \(h = [5, 4, 3, 2, 1]\)
Rising edges: \(5 + 0 + 0 + 0 + 0 = 5\). Only the first position rises (from 0 to 5). All subsequent positions are falling. Five operations, all starting at position 0 with decreasing ranges.
C. \(h = [1, 3, 1, 3, 1]\)
Rising edges: \(1 + 2 + 0 + 2 + 0 = 5\). The "zigzag" pattern has two interior rises of 2.
D. \(h = [3, 3, 3, 3, 3]\)
Rising edges: \(3 + 0 + 0 + 0 + 0 = 3\). A flat profile needs only 3 operations: three horizontal bars spanning the entire array.
Notice: arrays A, B, and C all have the same answer (5) despite very different shapes. Array D has max height 3 and answer 3 — a flat profile needs exactly max-height operations. The shape of the profile matters, not just the maximum.
Warm-up 2: Parity Sweep
Given this \(2 \times 2\) grid of coins, trace the snake-order algorithm:
Total = 10 (even), so all cells can be made even. Snake order: (0,0), (0,1), (1,1), (1,0).
Trace it yourself before checking: how many moves does the algorithm produce? What does the final grid look like?
Challenge
Prove that for the Grand Garden problem, the answer is always at most \(h_{\max} \times n\) (where \(h_{\max}\) is the maximum height) but at least \(h_{\max}\). When does the answer equal \(h_{\max}\) exactly?
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ABC116C — Grand Garden | atcoder.jp/contests/abc116/tasks/abc116_c | 300pts |
| ABC109D — Make Them Even | atcoder.jp/contests/abc109/tasks/abc109_d | 400pts |
| ABC173D — Chat in a Circle | atcoder.jp/contests/abc173/tasks/abc173_d | 400pts |
| CF515C — Drazil and Factorial | codeforces.com/problemset/problem/515/C | 1400 |
| CF1348A — Phoenix and Balance | codeforces.com/problemset/problem/1348/A | 800 |