These are the notes for Competitive Programming episode 43, part three of the DP optimisation section. Kavya's travel agency takes a colony to a temple: n families stand in a queue and board exactly k buses in queue order, and the noise in a bus is the square of the number of people in it. An original problem, Quiet Buses, asks for the smallest total noise. Filling every bus to about total / k gives 115 instead of 105. The layered DP dp[g][i] = min over j of dp[g−1][j] + (pre[i] − pre[j])² is correct but O(k·n²): Time Limit Exceeded at n = 10^5, k = 50. Printing the best split point shows that it never moves left as i grows. So we compute the middle i first, then give the left half the search range up to its best j and the right half the range from it: O(n log n) per layer, O(k·n·log n) in total. 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
Kavya runs a travel agency and is taking a colony to a temple. Family i has a[i] people. Families board in queue order, so each bus takes a block of neighbouring families, and no family is split. In a bus everyone chats with everyone, so the noise grows like the square of the number of people. Kavya wants the quietest trip: the smallest total noise over all k buses.
Problem T · Quiet Buses
(Written for this course, in the style of an AtCoder / Codeforces DP problem.)
Split a[1..n] into exactly k non-empty contiguous blocks, keeping the order. The noise of a block is (its sum)². Print the minimum total noise.
- Input: n and k, then a[1] … a[n].
- Constraints: 1 ≤ k ≤ min(n, 50), n ≤ 10^5, 1 ≤ a[i] ≤ 10^4.
- A block sum reaches 10^9 and its square 10^18: use
long long.
| Input | Output | Why |
|---|---|---|
6 3 / 4 1 3 5 2 2 |
105 |
buses of 8, 5, 4 people (or 5, 8, 4): 64 + 25 + 16 |
5 2 / 3 1 4 1 5 |
100 |
3 1 4 and 1 5: 8² + 6² = 64 + 36 |
3 3 / 5 5 5 |
75 |
every family alone: 25 + 25 + 25 |
Attempt 1: equal buses (Wrong Answer)
Squares punish big buses, so make every bus about equal: fill each one up to about total / k.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<ll> a(n);
ll total = 0;
for (ll &x : a) { cin >> x; total += x; }
ll target = (total + k - 1) / k, cur = 0, noise = 0; // about total/k each
int used = 1;
for (int i = 0; i < n; i++) {
if (cur + a[i] > target && cur > 0 && used < k) { noise += cur * cur; cur = 0; used++; }
cur += a[i];
}
noise += cur * cur;
cout << noise << "\n";
return 0;
}
Sample 1 prints 115 (expected 105): Wrong Answer. The target is ⌈17 / 3⌉ = 6. The greedy closes bus 1 at 5 people (4 + 1) and bus 2 at only 3 people, because adding the 5 would pass 6. Now it has used all its buses, so the last bus takes 5 + 2 + 2 = 9 people: 25 + 9 + 81 = 115. Each early choice looked fine locally, but it changed what was left for the end. (Sample 2 prints 116 instead of 100.)
Attempt 2: the layered DP (correct, TLE)
Let dp[g][i] = the least noise for the first i families in g buses. The last bus takes families j + 1 … i, and with prefix sums pre[i] = a[1] + … + a[i] its noise is (pre[i] − pre[j])²:
dp[g][i] = min over j < i of dp[g−1][j] + (pre[i] − pre[j])², dp[0][0] = 0, everything else starts at INF
Each layer g only needs layer g − 1, so we keep two arrays: prv (g − 1 buses) and cur (g buses).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<ll> pre(n + 1, 0);
for (int i = 1; i <= n; i++) { cin >> pre[i]; pre[i] += pre[i - 1]; }
const ll INF = LLONG_MAX;
vector<ll> prv(n + 1, INF), cur(n + 1);
prv[0] = 0; // 0 carriages, 0 groups
for (int g = 1; g <= k; g++) {
for (int i = 0; i <= n; i++) {
cur[i] = INF;
for (int j = 0; j < i; j++) // last carriage: groups j+1..i
if (prv[j] != INF)
cur[i] = min(cur[i], prv[j] + (pre[i] - pre[j]) * (pre[i] - pre[j]));
}
swap(prv, cur);
}
cout << prv[n] << "\n";
return 0;
}
Sample 1 prints 105, sample 2 100, the edge case 75. Correct. Now the worst case, built inside the program (n = 10^5, k = 50, random a[i] from 1 to 10^4):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 100000, k = 50; // worst case, built here
vector<ll> pre(n + 1, 0);
mt19937 rng(43);
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + rng() % 10000 + 1;
const ll INF = LLONG_MAX;
vector<ll> prv(n + 1, INF), cur(n + 1);
prv[0] = 0;
for (int g = 1; g <= k; g++) {
for (int i = 0; i <= n; i++) {
cur[i] = INF;
for (int j = 0; j < i; j++)
if (prv[j] != INF)
cur[i] = min(cur[i], prv[j] + (pre[i] - pre[j]) * (pre[i] - pre[j]));
}
swap(prv, cur);
}
cout << prv[n] << "\n";
return 0;
}
Time Limit Exceeded (it was still running when we stopped it after 10 seconds). Each layer tries about n² / 2 pairs (i, j), so the total is k · n² / 2 ≈ 50 · 10^10 / 2 = 2.5 · 10^11 steps.
The key observation: the split never moves left
For every i the inner loop tries every j to find one thing: where the last bus should start. Call that best j opt[g][i] (the optimal split point). Intuition: add one more family at the end of the queue and the last bus gets heavier, so it should give some families back to the earlier buses. Its start should move right, or stay; never left. Intuition fooled us once already (the greedy), so we print opt and look:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<ll> pre(n + 1, 0);
for (int i = 1; i <= n; i++) { cin >> pre[i]; pre[i] += pre[i - 1]; }
const ll INF = LLONG_MAX;
vector<ll> prv(n + 1, INF), cur(n + 1);
prv[0] = 0;
for (int g = 1; g <= k; g++) {
cout << "g=" << g << " opt:";
for (int i = 0; i <= n; i++) {
cur[i] = INF;
int opt = -1;
for (int j = 0; j < i; j++)
if (prv[j] != INF && prv[j] + (pre[i] - pre[j]) * (pre[i] - pre[j]) < cur[i]) {
cur[i] = prv[j] + (pre[i] - pre[j]) * (pre[i] - pre[j]);
opt = j; // best start of the last carriage
}
if (i >= g) cout << " " << opt;
}
cout << "\n";
swap(prv, cur);
}
return 0;
}
Sample 1 output:
g=1 opt: 0 0 0 0 0 0
g=2 opt: 1 1 2 3 3
g=3 opt: 2 3 3 4
As a table (opt[g][i] = the j where the last bus starts, for the first i families; "–" means fewer families than buses):
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| g = 1 | – | 0 | 0 | 0 | 0 | 0 | 0 |
| g = 2 | – | – | 1 | 1 | 2 | 3 | 3 |
| g = 3 | – | – | – | 2 | 3 | 3 | 4 |
Every row is non-decreasing in i: opt is monotone. Note that values repeat (1, 1 and 3, 3); that matters for the bug later. (Sample 2 prints g=2 opt: 1 2 2 3, also monotone.)
Why opt is monotone: the quadrangle inequality
Write cost(j, i) for the noise of the block a[j+1..i]. The opt is guaranteed to be monotone when the cost satisfies the quadrangle inequality:
cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c) for all a ≤ b ≤ c ≤ d
In plain words: you have two blocks that overlap ([a, c] and [b, d]). Swap them for one long block that covers both ([a, d]) plus the short overlap ([b, c]). That pair must cost at least as much: "the long one plus the short one" is never cheaper than "the two crossing ones".
Checking it for cost = (sum)². Split the long block into three parts: x = sum of a..b, y = sum of b..c (the overlap), z = sum of c..d. All three are ≥ 0 because the families have positive sizes.
- Left side: cost(a, c) + cost(b, d) = (x + y)² + (y + z)² = x² + 2xy + 2y² + 2yz + z²
- Right side: cost(a, d) + cost(b, c) = (x + y + z)² + y² = x² + 2xy + 2y² + 2yz + z² + 2xz
The right side is bigger by exactly 2xz ≥ 0, so the inequality holds. The extra 2xz is the "chatting" between the first part and the last part, which only happens when they sit in the same long bus.
Why does this make opt monotone? Suppose for i the best start is j₁ (the smallest best j, which is what our strict < keeps), and for a larger i′ some j₀ < j₁ were strictly better than j₁. Put a = j₀, b = j₁, c = i, d = i′ in the inequality and rearrange: cost(j₀, i) − cost(j₁, i) ≤ cost(j₀, i′) − cost(j₁, i′). So the advantage of j₀ over j₁ can only grow when the end moves from i′ back to i, and j₀ would also strictly beat j₁ for i: a contradiction with j₁ being the best. In a contest you rarely prove this: you print opt on random inputs and look, then confirm with a stress test.
We also checked it by brute force on the array 8 6 17 13 16 (all 126 quadruples a ≤ b ≤ c ≤ d), in Practice question 3 below: (sum)² breaks it 0 times.
Divide and conquer: solve the middle first
How do we use a monotone opt? Do not compute i from left to right. For a range of i values [l, r] whose opt we know lies in [optl, optr]:
- Take mid = (l + r) / 2 and compute cur[mid] by scanning every j in [optl, min(mid − 1, optr)]. Call the winner best.
- Every i < mid has opt ≤ best, so the left half [l, mid − 1] searches j in [optl, best].
- Every i > mid has opt ≥ best, so the right half [mid + 1, r] searches j in [best, optr]. best itself is still allowed, because opt values can repeat.
- Recurse. Each layer starts with
solve(0, n, 0, n).
This is divide and conquer: split the problem into two halves, solve each one recursively.
Why is each layer O(n log n)? Look at one recursion depth (one level of the recursion tree). At depth 0 there is one call, scanning [0, n]. At depth 1 there are two calls, scanning [optl, best] and [best, optr]: these two ranges touch only at best. At every depth the j ranges sit side by side and overlap only at their end points, so together they cover at most n + 1 values plus one shared end point per call: about O(n) per depth. Each call halves [l, r], so there are about log₂(n + 1) ≈ 17 depths for n = 10^5. Total per layer: O(n log n); for all k layers: O(k · n · log n) ≈ 50 · 10^5 · 17 ≈ 8.5 · 10^7.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX;
vector<ll> pre, prv, cur;
ll cost(int j, int i) { return (pre[i] - pre[j]) * (pre[i] - pre[j]); }
// fill cur[l..r]; the best j for them lies in [optl, optr]
void solve(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2, best = -1;
cur[mid] = INF;
for (int j = optl; j <= min(mid - 1, optr); j++)
if (prv[j] != INF && prv[j] + cost(j, mid) < cur[mid]) {
cur[mid] = prv[j] + cost(j, mid);
best = j;
}
if (best == -1) best = optl; // no valid j: keep the range as it is
solve(l, mid - 1, optl, best); // left half: opt ≤ best
solve(mid + 1, r, best, optr); // right half: opt ≥ best
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
pre.assign(n + 1, 0);
for (int i = 1; i <= n; i++) { cin >> pre[i]; pre[i] += pre[i - 1]; }
prv.assign(n + 1, INF);
cur.assign(n + 1, INF);
prv[0] = 0;
for (int g = 1; g <= k; g++) {
solve(0, n, 0, n);
swap(prv, cur);
}
cout << prv[n] << "\n";
return 0;
}
Details that matter:
j ≤ mid − 1: the last bus (families j + 1 … mid) must not be empty.prv[j] != INF: skip impossible states (for example j families in more buses than families), and never add toLLONG_MAX, which would overflow.best == -1happens only when no j is valid (mid < g); keeping optl leaves the ranges as wide as they were.
| Input | Output |
|---|---|
6 3 / 4 1 3 5 2 2 |
105 |
5 2 / 3 1 4 1 5 |
100 |
3 3 / 5 5 5 |
75 (k = n: every family alone) |
The worst case, with the same generator as the TLE run (n = 10^5, k = 50, mt19937 rng(43)), replacing main by:
int main() {
int n = 100000, k = 50; // worst case, built here
pre.assign(n + 1, 0);
mt19937 rng(43);
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + rng() % 10000 + 1;
prv.assign(n + 1, INF);
cur.assign(n + 1, INF);
prv[0] = 0;
for (int g = 1; g <= k; g++) {
solve(0, n, 0, n);
swap(prv, cur);
}
cout << prv[n] << "\n";
return 0;
}
prints 4987894304792711 in about 0.37 s. The layered DP ran out of time on exactly this input.
Stress test against the O(k·n²) DP
A stress test runs the fast solution and a slow but obviously correct one on many small random inputs and stops at the first difference. Here: 1000 queues of 1 … 10 families with sizes 1 … 20 and a random k from 1 to n (so k = n is tested too). The code reuses INF, pre, prv, cur, cost and solve from the accepted solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX;
vector<ll> pre, prv, cur;
ll cost(int j, int i) { return (pre[i] - pre[j]) * (pre[i] - pre[j]); }
// fill cur[l..r]; the best j for them lies in [optl, optr]
void solve(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2, best = -1;
cur[mid] = INF;
for (int j = optl; j <= min(mid - 1, optr); j++)
if (prv[j] != INF && prv[j] + cost(j, mid) < cur[mid]) {
cur[mid] = prv[j] + cost(j, mid);
best = j;
}
if (best == -1) best = optl; // no valid j: keep the range as it is
solve(l, mid - 1, optl, best); // left half: opt ≤ best
solve(mid + 1, r, best, optr); // right half: opt ≥ best
}
ll brute(int n, int k) {
vector<ll> p(n + 1, INF), c(n + 1);
p[0] = 0;
for (int g = 1; g <= k; g++, swap(p, c))
for (int i = 0; i <= n; i++) {
c[i] = INF;
for (int j = 0; j < i; j++) if (p[j] != INF) c[i] = min(c[i], p[j] + cost(j, i));
}
return p[n];
}
ll fast(int n, int k) {
prv.assign(n + 1, INF);
cur.assign(n + 1, INF);
prv[0] = 0;
for (int g = 1; g <= k; g++) { solve(0, n, 0, n); swap(prv, cur); }
return prv[n];
}
int main() {
mt19937 rng(7);
for (int t = 1; t <= 1000; t++) {
int n = rng() % 10 + 1, k = rng() % n + 1;
pre.assign(n + 1, 0);
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + rng() % 20 + 1;
if (brute(n, k) != fast(n, k)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 1000 tests passed";
}
Output: all 1000 tests passed.
The best + 1 bug
A tempting "optimisation": mid already used best, so the right half can start from best + 1. Only this line changes:
solve(mid + 1, r, best + 1, optr); // right half: opt > best ?
Sample 2 now prints 9223372036854775807, which is LLONG_MAX, our INF. In layer g = 1 every opt is 0 (the only valid start: one bus takes everything), and j = 0 is the only j with prv[j] ≠ INF. The first call (mid = 2) finds best = 0, so the right half searches from j = 1: no valid j at all. The left half loses j = 0 the same way one level down. Printing cur after each layer of the buggy program shows the damage:
INF INF 16 INF INF INF ← layer 1: only i = 2 was filled
INF INF INF 32 41 INF ← layer 2: i = 5 has nothing valid to build on
So cur[5] stays INF and that is what gets printed. (Sample 1 happens to print 105, which is why one sample is not enough.) The same change in the stress test prints mismatch on test 1.
The opt values never decrease, but they can repeat (1, 1 and 3, 3 in the table above). The right half must include best: [best, optr]. With the line fixed back, sample 2 prints 100 again.
Complexity vs the constraints
n ≤ 10^5, k ≤ 50.
| Approach | Time | Memory | Verdict |
|---|---|---|---|
| equal buses (greedy) | O(n) | O(n) | Wrong Answer (115, expected 105) |
| layered DP, every j for every i | O(k · n²) ≈ 2.5 · 10^11 | O(n) (two layers) | Time Limit Exceeded |
| divide and conquer DP | O(k · n · log n) ≈ 8.5 · 10^7 | O(n) (two layers) | Accepted, 0.37 s on the worst case |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| fill buses equally | 115 (expected 105) |
a local choice ruins the last bus | DP over layers |
| every j for every i | Time Limit Exceeded |
O(k · n²) ≈ 2.5 · 10^11 | opt is monotone: divide and conquer |
right half from best + 1 |
9223372036854775807 on sample 2; mismatch on test 1 in the stress test |
opt values can repeat | right half searches [best, optr] |
j up to mid instead of mid − 1 |
here still all 1000 tests passed (the squares hide it) |
allows an empty last bus; with a cost where an empty block is cheap it breaks "exactly k non-empty" | j ≤ min(mid − 1, optr) |
int for sums or squares |
overflow, wrong answers | a square reaches 10^18 | long long |
| using divide and conquer without checking opt | wrong answers (for max − min: 51 of 1000 tests mismatch, Practice 3) |
the cost breaks the quadrangle inequality | print opt, stress test |
Mini project
Build a "trip planner": read the families and k, print the minimum noise and the buses (where each starts, how many people ride in it). Add a --check mode that runs the O(k · n²) DP and the divide and conquer version side by side on random inputs, and a third mode that prints the opt table so you can see the monotone rows for any cost function you type in (sum², pairs, max − min, …). Use it to decide quickly whether divide and conquer DP is safe for a new cost.
Practice
-
Noise = chatting pairs: s · (s − 1) / 2 for a bus of s people.
Solution
Change only the cost: <code>ll s = pre[i] - pre[j]; return s * (s - 1) / 2;</code>. It still satisfies the quadrangle inequality: s(s − 1)/2 = (s² − s)/2, the −s part is linear and cancels on both sides, and the s² part leaves the same 2xz ≥ 0 (halved). Real outputs: sample 1 → <b>44</b> (8, 5, 4 people: 28 + 10 + 6), sample 2 → <b>43</b> (28 + 15), edge case → <b>30</b> (10 + 10 + 10). The stress test with this cost prints <b>all 1000 tests passed</b>. -
Print where each bus starts.
Solution
Store <code>from[g][mid] = best</code> inside <code>solve</code> (before <code>best</code> is replaced by optl), in a (k + 1) × (n + 1) table (50 · 10^5 ints = 20 MB at most). Then walk back from (g, i) = (k, n): bus g takes families from[g][i] + 1 … i, then i = from[g][i]. Real outputs: sample 1 → <code>105</code> and starts <b>1 3 5</b> (buses <code>4 1 | 3 5 | 2 2</code> = 5, 8, 4 people: 25 + 64 + 16 = 105, a tie with 8, 5, 4); sample 2 → <code>100</code>, starts <b>1 4</b>; edge case → <code>75</code>, starts <b>1 2 3</b>.from[G][mid] = best; // remember the split if (best == -1) best = optl; ... vector<int> starts; // walk back from (k, n) for (int g = k, i = n; g >= 1; g--) { int j = from[g][i]; starts.push_back(j + 1); // bus g takes families j+1..i i = j; } reverse(starts.begin(), starts.end()); -
Cost = max − min of a block. Is opt still monotone?
Solution
<b>No.</b> We ran the same stress test with cost = max − min of a[j+1..i] (precomputed for all pairs): <code>first mismatch on test 20: n=5 k=3 a = 8 6 17 13 16 brute 4 fast 5</code> and <code>51 of 1000 tests mismatch</code>. Printing <b>every</b> j that reaches the best value on that input:
In layer 3, opt goes 2 → 3 → 2: it moves left, and since each set has a single element, no tie-breaking rule can save it. The quadrangle inequality also fails: on <code>8 6 17 13 16</code> the brute-force check prints <code>max-min breaks it at a=0 b=1 c=2 d=3: 2 + 11 > 11 + 0</code> and <code>126 quadruples: (sum)^2 breaks 0, max-min breaks 12</code>. In words: blocks {8, 6} and {6, 17} cost 2 + 11 = 13, but the long block {8, 6, 17} plus the overlap {6} cost only 11 + 0. Use the O(k · n²) DP (or another idea) for this cost.g=1 opt: { 0 } { 0 } { 0 } { 0 } { 0 } g=2 opt: { 1 } { 2 } { 2 } { 2 } g=3 opt: { 2 } { 3 } { 2 } answer 4 -
k up to n.
Solution
The same code is correct for any k ≤ n (the stress test already draws k up to n, and the edge case <code>3 3</code> gives <code>75</code>). Only the time changes: O(k · n · log n) becomes O(n² log n). Real runs with random sizes 1 … 10^4: n = k = 2000 → <code>66633495705</code> in 0.14 s; n = k = 5000 → <code>165975684798</code> in 0.49 s; n = 5000, k = 2500 → <code>256486043754</code> in 0.32 s. For k = n the program also printed <code>sum of a[i]^2</code>, and it was equal: with squares and positive sizes, splitting a bus never makes it louder, so every family rides alone. For n = 10^5 and k = n this would be about 1.7 · 10^11 steps: too slow, and it needs a different trick (removing the "exactly k" layer with a penalty per bus, often called the Aliens trick).
Quick quiz
solve was called with j allowed in [0, 90]. The middle i = 50 found best = 20. Which j range does the right half search?
solve(l, mid - 1, optl, best);
solve(mid + 1, r, best, optr);
A) [0, 20] · B) [20, 90] · C) [21, 90] · D) [0, 90]
Answer
B. Every i > 50 has opt ≥ 20 (and ≤ optr = 90). best itself is allowed again, because neighbouring i can share the same opt. C is the best + 1 bug.
Interview questions
- What is divide and conquer DP? An optimisation for layered DPs of the form dp[g][i] = min over j < i of dp[g−1][j] + cost(j, i) when opt[g][i] is monotone in i: compute the middle i, then recurse with the search range split at its best j. O(n log n) per layer instead of O(n²).
- When can you use it? When the optimal split point never moves left as i grows. A sufficient condition is the quadrangle inequality cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c) for a ≤ b ≤ c ≤ d. In practice: print opt on random inputs and stress test.
- Why is each layer O(n log n)? At each recursion depth the j ranges are side by side and overlap only at their end points, so one depth scans O(n) values; halving [l, r] gives about log n depths.
- Why does the right half include best? opt is non-decreasing, not strictly increasing; two neighbouring i can share the same opt. Starting at best + 1 can skip the only valid split (real output:
9223372036854775807). - How much memory does it need? Two layers of n + 1 values (O(n)), plus O(log n) recursion stack. Storing opt for reconstruction adds O(k · n).
- How does it compare with the other DP optimisations? Monotonic queue (episode 41) handles a sliding window of j; convex hull trick (episode 42) handles costs that are lines in a term of j; divide and conquer DP handles a general cost with monotone opt, in O(k · n · log n); Knuth optimisation (next episode) handles interval DPs with monotone opt in O(n²).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Contiguous block | A run of neighbouring elements, with no gaps | families 3 … 5 |
| Layer | All DP states with the same number of groups g; layer g only reads layer g − 1 | prv = g − 1 buses, cur = g buses |
| Layered DP | dp[g][i] filled one layer at a time | dp[g][i] = min dp[g−1][j] + cost(j, i) |
| Prefix sum | pre[i] = a[1] + … + a[i]; the sum of a[j+1..i] is pre[i] − pre[j] | pre = 0 4 5 8 13 15 17 |
| cost(j, i) | The cost of the block a[j+1..i] (here its sum squared) | cost(0, 3) = 8² = 64 |
| opt / optimal split point | The j that gives the best value for dp[g][i]: where the last group starts | opt[2][6] = 3 on sample 1 |
| Monotone (non-decreasing) | Never goes down as i grows; equal neighbours are allowed | 1 1 2 3 3 |
| Divide and conquer | Split a problem into halves, solve each half recursively | left half [optl, best], right half [best, optr] |
solve(l, r, optl, optr) |
Fills cur[l..r], knowing their opt lies in [optl, optr] | solve(0, n, 0, n) |
| mid / best | The middle i of the current range and its optimal j | mid = 50, best = 20 |
| Recursion depth | One level of the recursion tree; about log₂ n levels here | 17 levels for n = 10^5 |
| Quadrangle inequality | cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c) for a ≤ b ≤ c ≤ d | (sum)²: right side bigger by 2xz |
| Greedy | Make the locally best choice and never undo it | equal buses → 115 |
| Stress test | Compare a fast and a slow correct solution on many small random inputs | all 1000 tests passed |
| INF | A value meaning "impossible"; here LLONG_MAX |
prv[j] = INF |
LLONG_MAX |
The largest long long: 2^63 − 1 |
9223372036854775807 |
| Overflow | A result too big for its type wraps around | int sums of 10^9 squared |
| TLE (Time Limit Exceeded) | The program is too slow for the time limit | O(k · n²) at n = 10^5 |
| WA (Wrong Answer) | The program prints a wrong result | 115 instead of 105 |
| Reconstruction | Walking back through stored opt values to recover the groups | starts 1 3 5 |
| Aliens trick | Removing an "exactly k groups" dimension by charging a penalty per group (a later topic) | k up to n = 10^5 |
Summary
- Split an array into k contiguous groups with a cost per group: the layered DP dp[g][i] = min over j of dp[g−1][j] + cost(j, i) is correct but O(k · n²).
- Equal-sized groups is a greedy that fails:
115instead of105. - Print opt[g][i]: for cost = (sum)² it never moves left (1 1 2 3 3; 2 3 3 4). The quadrangle inequality explains why: the difference is 2xz ≥ 0.
- Divide and conquer: compute mid by scanning [optl, min(mid − 1, optr)], then left [optl, best], right [best, optr]. O(n) per depth, log n depths: O(k · n · log n), two layers of memory.
- n = 10^5, k = 50:
4987894304792711in 0.37 s instead of TLE;all 1000 tests passedagainst the slow DP. - Real bug: the right half from best + 1 prints
9223372036854775807(INF), because opt values can repeat. - Not every cost works: max − min breaks the inequality (
51 of 1000 tests mismatch). Check before you trust it.
Solutions in C++, Java and Python
Problem T · Quiet Buses
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX;
vector<ll> pre, prv, cur;
ll cost(int j, int i) { return (pre[i] - pre[j]) * (pre[i] - pre[j]); }
// fill cur[l..r]; the best j for them lies in [optl, optr]
void solve(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2, best = -1;
cur[mid] = INF;
for (int j = optl; j <= min(mid - 1, optr); j++)
if (prv[j] != INF && prv[j] + cost(j, mid) < cur[mid]) {
cur[mid] = prv[j] + cost(j, mid);
best = j;
}
if (best == -1) best = optl; // no valid j: keep the range as it is
solve(l, mid - 1, optl, best); // left half: opt ≤ best
solve(mid + 1, r, best, optr); // right half: opt ≥ best
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
pre.assign(n + 1, 0);
for (int i = 1; i <= n; i++) { cin >> pre[i]; pre[i] += pre[i - 1]; }
prv.assign(n + 1, INF);
cur.assign(n + 1, INF);
prv[0] = 0;
for (int g = 1; g <= k; g++) {
solve(0, n, 0, n);
swap(prv, cur);
}
cout << prv[n] << "\n";
return 0;
}
Java
import java.util.*;
import java.io.*;
public class Main {
static final long INF = Long.MAX_VALUE;
static long[] pre, prv, cur;
static long cost(int j, int i) { return (pre[i] - pre[j]) * (pre[i] - pre[j]); }
// fill cur[l..r]; the best j for them lies in [optl, optr]
static void solve(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2, best = -1;
cur[mid] = INF;
for (int j = optl; j <= Math.min(mid - 1, optr); j++)
if (prv[j] != INF && prv[j] + cost(j, mid) < cur[mid]) {
cur[mid] = prv[j] + cost(j, mid);
best = j;
}
if (best == -1) best = optl; // no valid j: keep the range as it is
solve(l, mid - 1, optl, best); // left half: opt <= best
solve(mid + 1, r, best, optr); // right half: opt >= best
}
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;
in.nextToken(); int k = (int) in.nval;
pre = new long[n + 1];
for (int i = 1; i <= n; i++) { in.nextToken(); pre[i] = pre[i - 1] + (long) in.nval; }
prv = new long[n + 1];
cur = new long[n + 1];
Arrays.fill(prv, INF);
prv[0] = 0;
for (int g = 1; g <= k; g++) {
solve(0, n, 0, n);
long[] t = prv; prv = cur; cur = t;
}
System.out.println(prv[n]);
}
}
Python (about 8.5 · 10^7 steps at the worst case are far too slow in pure Python; fine for the samples and small inputs)
import sys
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + int(data[1 + i])
INF = float("inf")
prv = [INF] * (n + 1)
prv[0] = 0
cur = [INF] * (n + 1)
def solve(l, r, optl, optr):
# fill cur[l..r]; the best j for them lies in [optl, optr]
if l > r:
return
mid = (l + r) // 2
best, val = -1, INF
for j in range(optl, min(mid - 1, optr) + 1):
if prv[j] != INF:
c = prv[j] + (pre[mid] - pre[j]) ** 2
if c < val:
val, best = c, j
cur[mid] = val
if best == -1:
best = optl # no valid j: keep the range as it is
solve(l, mid - 1, optl, best) # left half: opt <= best
solve(mid + 1, r, best, optr) # right half: opt >= best
for g in range(k):
solve(0, n, 0, n)
prv, cur = cur, prv
print(prv[n])
main()
All three print 105, 100 and 75 for the two samples and the edge case 3 3 / 5 5 5.
Next episode: DP optimisation 4: Knuth optimisation (an interval DP from O(n³) to O(n²), with the same kind of monotone split point).