These are the notes for Competitive Programming episode 44, the fourth and last part of the DP optimisation section. The laddoo trays from episode 35 come back for the Diwali rush: the helper may only merge two neighbouring trays and charges one rupee per laddoo he lifts, but now there are up to 4000 trays. An original problem, Laddoo Trays (hard), asks for the cheapest way to end with one tray. Episode 35's interval DP is correct but tries every split point k for every range: about 10^10 steps at n = 4000, Time Limit Exceeded. Printing the best split opt[l][r] on a small input shows that it never decreases along a row or down a column, so the best split of a range is sandwiched between two answers we already know: opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r] (Knuth's condition). Searching only that sandwich, the work for one length telescopes to O(n), so the whole DP is O(n²): about 1.6 · 10^7 steps. Two real bugs follow: forgetting the base case opt[i][i] = i, and letting k reach r. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
It is the week before Diwali and the sweet shop has trays of laddoos everywhere: a whole row of them, up to 4000. The trays are too heavy to reorder, so the helper can only merge two trays standing next to each other, and he charges ₹1 for every laddoo he lifts (both trays are lifted). Same rules as episode 35, ten times more trays.
The idea that saves us comes from a dictionary. You have already found "cat" on page 40 and "cow" on page 52. Where is "cot"? It must be somewhere from page 40 to page 52: you do not search the whole book. And if you look up a whole run of words in order, each search starts where the previous one ended, so in total you flip only a few pages. In the DP, the two "known pages" are the best splits of two slightly shorter ranges, which were computed earlier.
Problem L2 · Laddoo Trays (hard)
(Written for this course, in the style of an AtCoder Beginner Contest problem. The easy version is Problem L in episode 35.)
n trays stand in a row; tray i holds a_i laddoos. Repeatedly merge two neighbouring trays into one; a merge costs the total number of laddoos in the two trays. Continue until one tray is left. Print the minimum total cost.
- Input: n (1 ≤ n ≤ 4000), then a_1 … a_n (1 ≤ a_i ≤ 10^9).
- Output: the minimum total cost.
| Input | Output |
|---|---|
4 / 20 20 10 20 |
140 ((20+20) = 40, (10+20) = 30, then 70) |
4 / 10 20 30 40 |
190 |
1 / 7 |
0 (nothing to merge) |
6 / 3 1 4 1 5 9 |
55 |
The answer fits in long long: the total is at most 4 · 10^12 laddoos, and each laddoo is lifted at most n − 1 times, so the cost stays below 1.6 · 10^16 (LLONG_MAX ≈ 9.2 · 10^18).
The DP from episode 35. dp[l][r] = the cheapest way to merge trays l..r into one tray. Think about the last merge: it joins a block l..k and a block k+1..r, which were merged independently, and it lifts every laddoo in l..r:
dp[l][r] = min over l ≤ k < r of ( dp[l][k] + dp[k+1][r] ) + sum(l..r), dp[i][i] = 0
The range sum comes from prefix sums (pre[r+1] − pre[l]), and the table is filled by length, short ranges first.
Step 1: the O(n³) DP (right, but TLE at n = 4000)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last merge: [l..k] + [k+1..r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
| Input | Output |
|---|---|
| sample 1 | 140 |
| sample 2 | 190 |
1 / 7 |
0 |
6 / 3 1 4 1 5 9 |
55 |
Now the worst case, 4000 trays built inside the program with a fixed random generator (mt19937 rng(44), values 1 … 10^9), so no huge input has to be pasted:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 4000; // worst case, built here
vector<ll> a(n);
mt19937 rng(44);
for (ll &x : a) x = rng() % 1000000000 + 1;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // last merge: [l..k] + [k+1..r]
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
On the SyntaxPilot compiler: Time Limit Exceeded. Run locally with no time limit, it does finish and prints 22378251862038, but only after about 40 seconds of CPU time, twenty times a typical 2-second limit. There are only n² / 2 ≈ 8 · 10^6 states; the killer is the inner loop over k: (n − 1) · n · (n + 1) / 6 = 10,666,666,000 split points in total.
Step 2: print opt[l][r] and look for a pattern
Same trick as in the previous DP optimisation episodes: before optimising, print the best choices on a small input. opt[l][r] is the k that gave the minimum for range l..r (the first one, if there is a tie).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n, -1));
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k; // best last split
}
dp[l][r] += pre[r + 1] - pre[l];
}
for (int l = 0; l < n; l++) { // print opt[l][r] for r > l
for (int r = 0; r < n; r++)
cout << (r > l ? to_string(opt[l][r]) : string(".")) << " ";
cout << "\n";
}
return 0;
}
Input 6 / 3 1 4 1 5 9, real output (row = l, column = r):
. 0 1 1 2 3
. . 1 1 2 4
. . . 2 3 4
. . . . 3 4
. . . . . 4
. . . . . .
- Along a row (l fixed, r grows: the range gets longer on the right), row 0 reads 0, 1, 1, 2, 3: it never goes down. So opt[l][r−1] ≤ opt[l][r].
- Down a column (r fixed, l grows: the range loses trays on the left), column 5 reads 3, 4, 4, 4, 4: it never goes down either. So opt[l][r] ≤ opt[l+1][r].
Put the two together: every best split is sandwiched between its left neighbour and the cell below it. For example opt[0][5] = 3 sits between opt[0][4] = 2 and opt[1][5] = 4, so instead of trying all five splits 0 … 4 we only need to try 2, 3 and 4.
Knuth's condition
opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r]
Both neighbours are ranges one tray shorter, so they were computed in the previous length. This is exactly the dictionary: two pages already found, search only between them. One printed table is not a proof, of course; the section "When does Knuth apply?" below says why it holds for this cost, and the stress test checks it on 1000 random inputs.
Step 3: why the total is only O(n²) (the telescoping proof)
For one cell (l, r) the loop runs k from opt[l][r−1] to opt[l+1][r], which is
steps(l, r) = opt[l+1][r] − opt[l][r−1] + 1
(The min(r − 1, …) cap in the real code can only make this smaller.) One cell can still cost O(n), for example when opt[l][r−1] = l and opt[l+1][r] = r − 1. The trick is to add up a whole length at once.
Fix a length len and let the left end run over l = 0, 1, …, n − len (so r = l + len − 1). Write the terms one below the other:
l = 0 : opt[1][len−1] − opt[0][len−2] + 1
l = 1 : opt[2][len] − opt[1][len−1] + 1
l = 2 : opt[3][len+1] − opt[2][len] + 1
…
l = n−len : opt[n−len+1][n−1] − opt[n−len][n−2] + 1
The plus part of each line is exactly the minus part of the next line (opt[1][len−1] appears in lines 0 and 1, opt[2][len] in lines 1 and 2, and so on). They cancel in pairs, like a telescope folding up, and only the two ends survive:
Σ steps = opt[n−len+1][n−1] − opt[0][len−2] + (n − len + 1) ≤ (n − 1) + n < 2n
So one whole length costs O(n), even though a single cell may cost O(n) on its own. This is an amortised bound: expensive cells are paid for by cheap neighbours. There are n − 1 lengths, so the total is O(n²): at most 2n² ≈ 3.2 · 10^7, and in practice about half of that.
Counting the work for real
The same Knuth DP, with counters for both loops on the n = 4000 worst case:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 4000; // worst case, built here
vector<ll> a(n);
mt19937 rng(44);
for (ll &x : a) x = rng() % 1000000000 + 1;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
ll knuthSteps = 0, cubicSteps = 0, worstLen = 0;
for (int len = 2; len <= n; len++) {
ll thisLen = 0;
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
cubicSteps += r - l; // every k from l to r - 1
dp[l][r] = LLONG_MAX;
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++) {
thisLen++;
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
}
dp[l][r] += pre[r + 1] - pre[l];
}
knuthSteps += thisLen;
worstLen = max(worstLen, thisLen);
}
cout << "answer " << dp[0][n - 1] << "\n";
cout << "every k " << cubicSteps << " steps\n";
cout << "Knuth " << knuthSteps << " steps\n";
cout << "worst length " << worstLen << " steps (2n = " << 2 * n << ")\n";
return 0;
}
Output:
answer 22378251862038
every k 10666666000 steps
Knuth 15984638 steps
worst length 7996 steps (2n = 8000)
The same answer as the 40-second O(n³) run, with 667 times fewer split points tried, and no single length ever exceeded the 2n bound from the proof.
Step 4: the accepted solution
Two changes to episode 35's code: a second table opt, with the base case opt[i][i] = i (a range of one tray "splits" at itself, which starts every sandwich), and the k loop running only over the sandwich, capped at r − 1 because the right block k+1..r must not be empty.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
// Knuth: opt[l][r-1] <= opt[l][r] <= opt[l+1][r]
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
| Input | Output |
|---|---|
4 / 20 20 10 20 |
140 |
4 / 10 20 30 40 |
190 |
1 / 7 |
0 |
6 / 3 1 4 1 5 9 |
55 |
For length 2 the sandwich is opt[l][l] = l up to min(l, opt[l+1][l+1] = l + 1) = l: exactly the one possible split. That is why both the base case and the cap matter.
The worst case, built inside the program as before:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 4000; // worst case, built here
vector<ll> a(n);
mt19937 rng(44);
for (ll &x : a) x = rng() % 1000000000 + 1;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
// Knuth: opt[l][r-1] <= opt[l][r] <= opt[l+1][r]
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
It prints 22378251862038 (the same value the O(n³) DP needed 40 seconds for) in under a second: 0.27 s of CPU time and 0.93 s wall clock here, most of it allocating and touching the two tables. Peak memory was 191348 KB (about 187 MiB): now memory, not time, is the real limit. See the complexity table below.
A stress test against the O(n³) DP
Knuth's condition is a claim about the cost function. Never trust it on faith: compare the fast DP with the plain one on many small random inputs.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cubic(vector<ll>& a) {
int n = a.size();
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
for (int len = 2; len <= n; len++)
for (int l = 0, r = len - 1; r < n; l++, r++) {
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l];
}
return dp[0][n - 1];
}
ll knuth(vector<ll>& a) {
int n = a.size();
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++)
for (int l = 0, r = len - 1; r < n; l++, r++) {
dp[l][r] = LLONG_MAX;
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
return dp[0][n - 1];
}
int main() {
mt19937 rng(44);
for (int t = 1; t <= 1000; t++) {
vector<ll> a(rng() % 10 + 1);
for (ll &x : a) x = rng() % 50 + 1;
if (cubic(a) != knuth(a)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output: all 1000 tests passed. Small sizes (1 … 10 trays) and small values (1 … 50) make ties and short ranges common, which is exactly where off-by-one mistakes in the sandwich show up.
Bug 1: forgetting opt[i][i] = i
Someone deletes the base-case line. vector<int>(n) fills opt with zeros, so every one-tray range claims its best split is 0.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
// Knuth: opt[l][r-1] <= opt[l][r] <= opt[l+1][r]
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Sample 2 (10 20 30 40, expected 190) prints -9223372036854775619. Sample 1 prints -9223372036854775689.
What happened on sample 2: for the range 1..2 the sandwich is opt[1][1] = 0 up to min(1, opt[2][2] = 0) = 0, so the only k tried is 0, which is outside the range [1, 2). It reads dp[1][0] + dp[1][2] = 0 + LLONG_MAX, which is not smaller than LLONG_MAX, so no split is ever accepted and dp[1][2] stays at LLONG_MAX. Adding the range sum 50 pushes it past the largest long long: signed overflow (undefined behaviour in C++; in practice it wraps around 2^64) gives −9223372036854775759. That huge negative number then spreads through every range that uses it, and dp[0][3] ends as LLONG_MAX + 190 wrapped around, which is exactly −9223372036854775619. A big negative answer to a "minimum cost" problem is the classic sign of LLONG_MAX overflow.
Fix: for (int i = 0; i < n; i++) opt[i][i] = i;
Bug 2: dropping the min(r − 1, …) cap
The base case is back, but the loop is written straight from Knuth's condition: k <= opt[l + 1][r].
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
// Knuth: opt[l][r-1] <= opt[l][r] <= opt[l+1][r]
for (int k = opt[l][r - 1]; k <= opt[l + 1][r]; k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Sample 2: Runtime Error (SIGSEGV), a segmentation fault (locally Segmentation fault, exit code 139 = signal 11). Sample 1 crashes the same way; only 1 / 7 survives (it prints 0, because with one tray the loop never runs).
Why: for a range of two trays, opt[l+1][r] = opt[r][r] = r, so k reaches r. Then dp[k + 1] is dp[r + 1], and for the last range (r = n − 1) that is row n, one past the end of the table. Reading through a row that does not exist touches memory the program does not own, and the operating system kills it. Remember: the left block is l..k and the right block is k+1..r, so k must stay below r.
Fix: k <= min(r - 1, opt[l + 1][r]).
When does Knuth apply?
Knuth optimisation fits DPs of the form
dp[l][r] = min over l ≤ k < r of ( dp[l][k] + dp[k+1][r] ) + C(l, r)
where C(l, r) is the extra cost of the range (here the range sum). It is guaranteed to be correct when C has two properties, for any four positions a ≤ b ≤ c ≤ d:
- Quadrangle inequality: C(a, c) + C(b, d) ≤ C(a, d) + C(b, c). In plain words: two overlapping ranges together cost no more than the outer range plus the inner range. Spreading the cost over the overlap never loses.
- Monotone on nested ranges: C(b, c) ≤ C(a, d). A range inside another range never costs more than the bigger one.
For the laddoo trays, C(l, r) = a_l + … + a_r. In the quadrangle inequality both sides count exactly the same laddoos (every tray from a to d once, and the overlap b..c twice), so it holds with equality. And since every a_i ≥ 1, a longer range has a bigger sum, so the cost is monotone. Under these two conditions one can prove that dp itself satisfies the quadrangle inequality, and from that, the sandwich opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r] (Knuth, 1971, for optimal binary search trees; generalised by F. Frances Yao, 1980, which is why it is also called the Knuth–Yao speed-up).
In a contest you rarely prove it. The practical recipe:
- The DP is an interval DP over a split point, with a cost that looks like a range sum, a range length or something built from them.
- Print opt on small random inputs and check that rows and columns never decrease.
- Stress test the Knuth version against the O(n³) one.
If the cost has negative values or depends on the split point k in a strange way, the sandwich can fail, and Knuth then gives a Wrong Answer with no warning.
Complexity and memory vs the constraints
| Approach | Time | Memory | Verdict at n = 4000 |
|---|---|---|---|
| every split point k (episode 35) | O(n³ / 6): 10,666,666,000 split points, ≈ 40 s | dp: 128 MB | TLE |
| Knuth: only the sandwich | O(n²): 15,984,638 split points, 0.93 s wall | dp 128 MB + opt 64 MB = 192 MB | accepted (with a 256 MB limit) |
The memory is simple arithmetic: 4000 × 4000 = 1.6 · 10^7 cells; long long is 8 bytes, so dp is 128 MB; int is 4 bytes, so opt is 64 MB. Measured peak: 191348 KB. Check the memory limit before you trust it: with a 128 MB limit this would be Memory Limit Exceeded. Ways to save memory if needed: keep opt as int (never long long), store only the upper triangle (l ≤ r, half the cells), or use a flat array instead of vector<vector<…>>.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| try every k at n = 4000 | Time Limit Exceeded (≈ 40 s locally) |
O(n³) ≈ 1.07 · 10^10 | k only in the sandwich |
no opt[i][i] = i |
-9223372036854775619 (expected 190) |
empty sandwich, dp stays LLONG_MAX, + sum wraps |
set the base case |
k <= opt[l + 1][r] without the cap |
Runtime Error (SIGSEGV) |
k reaches r, dp[r + 1] is out of bounds |
k <= min(r - 1, opt[l + 1][r]) |
| using Knuth where the sandwich fails | Wrong Answer |
the cost does not satisfy the conditions | print opt, stress test against O(n³) |
vector<vector<ll>> opt |
128 MB + 128 MB | split points fit in int |
vector<vector<int>> opt |
| filling by l and r instead of by length | reads unfilled neighbours | opt[l][r−1] and opt[l+1][r] must be ready | for len = 2..n outside |
Mini project
Build a "Knuth checker" for any interval DP. Write the plain O(n³) DP once, with the cost C(l, r) as a function you can swap. For each of 1000 random small inputs, fill dp and opt with every k, then check every cell for opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r] and report the first cell that breaks it. Try it with C = range sum (never breaks), C = range length, C = (range sum)², and C = a random number per range (breaks quickly). Then add a counter like the one above and print the number of split points with and without Knuth for n = 500, 1000, 2000 and 4000: the ratio should grow roughly linearly with n.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17), and each Knuth solution was checked against a brute-force DP on hundreds of random small inputs (600 for problems 1 and 2 together, 500 for problem 3), with no mismatch.
1. Optimal binary search tree. Keys 1 … n in sorted order are searched f_1 … f_n times. Build a BST that minimises Σ f_i · (depth of key i), with the root at depth 1. This is Knuth's original problem.
Solution
dp[i][j] = cheapest tree for keys i..j (empty range = 0). Choose the root k (i ≤ k ≤ j): the left and right subtrees are independent, and every key in i..j goes one level deeper, so dp[i][j] = min over k of dp[i][k−1] + dp[k+1][j] + (f_i + … + f_j). The cost is a range sum again, so root[i][j−1] ≤ root[i][j] ≤ root[i+1][j] holds, with base case root[i][i] = i. Here k = j is a valid root, so no r − 1 cap is needed.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> f(n + 2, 0), pre(n + 2, 0);
for (int i = 1; i <= n; i++) { cin >> f[i]; pre[i] = pre[i - 1] + f[i]; }
// dp[i][j] = cheapest tree for keys i..j (dp[i][i-1] = 0: empty)
vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));
vector<vector<int>> root(n + 2, vector<int>(n + 2, 0));
for (int i = 1; i <= n; i++) { dp[i][i] = f[i]; root[i][i] = i; }
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = LLONG_MAX;
// Knuth: root[i][j-1] <= root[i][j] <= root[i+1][j]
for (int k = root[i][j - 1]; k <= root[i + 1][j]; k++) {
ll c = dp[i][k - 1] + dp[k + 1][j];
if (c < dp[i][j]) { dp[i][j] = c; root[i][j] = k; }
}
dp[i][j] += pre[j] - pre[i - 1]; // every key goes one level deeper
}
cout << dp[1][n] << " (root = key " << root[1][n] << ")\n";
return 0;
}
3 / 34 8 50 prints 142 (root = key 3); 5 / 5 1 9 2 7 prints 42 (root = key 3). O(n²).
2. Cut a stick at given marks. A stick of length L must be cut at m given marks; cutting a piece costs its current length. Find the cheapest order of cuts.
Solution
Add the two ends: points p_0 = 0 < p_1 < … < p_m < p_{m+1} = L. dp[i][j] = cheapest way to make every cut strictly between p_i and p_j. The first cut at p_k (i < k < j) costs p_j − p_i and leaves two independent pieces: dp[i][j] = min over k of dp[i][k] + dp[k][j] + (p_j − p_i). The cost is a range length, so Knuth applies. Ranges with one mark inside have only one choice; longer ranges search opt[i][j−1] … opt[i+1][j], which always lies strictly inside (i, j).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll L;
int m;
cin >> L >> m;
vector<ll> p(m + 2, 0);
for (int i = 1; i <= m; i++) cin >> p[i];
p[m + 1] = L;
sort(p.begin(), p.end()); // points 0, the marks, L
int N = m + 2;
// dp[i][j] = cheapest way to make every cut strictly between p[i] and p[j]
vector<vector<ll>> dp(N, vector<ll>(N, 0));
vector<vector<int>> opt(N, vector<int>(N, 0));
for (int i = 0; i + 2 < N; i++) { // one mark inside: only one choice
dp[i][i + 2] = p[i + 2] - p[i];
opt[i][i + 2] = i + 1;
}
for (int len = 3; len < N; len++)
for (int i = 0; i + len < N; i++) {
int j = i + len;
dp[i][j] = LLONG_MAX;
// Knuth: opt[i][j-1] <= opt[i][j] <= opt[i+1][j]
for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) // first cut at p[k]
if (dp[i][k] + dp[k][j] < dp[i][j]) {
dp[i][j] = dp[i][k] + dp[k][j];
opt[i][j] = k;
}
dp[i][j] += p[j] - p[i]; // that cut costs the piece's length
}
cout << dp[0][N - 1] << "\n";
return 0;
}
Input L m then the marks: 100 3 / 25 50 75 → 200; 10 4 / 4 5 7 8 → 22; 7 4 / 1 3 4 5 → 16; 9 5 / 5 6 1 4 2 → 22; 10 0 → 0.
3. Trays in a circle (tray n is next to tray 1), n ≤ 4000.
Solution
Write the array twice (length 2n) and run the Knuth DP on it, but only for lengths up to n; the answer is the minimum of dp[i][i+n−1] over i = 0 … n−1 (cutting the circle between tray i−1 and tray i). The cost is still a range sum on the doubled array, so the sandwich still holds. Time O(2n · n), but memory is 4× larger: two 8000 × 8000 tables would be 768 MB, so for n = 4000 you must store only the cells with r − l < n (a 2n × n band).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> a(2 * n);
for (int i = 0; i < n; i++) { cin >> a[i]; a[i + n] = a[i]; } // write the circle twice
int m = 2 * n;
vector<ll> pre(m + 1, 0);
for (int i = 0; i < m; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(m, vector<ll>(m, 0));
vector<vector<int>> opt(m, vector<int>(m));
for (int i = 0; i < m; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++) // ranges up to one full turn
for (int l = 0; l + len - 1 < m; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
ll best = LLONG_MAX;
for (int i = 0; i < n; i++) best = min(best, dp[i][i + n - 1]); // cut the circle after tray i-1
cout << best << "\n";
return 0;
}
| Trays | In a row | In a circle |
|---|---|---|
10 40 40 10 |
200 |
180 |
1 50 50 1 1 |
208 |
161 |
20 20 10 20 |
140 |
140 |
7 |
0 |
0 |
In the circle the two 10s are neighbours, so they can be merged first.
4. Print the merge order as a bracketed expression.
Solution
The Knuth DP already stores opt[l][r], the last split of every range. Recurse: a single tray prints its number; a range prints ( plan(l, opt) + plan(opt + 1, r) ).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> a;
vector<vector<int>> opt;
string plan(int l, int r) { // the merge plan for trays l..r
if (l == r) return to_string(a[l]);
int k = opt[l][r]; // the last merge splits after k
return "(" + plan(l, k) + " + " + plan(k + 1, r) + ")";
}
int main() {
int n;
cin >> n;
a.resize(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
opt.assign(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << " = " << plan(0, n - 1) << "\n";
return 0;
}
140 = ((20 + 20) + (10 + 20))
190 = (((10 + 20) + 30) + 40)
55 = (((3 + 1) + (4 + 1)) + (5 + 9))
0 = 7
The recursion depth is at most n, which is fine for n = 4000.
Quick quiz
We are computing dp[3][10]. opt[3][9] = 5 and opt[4][10] = 7. Which split points k does the Knuth loop try?
for (int k = opt[l][r - 1];
k <= min(r - 1, opt[l + 1][r]); k++)
A) 3 to 9 · B) 5 to 7 · C) 5 to 9 · D) 7 to 10
Answer
B. l = 3, r = 10: k starts at opt[3][9] = 5 and stops at min(9, opt[4][10] = 7) = 7. Three tries instead of the seven (3 … 9) of the plain DP.
Interview questions
- What is Knuth optimisation? A speed-up for interval DPs of the form dp[l][r] = min over k of dp[l][k] + dp[k+1][r] + C(l, r): when opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r], search k only in that range. O(n³) becomes O(n²).
- Why is it O(n²) when one cell can still take O(n) steps? For a fixed length, the step counts opt[l+1][r] − opt[l][r−1] + 1 telescope: the sum over all l is at most about 2n. n lengths × O(n) = O(n²). It is an amortised bound.
- When does it apply? When the cost C satisfies the quadrangle inequality, C(a, c) + C(b, d) ≤ C(a, d) + C(b, c) for a ≤ b ≤ c ≤ d, and is monotone on nested intervals. Range sums and range lengths satisfy both. In a contest: print opt and stress test.
- What are the base case and the boundary details? opt[i][i] = i, the table filled by increasing length, and k capped at r − 1 when the right block k+1..r must be non-empty.
- How does it compare with divide-and-conquer optimisation? Divide and conquer (part 3 of this section) speeds up layered DPs dp[i][j] = min over k < j of dp[i−1][k] + C(k, j) using monotone opt within one layer, giving O(k · n log n). Knuth is for interval DPs, uses two neighbours from shorter ranges, and gives O(n²) without a log factor.
- What limits it in practice? Memory: two n × n tables, 192 MB at n = 4000 with
long longdp andintopt. Check the memory limit, keep opt asint, or store only l ≤ r.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Interval DP (range DP) | A DP whose state is a range [l, r], built from smaller ranges | dp[l][r] = cheapest merge of trays l..r |
| Split point | Where a range is cut into two sub-ranges for the last merge | k in [l, r): [l..k] + [k+1..r] |
| Last merge | The final operation in a range, joining two independently solved blocks | (20 + 20) + (10 + 20) |
| Prefix sums | pre[i] = a[0] + … + a[i−1], giving any range sum in O(1) | sum(l..r) = pre[r+1] − pre[l] |
| Fill by length | Solve all short ranges before longer ones | for (int len = 2; len <= n; len++) |
| Base case | The smallest states, set before the loops | dp[i][i] = 0, opt[i][i] = i |
| opt[l][r] | The best (first minimising) split point of range l..r | opt[0][5] = 3 for 3 1 4 1 5 9 |
| Knuth's condition | opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r] | 2 ≤ opt[0][5] = 3 ≤ 4 |
| Sandwich | The range of k allowed by Knuth's condition | k from 2 to 4 instead of 0 to 4 |
| Knuth optimisation (Knuth–Yao speed-up) | Searching only the sandwich, turning O(n³) into O(n²) | 15,984,638 steps instead of 10,666,666,000 |
| Telescoping sum | A sum where each term's plus part cancels the next term's minus part, leaving only the ends | (x₁ − x₀) + (x₂ − x₁) + … = x_last − x₀ |
| Amortised | A bound on the total cost of many steps, even if a single step is expensive | one cell O(n), one whole length O(n) |
| Quadrangle inequality | C(a, c) + C(b, d) ≤ C(a, d) + C(b, c) for a ≤ b ≤ c ≤ d | range sums: holds with equality |
| Monotone on nested intervals | An inner range never costs more than an outer one: C(b, c) ≤ C(a, d) | sum(2..3) ≤ sum(0..5) when all a_i ≥ 1 |
| O(n³), O(n²) | How the number of steps grows with n (big-O notation) | n = 4000: ≈ 10^10 vs ≈ 1.6 · 10^7 |
| Time Limit Exceeded (TLE) | The program ran longer than allowed | O(n³) at n = 4000, ≈ 40 s |
| Memory limit | The most memory a solution may use | 192 MB of tables needs a 256 MB limit |
LLONG_MAX |
The largest long long, 9223372036854775807, used as "infinity" |
dp[l][r] = LLONG_MAX; |
LLONG_MAX overflow |
Adding to LLONG_MAX goes past the largest value; signed overflow is undefined behaviour and in practice wraps to a huge negative |
-9223372036854775619 |
| Undefined behaviour | Code whose result C++ does not define; anything may happen | signed overflow, reading out of bounds |
| Segmentation fault (SIGSEGV) | The operating system kills a program that touches memory it does not own | dp[r + 1] past the last row |
| Runtime Error | The judge's verdict when a program crashes | the missing min(r − 1, …) cap |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random small inputs | all 1000 tests passed |
mt19937 |
C++'s Mersenne Twister random generator; a fixed seed gives the same numbers every run | mt19937 rng(44); |
| Worst case | The input that makes the program do the most work | n = 4000 trays, values up to 10^9 |
| Optimal binary search tree | A BST over sorted keys that minimises Σ frequency × depth | frequencies 34 8 50 → 142 |
| Doubling (for circles) | Writing a circular array twice so every circular range becomes a normal range | 10 40 40 10 → circle 180 |
Summary
- Problem L2 (n ≤ 4000): episode 35's interval DP is correct but tries 10,666,666,000 split points, TLE (≈ 40 s).
- Printing opt[l][r] for
3 1 4 1 5 9shows rows and columns that never decrease: opt[l][r−1] ≤ opt[l][r] ≤ opt[l+1][r]. - Search k only in that sandwich, like a dictionary lookup between two known pages.
- For one length the step counts telescope to less than 2n, so the total is O(n²): 15,984,638 steps, under a second,
22378251862038. - It is safe when the cost satisfies the quadrangle inequality and is monotone on nested ranges (range sums do); in contests, print opt and stress test (
all 1000 tests passed). - Memory is O(n²) too: dp 128 MB + opt 64 MB at n = 4000.
- Real bugs: no
opt[i][i] = i→-9223372036854775619; nomin(r − 1, …)cap → SIGSEGV.
Solutions in C++, Java and Python
Problem L2 · Laddoo Trays (hard)
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (ll &x : a) cin >> x;
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n));
for (int i = 0; i < n; i++) opt[i][i] = i;
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = LLONG_MAX;
// Knuth: opt[l][r-1] <= opt[l][r] <= opt[l+1][r]
for (int k = opt[l][r - 1]; k <= min(r - 1, opt[l + 1][r]); k++)
if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r];
opt[l][r] = k;
}
dp[l][r] += pre[r + 1] - pre[l];
}
cout << dp[0][n - 1] << "\n";
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken(); int n = (int) in.nval;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) { in.nextToken(); pre[i + 1] = pre[i] + (long) in.nval; }
long[][] dp = new long[n][n]; // dp[l][r]: merge trays l..r
int[][] opt = new int[n][n]; // opt[l][r]: best last split
for (int i = 0; i < n; i++) opt[i][i] = i; // base case of every sandwich
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
long best = Long.MAX_VALUE;
int hi = Math.min(r - 1, opt[l + 1][r]);
for (int k = opt[l][r - 1]; k <= hi; k++) { // only the sandwich
long c = dp[l][k] + dp[k + 1][r];
if (c < best) { best = c; opt[l][r] = k; }
}
dp[l][r] = best + pre[r + 1] - pre[l];
}
System.out.println(dp[0][n - 1]);
}
}
(StreamTokenizer reads numbers as double, which is exact for values up to 10^9.) With OpenJDK 21 it printed 22378251862038 for the n = 4000 worst case in 0.64 s.
Python (correct, but too slow and too big for n = 4000 in pure Python: the worst case took 8.2 s and about 745 MiB here. It handles n ≈ 1000 in 0.34 s and n ≈ 2000 in 1.6 s.)
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
pre = [0] * (n + 1)
for i, x in enumerate(a):
pre[i + 1] = pre[i] + x
dp = [[0] * n for _ in range(n)] # dp[l][r]: merge trays l..r
opt = [[0] * n for _ in range(n)] # opt[l][r]: best last split
for i in range(n):
opt[i][i] = i # base case of every sandwich
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
dl, best, bk = dp[l], None, l
for k in range(opt[l][r - 1], min(r - 1, opt[l + 1][r]) + 1): # only the sandwich
c = dl[k] + dp[k + 1][r]
if best is None or c < best:
best, bk = c, k
dp[l][r] = best + pre[r + 1] - pre[l]
opt[l][r] = bk
print(dp[0][n - 1])
main()
All three print 140, 190, 0 and 55 for the four samples (20 20 10 20, 10 20 30 40, 7, 3 1 4 1 5 9), and all three print the same answers as the C++ version on the random tests with n = 500, 1000 and 2000 (2065336328967, 4628661785350, 10262592527208).
Next episode: Graphs for contests: BFS/DFS templates, grids and 0-1 BFS. That finishes DP optimisation: the monotonic queue, the convex hull trick, divide and conquer, and Knuth.