The Undo Trick
The Problem That Breaks Pure Greedy
Here's a problem that sounds like it should be easy: given an array, pick elements to maximize your sum, but no two picked elements can be adjacent.
The Greedy Choice: Pick the best available element, but leave a mathematical breadcrumb (\(V = \text{val}[L] + \text{val}[R] - \text{val}[i]\)) that lets you reverse the decision later if it was a mistake.
Try [10, 20, 15]. Greedy picks 20 (the largest). That blocks both 10 and 15. Total = 20. But \(10 + 15 = 25\).
Greedy just lost by committing too early. It grabbed the locally best element without realizing the two neighbors it blocked were worth more combined.
This isn't some edge case. It happens constantly. And if your first instinct is "just use DP" — sure, that works, but it's \(O(nk)\) when you need answers for all \(k\) simultaneously. The technique in this lesson does it in \(O(n \log n)\) and teaches you something deeper about greedy algorithms.
Why Can't We Just Fix Greedy?
You might think: "sort by value, pick greedily, skip neighbors." That's still greedy, and it still fails. The core issue is physical: picking one element permanently destroys two adjacent resources. When the combined value of those two destroyed resources exceeds the picked element, greedy has made an irrecoverable mistake.
Instead of asking "why does greedy fail?", ask: "what if greedy could un-fail?"
Theoretical Note (Matroids). Greedy is guaranteed optimal when the valid sets form a matroid — a structure with the "exchange property": if you have a valid set of size \(k\) and another of size \(k+1\), you can always extend the smaller one. For non-adjacent selection, this property fails. Sets \(A = \{2, 4\}\) (size 2) and \(B = \{1, 3, 5\}\) (size 3): none of 1, 3, 5 can be added to A without adjacency violations. No matroid → no greedy guarantee. But the undo trick lets greedy simulate the optimal by correcting its own mistakes.
The Core Idea: Leave a Breadcrumb
Here's something that takes a while to click, but once it does, you'll see it everywhere.
When greedy picks element \(i\) with value \(v_i\), don't just pick it and move on. Replace it with a virtual element whose value is carefully chosen:
Why this specific value? Here's the key algebra. If the algorithm later picks \(V\), the combined gain from both picks is:
The \(v_i\) terms cancel. Picking \(V\) mathematically "refunds" the original choice of \(v_i\) and replaces it with both neighbors. The algorithm is saying: "actually, I should have picked left and right instead."
Let's see this concretely. With [10, 20, 15]:
- Greedy picks 20. We insert \(V = 10 + 15 - 20 = 5\).
- Later, greedy picks 5. Total \(= 20 + 5 = 25 = 10 + 15\).
- The 20 was "refunded." The final selection is effectively \(\{10, 15\}\).
This is the breadcrumb. It sits in the data structure and waits. If it's ever worth undoing the choice, the algorithm will naturally find and use it.
What If \(V\) Is Negative?
Sometimes \(V = \text{val}[L] + \text{val}[R] - \text{val}[i]\) is negative. That means undoing this choice would decrease your total. A negative \(V\) sinks in the max-heap and never gets picked unless you're forced to (e.g., you must pick exactly \(k\) elements and have nothing better). The math still holds — the formula doesn't care about the sign.
The Trap: Thinking "Virtual" Means "Fake"
Here's where almost every first understanding breaks. The virtual element is not some hacky workaround. It's a real element in the data structure — it has a position in the linked list, a value, and the algorithm treats it identically to original elements.
When we pick element \(i\), we are collapsing \(i\) and its two neighbors into a single new node. The array shrinks by 2 elements. The new virtual node inherits the left neighbor of the old left node, and the right neighbor of the old right node. The linked list "bridges the gap" over the deleted neighbors.
When the algorithm picks a virtual element, it might create another virtual element (the undo-of-an-undo). And that's fine. The math telescopes cleanly no matter how many layers of undo stack up.
Trace: Watch It Correct Itself
Let's trace [10, 20, 15] step by step. Stare at this table — every column matters.
| Step | Heap State | Pop | Action | Virtual Insert | Running Total |
|---|---|---|---|---|---|
| Init | {(20,1), (15,2), (10,0)} | — | — | — | 0 |
| 1 | — | (20, idx 1) | Pick 20. Remove neighbors 10 (idx 0) and 15 (idx 2) | \(V = 10 + 15 - 20 =\) 5 at idx 1 | 20 |
| 2 | {(5,1)} | (5, idx 1) | Pick 5 (virtual). No more neighbors to remove. | — | \(20 + 5 =\) 25 |
After step 2: total \(= 25 = 10 + 15\). The undo element (value 5) encoded: "if you pick me, you're swapping your earlier choice of 20 for the pair \(10 + 15\)."
The greedy algorithm made a mistake, then corrected itself. Not because we added special-case logic, but because the math of the virtual element guaranteed the correction would be available.
Try it yourself before reading on: What if the array were [10, 20, 25]? What virtual element gets created? Does it ever get picked?
The Full Machine: Max-Heap + Doubly Linked List
The algorithm needs two data structures working together:
- Max-heap — always surfaces the best available gain (real or virtual)
- Doubly linked list — \(O(1)\) neighbor lookup and deletion
Algorithm (Max K Non-Adjacent Elements)
1. Initialize linked list: L[i] = i-1, R[i] = i+1
2. Add sentinels: values[0] = -2e15, values[n+1] = -2e15
3. Push all elements (value, index) into max-heap
4. For j = 1 to floor((n+1)/2):
a. Pop max from heap (skip deleted nodes — lazy deletion)
b. Let (val, id) = popped element
c. Add val to running sum; output sum
d. Compute V = values[L[id]] + values[R[id]] - values[id]
e. Mark L[id] and R[id] as deleted
f. Update linked list: L[id] = L[L[id]], R[id] = R[R[id]]
Also: R[L[id]] = id, L[R[id]] = id
g. Set values[id] = V, push (V, id) into heap
What Breaks If You Skip Sentinels?
The sentinels (\(-2 \times 10^{15}\) at positions 0 and \(n+1\)) act as boundary guards. If a real element at the edge gets picked, its "outside" neighbor is \(-2 \times 10^{15}\), so \(V = -2 \times 10^{15} + \text{val}[\text{other}] - \text{val}[\text{picked}]\) is extremely negative. This prevents the algorithm from ever trying to "undo into the boundary."
Without sentinels, you need ugly boundary checks: "if this is the first element, don't access L[L[id]]." The sentinels eliminate every special case.
What Breaks If You Skip Lazy Deletion?
Removing an element from a heap is \(O(n)\). We mark elements as deleted instead, and skip them during pops. Each element gets pushed at most twice (once real, once virtual) and extracted at most once, so lazy deletion costs \(O(n \log n)\) total.
If you try actual heap removal, you're back to \(O(n^2)\).
The Linked List Surgery
When we pick element id and delete its neighbors, we are collapsing three nodes into one. The virtual node at position id inherits the left neighbor of the old left node, and the right neighbor of the old right node:
L[id] = L[L[id]] // id's new left = old left's left
R[id] = R[R[id]] // id's new right = old right's right
R[L[id]] = id // new left neighbor points right to id
L[R[id]] = id // new right neighbor points left to id
Standard doubly-linked-list removal, done twice (once per deleted neighbor). If you've ever implemented LRU cache, this is the same pointer surgery.
Full Solution: JOI 2019 — Candies
Problem: Given an array of \(n\) integers, for each \(j\) from 1 to \(\lfloor(n+1)/2\rfloor\), find the maximum sum of \(j\) non-adjacent elements.
This is the direct application. Each iteration outputs the answer for the next \(j\).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int numElements;
cin >> numElements;
vector<long long> values(numElements + 2);
vector<int> leftNeighbor(numElements + 2);
vector<int> rightNeighbor(numElements + 2);
vector<bool> isDeleted(numElements + 2, false);
values[0] = -2e15;
values[numElements + 1] = -2e15;
leftNeighbor[0] = 0;
rightNeighbor[0] = 1;
leftNeighbor[numElements + 1] = numElements;
rightNeighbor[numElements + 1] = numElements + 1;
auto maxHeapCompare = [](const pair<long long, int>& leftPair, const pair<long long, int>& rightPair) {
return leftPair.first < rightPair.first;
};
priority_queue<pair<long long, int>, vector<pair<long long, int>>, decltype(maxHeapCompare)> maxHeap(maxHeapCompare);
for (int i = 1; i <= numElements; ++i) {
cin >> values[i];
leftNeighbor[i] = i - 1;
rightNeighbor[i] = i + 1;
maxHeap.push({values[i], i});
}
long long currentMaxSum = 0;
int maxPicks = (numElements + 1) / 2;
for (int j = 1; j <= maxPicks; ++j) {
while (isDeleted[maxHeap.top().second]) {
maxHeap.pop();
}
auto [currentValue, currentIndex] = maxHeap.top();
maxHeap.pop();
currentMaxSum += currentValue;
cout << currentMaxSum << "\n";
values[currentIndex] = values[leftNeighbor[currentIndex]] + values[rightNeighbor[currentIndex]] - values[currentIndex];
isDeleted[leftNeighbor[currentIndex]] = true;
isDeleted[rightNeighbor[currentIndex]] = true;
leftNeighbor[currentIndex] = leftNeighbor[leftNeighbor[currentIndex]];
rightNeighbor[currentIndex] = rightNeighbor[rightNeighbor[currentIndex]];
rightNeighbor[leftNeighbor[currentIndex]] = currentIndex;
leftNeighbor[rightNeighbor[currentIndex]] = currentIndex;
maxHeap.push({values[currentIndex], currentIndex});
}
return 0;
}
Complete State Trace on [10, 20, 15]
Indices 1..3 with sentinels at 0 and 4. Stare at every column — this is where the understanding happens.
| Step | Positions (linked list) | Heap Contents | Pop | sum += | \(V\) computed | Deletions |
|---|---|---|---|---|---|---|
| Init | \(0(-2 \times 10^{15}) \leftrightarrow 1(10) \leftrightarrow 2(20) \leftrightarrow 3(15) \leftrightarrow 4(-2 \times 10^{15})\) | {(20,2), (15,3), (10,1)} | — | — | — | — |
| \(j=1\) | — | — | (20, 2) | 20 | \(V = 10 + 15 - 20 = 5\) | del[1]=T, del[3]=T |
| — | \(0 \leftrightarrow 2(5) \leftrightarrow 4\) | {(15,3)*, (10,1)*, (5,2)} | — | — | — | — |
| \(j=2\) | — | skip (15,3)*, skip (10,1)* | (5, 2) | 25 | \(V = -2 \times 10^{15} + (-2 \times 10^{15}) - 5\) | — |
* = deleted, skipped during pop
Output: 20, 25. Correct.
The Minimization Twin: IOI 2007 — Backup
The undo trick works for minimization too. IOI 2007 Backup: given \(n\) points on a line, choose exactly \(k\) pairs of adjacent points to minimize total distance.
After sorting, the distances between consecutive points form an array. The problem reduces to: pick \(k\) non-adjacent elements from the difference array to minimize the sum.
The only changes:
- Min-heap instead of max-heap
- Sentinels are \(+2 \times 10^{15}\) instead of \(-2 \times 10^{15}\) (so boundaries never get picked in minimization)
The undo formula is identical: \(V = \text{val}[L] + \text{val}[R] - \text{val}[i]\). The telescoping cancellation works the same way.
The CSES Connection
A related CSES problem (Minimum Pairings) asks: given \(n\) points, form \(k\) pairs to minimize total distance. After sorting and computing the difference array, it's the same "min sum of \(k\) non-adjacent elements" — solvable with the min-heap undo trick.
Complexity
- Time: \(O(n \log n)\). Each of \(O(n)\) iterations does \(O(\log n)\) heap work.
- Space: \(O(n)\) for linked list, deleted array, and heap.
Each element is pushed at most twice (once real, once virtual) and extracted at most once. Lazy deletion keeps everything efficient.
Try It
Predict first, then verify. This is how the technique actually sticks.
Exercise 1: Array = [3, 7, 4, 6, 2, 8, 1]. Before running the algorithm, predict: what does greedy pick first? What virtual element gets created? What does greedy pick second?
Now trace the full algorithm for \(j = 1, 2, 3\). Fill in this table:
| \(j\) | Popped (val, idx) | \(V\) created | sum |
|---|---|---|---|
| 1 | ? | ? | ? |
| 2 | ? | ? | ? |
| 3 | ? | ? | ? |
Verify each output matches the true optimal sum of \(j\) non-adjacent elements (you can check with brute force for a 7-element array).
Exercise 2 (The edge case): Array = [5, 5, 5, 5, 5]. What happens? What are the virtual elements? Does the algorithm handle all-equal values correctly?
Challenge: Can you prove that the running sum is always non-decreasing? (Hint: think about what happens to the maximum heap element after each iteration.)
Problems
| Problem | Link | Difficulty |
|---|---|---|
| JOI 2019 — Candies | oj.uz/problem/view/JOI19_candies | Hard |
| IOI 2007 — Backup | dmoj.ca/problem/ioi07p3 | Hard |
| CSES — Minimum Pairings | cses.fi | Medium-Hard |