Why this matters when you build with AI
An AI tool given a DP problem often answers with the first technique that fits the wording. A statement that says "minimum cost to split the row" becomes a quadratic loop, even when n is 200000. The sample passes, a brute force on small inputs agrees, and the judge still times out.
This set trains the order of work: read the limits, pick the technique from the limits and the shape of the transition, write a brute force, then compare. An AI answer is a draft. It is trustworthy only after it matches a brute force on random small inputs and runs in time at the largest limit.
How to use this set
Each problem has a statement, limits, one sample and a hint. The hint names the technique class. Read it only after a first attempt. "Show the answer" comes after the hint and holds a reference solution.
Every reference solution was compiled with g++ -std=c++17 -O2 and compared with a brute force on 300 random small inputs. Work in this order:
- Read the limits and write down the complexity you need. An O(n^2) loop at n = 200000 does about 4 * 10^10 steps.
- Write the brute force first, in the simplest form that follows the statement.
- Write the DP and check it on the sample.
- Compare the two on random small inputs.
- Time the DP at the largest limit. Only then open the answer.
| # | Problem | Main technique | Largest limit |
|---|---|---|---|
| 1 | Shelf cuts | prefix DP over the last shelf | n = 300 |
| 2 | Parcels to couriers | subset DP over couriers | n = m = 16 |
| 3 | Submask sums | subset-sum (zeta) transform | n = 18 |
| 4 | Non-decreasing digits | digit DP | N = 10^18 |
| 5 | Connected pick in a tree | tree knapsack | n = 2000 |
| 6 | Heaviest path from each node | rerooting | n = 200000 |
| 7 | Bounded items | binary splitting | n = 100, counts 1000 |
| 8 | Blocks with a one | window sums of dp | n = 200000 |
| 9 | Relay costs in a window | monotone deque | n = 200000 |
| 10 | Arbitrary slopes | Li Chao tree | n = 200000 |
| 11 | Squared pieces | divide and conquer optimisation | n = 3000 |
| 12 | Ribbon welding | Knuth optimisation | n = 300 |
| 13 | Pick the technique | no code, reasoning from limits | none |
| 14 | Prefix subset sums | bitset DP | n = 200 |
Terms used
- A brute force is a slow program that follows the statement directly. You trust it because it is simple.
- A reference solution is the fast program under "Show the answer". It is checked against the brute force.
- A stress test runs many random small inputs through two programs and compares the outputs.
- A sample is the example in the statement. It is one input, so passing it is a weak test.
- Modulo 998244353 means the answer is the remainder after dividing by that fixed number.
- A bitset is a row of bits packed into machine words, so a shift or an OR touches 64 bits at once.
The harness
Each C++ program has two modes. With no argument it runs the fast solution. With the argument brute it runs the slow one. This Python loop feeds both the same random input and compares the output.
import random
import subprocess
def run(binary, args, text):
r = subprocess.run([binary] + args, input=text, capture_output=True, text=True, timeout=60)
return r.stdout.strip()
def stress(binary, make_input, tests=300):
bad = 0
for _ in range(tests):
text = make_input()
if run(binary, [], text) != run(binary, ["brute"], text):
bad += 1
print("differs on input:", repr(text))
print(f"{binary}: {tests - bad}/{tests} agree")
def small_p01():
n = random.randint(1, 12)
K = random.randint(0, 10)
h = [random.randint(1, 20) for _ in range(n)]
return f"{n} {K}\n" + " ".join(map(str, h)) + "\n"
stress("./p01", small_p01)On this machine the run printed:
./p01: 300/300 agreeThe generator is the only part that changes per problem. It must make valid inputs only: values inside the limits, parents before children, and the right count on each line. Random tests use small n so the brute force finishes. Large n is checked by timing, and for two problems by a slower polynomial reference. Each problem says which check was done.
The problems
Problem 1: Shelf cuts
You have n boards in a row. Board i has height h_i. Cut the row into consecutive shelves. A shelf costs K plus the gap between its tallest and shortest board. Output the smallest total cost.
Input: the first line holds n and K. The second line holds h_1 to h_n. Limits: 1 at most n at most 300, 0 at most K at most 10^6, 1 at most h_i at most 10^6.
Sample input:
5 3
4 1 3 9 2Sample output: 11
Hint, read after a first attempt: the state is "the first i boards are placed". The transition picks where the last shelf starts. Count states times transition cost before you optimise.
Show the answer
The state dp[i] is the least cost for the first i boards. Walk the start j of the last shelf down from i - 1 to 0, keeping the running tallest and shortest board.
ll solve(int n, ll K, const vector<ll>& h) {
const ll INF = LLONG_MAX / 4;
vector<ll> dp(n + 1, INF);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
ll mx = LLONG_MIN, mn = LLONG_MAX;
for (int j = i - 1; j >= 0; --j) {
mx = max(mx, h[j]);
mn = min(mn, h[j]);
dp[i] = min(dp[i], dp[j] + K + mx - mn);
}
}
return dp[n];
}Every answer in this set uses this shared header:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;The sample gives 11: one shelf of all five boards costs 3 + (9 - 1). Complexity is O(n^2) time and O(n) memory. Checked against a brute force that tries every set of cuts, on 300 random inputs with n up to 12.
Problem 2: Parcels to couriers
There are n parcels and m couriers, with n at most m. Each parcel goes to exactly one courier, and each courier takes at most one parcel. Courier c takes parcel p at cost cost[p][c]. Output the least total cost.
Input: the first line holds n and m. Then n lines follow, line p holding cost[p][1] to cost[p][m]. Limits: 1 at most n at most 16, n at most m at most 16, every cost from 1 to 100.
Sample input:
3 4
5 9 2 7
6 3 8 4
1 7 4 6Sample output: 6
Hint, read after a first attempt: keep the set of taken parcels as a bitmask. Process the couriers one at a time.
Show the answer
For each courier, either skip it or give it one parcel that is not yet taken. A new array is used for each courier, so no courier is used twice.
ll solve(int n, int m, const vector<vector<ll>>& cost) {
const ll INF = LLONG_MAX / 4;
int full = (1 << n) - 1;
vector<ll> dp(1 << n, INF), nd;
dp[0] = 0;
for (int c = 0; c < m; ++c) {
nd = dp; // skip this courier
for (int mask = 0; mask <= full; ++mask) {
if (dp[mask] >= INF) continue;
for (int p = 0; p < n; ++p)
if (!((mask >> p) & 1)) {
int nm = mask | (1 << p);
nd[nm] = min(nd[nm], dp[mask] + cost[p][c]);
}
}
dp.swap(nd);
}
return dp[full];
}The sample gives 6: parcel 1 goes to courier 3 (cost 2), parcel 2 to courier 2 (cost 3), parcel 3 to courier 1 (cost 1). Complexity is O(m * 2^n * n) time. For n = m = 16 the program ran in 0.02 s. Checked against a search over all assignments on 300 random inputs with n at most 4 and m at most 5.
Problem 3: Submask sums
You are given 2^n numbers g_0 to g_(2^n - 1). Read an index T as a bit mask: bit i of T is set when item i is in T. For a mask S, F(S) is the sum of g[T] over every submask T of S, meaning every T whose set bits are all set in S. Output the sum of F(S) over all 2^n masks S.
Input: the first line holds n. The second line holds the 2^n numbers. Limits: 1 at most n at most 18, 0 at most g at most 1000.
Sample input:
2
1 2 3 4Sample output: 18
Check by hand: F(0) = 1, F(1) = 1 + 2 = 3, F(2) = 1 + 3 = 4, F(3) = 1 + 2 + 3 + 4 = 10. The sum is 18.
Hint, read after a first attempt: there are two methods. Listing the submasks of every S costs about 3^n steps. Adding one bit at a time costs about n * 2^n. Time both at n = 18 before you choose.
Show the answer
Process one bit at a time. For bit i, each mask that has bit i receives the value of the mask without bit i. Afterwards f[S] holds F(S).
ll zeta_total(int n, vector<ll> f) {
for (int i = 0; i < n; ++i)
for (int m = 0; m < (1 << n); ++m)
if ((m >> i) & 1) f[m] += f[m ^ (1 << i)];
ll total = 0;
for (ll x : f) total += x;
return total;
}The slower method lists the submasks of each S:
ll submask_enum_total(int n, const vector<ll>& g) {
ll total = 0;
for (int S = 0; S < (1 << n); ++S)
for (int T = S;; T = (T - 1) & S) {
total += g[T];
if (T == 0) break;
}
return total;
}Both matched a double loop over all pairs on 300 random inputs with n at most 8. On a random input with n = 18 the answer was 193140757951. The transform took 0.05 s and the enumeration 0.29 s on the test machine (WSL2, g++ 15.2.0, -O2). Your times will differ. The answer can reach about 1000 * 3^18, which is 3.9 * 10^11, so use 64-bit integers.
Problem 4: Non-decreasing digits
Count the integers x with 1 at most x at most N whose decimal digits never decrease from left to right, and whose digit sum is divisible by 4. 1123 has non-decreasing digits and 1213 does not. N is a string with no leading zeros.
Input: one line with N. Limits: N has at most 19 digits and N is at most 10^18.
Sample input:
40Sample output: 8
The eight numbers are 4, 8, 13, 17, 22, 26, 35 and 39. Their digit sums are 4, 8, 4, 8, 4, 8, 8 and 12.
Hint, read after a first attempt: this is a digit DP. The state holds the position, the previous digit, the digit sum mod 4, a started flag and a tight flag.
Show the answer
The tight flag means the digits so far equal N, so the next digit may not exceed N's digit. Results are stored only when the flag is off, because then the rest does not depend on N.
string D;
ll memo[20][10][4][2];
bool seen[20][10][4][2];
ll go(int pos, int last, int s, int started, bool tight) {
if (pos == (int)D.size()) return (started && s == 0) ? 1 : 0;
if (!tight && seen[pos][last][s][started]) return memo[pos][last][s][started];
int lim = tight ? D[pos] - '0' : 9;
ll res = 0;
for (int d = 0; d <= lim; ++d) {
bool nt = tight && d == lim;
if (!started) {
if (d == 0) res += go(pos + 1, 0, 0, 0, nt); // a leading zero is not a digit
else res += go(pos + 1, d, d % 4, 1, nt);
} else {
if (d < last) continue; // digits must not decrease
res += go(pos + 1, d, (s + d) % 4, 1, nt);
}
}
if (!tight) {
seen[pos][last][s][started] = true;
memo[pos][last][s][started] = res;
}
return res;
}Read N into D and call go(0, 0, 0, 0, true). The number 0 is never counted, because the started flag stays 0 for it. For N = 10^18 the program printed 1171884. The brute force, which tests every x up to N, matched on 300 random N up to 10^5.
Problem 5: Connected pick in a tree
The tree has n nodes, numbered 1 to n, with root 1. The parent of node i is p_i, and p_i is less than i. Node i has value v_i, which may be negative. Choose a set S of at most k nodes. S must be empty, or be connected and contain node 1. Output the largest sum of values in S. The empty set gives 0.
Input: the first line holds n and k. The second line holds p_2 to p_n. The third line holds v_1 to v_n. Limits: 1 at most n at most 2000, 1 at most k at most n, every value from -10^6 to 10^6.
Sample input:
5 3
1 1 2 2
4 -1 3 2 5Sample output: 8
The best set is nodes 1, 2 and 5, with value 4 + (-1) + 5 = 8.
Hint, read after a first attempt: let dp[u][c] be the best sum of c nodes that contain u and lie inside u's subtree. Merge the children one at a time, the way a knapsack merges items.
Show the answer
Index 0 means "not taken". Each child is merged into its parent with the option of taking none of the child's nodes. Sizes are capped at k.
ll solve(int n, int k, const vector<int>& par, const vector<ll>& v) {
const ll NEG = LLONG_MIN / 4;
vector<vector<ll>> dp(n + 1);
for (int u = 1; u <= n; ++u) dp[u] = {NEG, v[u]};
for (int u = n; u >= 2; --u) { // children have larger indices, so they are finished first
int p = par[u];
vector<ll> ch = dp[u];
ch[0] = 0; // option: take none of this child's nodes
int cap = min((int)dp[p].size() - 1 + (int)ch.size() - 1, k);
vector<ll> nw(cap + 1, NEG);
for (int a = 1; a < (int)dp[p].size(); ++a)
for (int b = 0; b < (int)ch.size() && a + b <= cap; ++b)
if (dp[p][a] > NEG && ch[b] > NEG) nw[a + b] = max(nw[a + b], dp[p][a] + ch[b]);
dp[p] = nw;
dp[u].clear();
}
ll best = 0; // the empty set
for (int c = 1; c < (int)dp[1].size(); ++c) best = max(best, dp[1][c]);
return best;
}The sample gives 8. Complexity is O(n * k) time. On a random tree with n = k = 2000 the program ran in 0.005 s. Checked against all subsets on 300 random trees with n at most 10.
Test the empty set on purpose. If every value is -1, the answer is 0. A version that starts from the best single node prints -1 for that input.
Problem 6: Heaviest path from each node
The tree has nodes 1 to n, with root 1 and p_i less than i. Node i has weight w_i, at least 1. For each node u, find the largest total weight of a path that starts at u. The weight of a path is the sum of its node weights, including u. The path may stop at u. Output the n answers on one line, in order of u.
Input: the first line holds n. The second line holds w_1 to w_n. The third line holds p_2 to p_n. Limits: 1 at most n at most 200000, 1 at most w_i at most 10^9.
Sample input:
4
2 3 1 5
1 1 3Sample output: 8 11 6 11
Check node 2: the path 2, 1, 3, 4 has weight 3 + 2 + 1 + 5 = 11.
Hint, read after a first attempt: this is rerooting. One pass from the leaves up gives the best downward path from each node. A second pass from the root down gives the best path that first goes up. Keep the two best child values per node.
Show the answer
down[u] is the best path from u into its own subtree. outv[x] is the best path that starts at the parent of x and never enters x's subtree, and it includes the parent's weight.
vector<ll> solve(int n, const vector<ll>& w, const vector<int>& par) {
vector<ll> b1(n + 1, 0), b2(n + 1, 0), down(n + 1, 0), outv(n + 1, 0), ans(n + 1, 0);
vector<int> arg1(n + 1, 0);
for (int u = n; u >= 1; --u) {
down[u] = w[u] + b1[u]; // b1 holds the best child value, or 0 if none
if (u >= 2) {
int p = par[u];
if (down[u] > b1[p]) {
b2[p] = b1[p];
b1[p] = down[u];
arg1[p] = u;
} else if (down[u] > b2[p]) {
b2[p] = down[u];
}
}
}
for (int x = 2; x <= n; ++x) {
int p = par[x];
ll sib = (arg1[p] == x) ? b2[p] : b1[p]; // best sibling branch
outv[x] = w[p] + max({0LL, outv[p], sib});
}
for (int x = 1; x <= n; ++x) ans[x] = w[x] + max(outv[x], b1[x]);
return ans;
}The sample prints 8 11 6 11. Complexity is O(n) time and memory. At n = 200000 the program ran in 0.09 s including output. Checked against a search from every node on 300 random trees with n at most 10.
Problem 7: Bounded items
There are n kinds of item. Kind i has value v_i, weight w_i and count c_i, and you may take 0 to c_i copies of it. The capacity is W. Choose the numbers so the total weight is at most W. Output the largest total value.
Input: the first line holds n and W. Then n lines follow, each with v, w and c. Limits: 1 at most n at most 100, 0 at most W at most 10^4, 1 at most v and w at most 1000, 1 at most c at most 1000.
Sample input:
3 10
6 4 2
5 3 3
9 5 1Sample output: 16
Two items of the second kind (weight 6, value 10) and one of the first kind (weight 4, value 6) give weight 10 and value 16.
Hint, read after a first attempt: the 0/1 knapsack step is the one you know. The new step is how to turn c copies into a few bundles without losing any count.
Show the answer
Binary splitting writes a count c as bundles of sizes 1, 2, 4, and so on, plus one remainder. Each bundle is then a 0/1 item. Every count from 0 to c can be built from the bundles.
ll solve(int W, const vector<array<ll, 3>>& items) { // each item: value, weight, count
vector<ll> dp(W + 1, 0); // dp[x] = best value with total weight at most x
for (auto [v, w, c] : items) {
ll rem = c, k = 1;
while (rem > 0) {
ll t = min(k, rem); // one bundle of t copies
ll tv = t * v, tw = t * w;
for (ll x = W; x >= tw; --x) dp[x] = max(dp[x], dp[x - tw] + tv);
rem -= t;
k *= 2;
}
}
return dp[W];
}The sample gives 16. Complexity is O(W * sum of log2(c_i)). The worst case is about 100 * 10 * 10^4 = 10^7 steps. At n = 100 and W = 10^4 with random values the program ran in 0.005 s. Checked against a count-by-count enumeration on 300 random inputs with n at most 4 and counts at most 3.
Problem 8: Blocks with a one
A binary string s of length n has characters '0' and '1'. Split it into consecutive blocks. Each block has length at most K and contains at least one '1'. Count the splits modulo 998244353. Two splits differ when some cut is in a different place.
Input: the first line holds n and K. The second line holds s. Limits: 1 at most n at most 200000, 1 at most K at most n.
Sample input:
7 3
0100110Sample output: 2
The two splits are 01 | 001 | 10 and 010 | 01 | 10.
Hint, read after a first attempt: let dp[i] count the splits of the first i characters. The valid starts of the last block form a range, so a running sum of dp gives the total in O(1).
Show the answer
Let last1 be the position of the last '1' up to i. The block from j + 1 to i contains a one exactly when j is less than last1. Together with the length limit, j must lie between max(0, i - K) and last1 - 1. A prefix sum P of dp gives that range sum at once.
const ll MOD = 998244353;
ll solve(int n, int K, const string& s) {
vector<ll> dp(n + 1, 0), P(n + 2, 0); // P[t + 1] = dp[0] + ... + dp[t]
dp[0] = 1;
P[1] = 1;
int last1 = 0; // 1-based position of the last '1' so far, 0 if none
for (int i = 1; i <= n; ++i) {
if (s[i - 1] == '1') last1 = i;
if (last1 > 0) {
int lo = max(0, i - K), hi = last1 - 1;
if (hi >= lo) dp[i] = (P[hi + 1] - P[lo] + MOD) % MOD;
}
P[i + 1] = (P[i] + dp[i]) % MOD;
}
return dp[n];
}The sample gives 2. Complexity is O(n) time and memory. Checked against a loop over all cut sets on 300 random strings with n at most 14. At n = 200000 with K = 50 the program ran in 0.01 s.
Problem 9: Relay costs in a window
The statement defines dp[0] = 0 and, for i from 1 to n:
dp[i] = a_i + (the minimum of dp[j] + b_j over j from max(0, i - K) to i - 1)
Output dp[n]. Read it as a relay: a jump from station j to station i costs b_j + a_i, and it may go back at most K stations.
Input: the first line holds n and K. The second line holds a_1 to a_n. The third line holds b_0 to b_(n-1). Limits: 1 at most K at most n at most 200000, every value from -10^9 to 10^9.
Sample input:
5 2
3 1 4 1 5
0 2 -1 4 1Sample output: 7
The dp values for indices 0 to 5 are 0, 3, 1, 4, 1, 7.
Hint, read after a first attempt: this is a sliding window minimum. Keep the candidates in a deque ordered by value. A candidate that is not smaller than a newer one can never be the minimum again.
Show the answer
Each index j gets the key dp[j] + b_j. The front of the deque is the answer for the current window.
ll solve(int n, int K, const vector<ll>& a, const vector<ll>& b) { // a: 1..n, b: 0..n-1
vector<ll> dp(n + 1, 0), key(n + 1, 0);
deque<int> dq;
dp[0] = 0;
key[0] = dp[0] + b[0];
dq.push_back(0);
for (int i = 1; i <= n; ++i) {
while (!dq.empty() && dq.front() < i - K) dq.pop_front(); // left the window
dp[i] = a[i] + key[dq.front()];
if (i < n) {
key[i] = dp[i] + b[i];
while (!dq.empty() && key[dq.back()] >= key[i]) dq.pop_back(); // dominated
dq.push_back(i);
}
}
return dp[n];
}The sample gives 7. Complexity is O(n) time and memory. At n = 200000 with K = 5000 and values near 10^9 the program ran in 0.10 s. The O(n * K) brute force matched on 300 random inputs with n at most 40. Looping over every earlier j instead of the window does about n^2 / 2 = 2 * 10^10 steps at n = 200000.
Problem 10: Arbitrary slopes
The statement defines dp[0] = 0 and, for i from 1 to n:
dp[i] = R_i + (the minimum of dp[j] + P_i * Q_j over j from 0 to i - 1)
Output dp[n]. The P values and the Q values come in no sorted order.
Input: the first line holds n. The second line holds P_1 to P_n. The third line holds R_1 to R_n. The fourth line holds Q_0 to Q_(n-1). Limits: 1 at most n at most 200000, every P_i and R_i from -10^4 to 10^4, every Q_j from 0 to 10^4.
Sample input:
3
1 -2 3
0 1 -1
2 0 1Sample output: -1
The dp values for indices 0 to 3 are 0, 2, -3, -1.
Hint, read after a first attempt: each j is a line y = Q_j * x + dp[j], and each i asks for the smallest line value at x = P_i. Slopes and queries come in no order, so a convex hull with a moving pointer is not enough. Use a structure that accepts lines in any order.
Show the answer
A Li Chao tree is a segment tree over the integers from -10^4 to 10^4. Each node keeps one line, the one that is best at the node's middle point. Insertion walks down one path and pushes the loser to one side. A query walks one path and takes the minimum.
const int OFF = 10000; // x in [-10000, 10000] is stored at index x + OFF
const int SZ = 2 * OFF + 1;
struct Line {
ll m, b;
ll at(ll x) const { return m * x + b; }
};
struct LiChao {
vector<Line> t;
vector<char> has;
LiChao() : t(4 * SZ), has(4 * SZ, 0) {}
void add(Line nw) {
int node = 1, lo = 0, hi = SZ - 1;
while (true) {
if (!has[node]) {
t[node] = nw;
has[node] = 1;
return;
}
int mid = (lo + hi) / 2;
bool leftBetter = nw.at(lo - OFF) < t[node].at(lo - OFF);
bool midBetter = nw.at(mid - OFF) < t[node].at(mid - OFF);
if (midBetter) swap(t[node], nw); // keep the better line at mid in the node
if (lo == hi) return;
if (leftBetter != midBetter) { // the two lines cross in [lo, mid]
node = 2 * node;
hi = mid;
} else {
node = 2 * node + 1;
lo = mid + 1;
}
}
}
ll query(int idx) const { // idx = x + OFF
ll best = LLONG_MAX / 4;
int node = 1, lo = 0, hi = SZ - 1;
while (true) {
if (has[node]) best = min(best, t[node].at(idx - OFF));
if (lo == hi) break;
int mid = (lo + hi) / 2;
if (idx <= mid) {
node = 2 * node;
hi = mid;
} else {
node = 2 * node + 1;
lo = mid + 1;
}
}
return best;
}
};
ll solve(int n, const vector<ll>& P, const vector<ll>& R, const vector<ll>& Q) {
LiChao tree;
vector<ll> dp(n + 1, 0);
tree.add({Q[0], dp[0]});
for (int i = 1; i <= n; ++i) {
dp[i] = R[i] + tree.query((int)(P[i] + OFF));
if (i < n) tree.add({Q[i], dp[i]});
}
return dp[n];
}The sample gives -1. Complexity is O(n * log C) time, with C = 20001 points, and O(C) memory. At n = 200000 with random values the program ran in 0.14 s. It matched the quadratic DP on 20 random inputs with n from 200 to 1500.
The domain must match the limits. A query at x = 10001 would index past the tree.
Problem 11: Squared pieces
Given non-negative numbers a_1 to a_n, split them into exactly k consecutive pieces, each with at least one number. A piece costs the square of its sum. Output the least total cost.
Input: the first line holds n and k. The second line holds a_1 to a_n. Limits: 1 at most k at most n at most 3000, k at most 50, 0 at most a_i at most 10^4.
Sample input:
5 2
1 2 3 4 5Sample output: 117
The best cut is after the third number. The pieces have sums 6 and 9, and 36 + 81 = 117. The other cuts give 197, 153 and 125.
Hint, read after a first attempt: the DP has one layer per number of pieces. The best cut for a fixed end moves right as the end moves right. A divide and conquer over the end points finds the cuts for each layer in O(n log n).
Show the answer
Let dp_t[i] be the least cost of splitting the first i numbers into t pieces. With prefix sums P, a piece from j to i costs (P[i] - P[j])^2. The recursion solves the middle end point, then limits the left half to cuts up to that best cut and the right half to cuts from it on.
ll solve(int n, int k, const vector<ll>& a) { // a: 1..n
vector<ll> P(n + 1, 0);
for (int i = 1; i <= n; ++i) P[i] = P[i - 1] + a[i];
const ll INF = LLONG_MAX / 4;
vector<ll> prev(n + 1, INF), cur(n + 1, INF);
prev[0] = 0; // zero pieces cover zero numbers
function<void(int, int, int, int)> rec = [&](int lo, int hi, int optlo, int opthi) {
if (lo > hi) return;
int mid = (lo + hi) / 2;
ll best = INF;
int bestj = optlo;
for (int j = optlo; j <= min(mid - 1, opthi); ++j) {
if (prev[j] >= INF) continue;
ll d = P[mid] - P[j];
ll c = prev[j] + d * d;
if (c < best) {
best = c;
bestj = j;
}
}
cur[mid] = best;
rec(lo, mid - 1, optlo, bestj);
rec(mid + 1, hi, bestj, opthi);
};
for (int t = 1; t <= k; ++t) {
fill(cur.begin(), cur.end(), INF);
rec(t, n, t - 1, n - 1);
swap(prev, cur);
}
return prev[n];
}The sample gives 117. The best cut never moves left as the end moves right. This follows from the quadrangle inequality. For a at most b at most c at most d, the cost of pieces (a, c) and (b, d) together is at most the cost of pieces (a, d) and (b, c) together. Write the prefix sums at those points as x at most y at most z at most u. The right side minus the left side equals 2 (y - x)(u - z), which is never negative. The program also matched a quadratic layered DP on 20 random inputs with n up to 600 and k up to 12, and an enumeration of all splits on 300 inputs with n at most 10. Complexity is O(k * n * log n). At n = 3000 and k = 50 the program ran in 0.005 s.
Problem 12: Ribbon welding
A row of n strips has lengths s_1 to s_n. Two neighbouring groups can be welded into one. The weld costs the total length of the two groups. Strips never change order. Output the least total cost to weld everything into one group.
Input: the first line holds n. The second line holds s_1 to s_n. Limits: 1 at most n at most 300, 1 at most s_i at most 1000.
Sample input:
4
3 1 4 2Sample output: 20
Weld 3 with 1 (cost 4), then 4 with 2 (cost 6), then the two results (cost 10). The total is 20.
Hint, read after a first attempt: this is an interval DP. A plain version tries every split point and costs O(n^3). The best split points for an interval lie between those of its two shorter neighbours, so each interval needs to try only a short range. That is Knuth's optimisation.
Show the answer
Let opt[l][r] be the split point that gave the best value for [l, r]. The search for [l, r] runs from opt[l][r - 1] to opt[l + 1][r]. A length-2 interval has one possible split, so the upper bound is capped at r - 1.
ll knuth(int n, const vector<ll>& s) {
vector<ll> pre(n + 1, 0);
for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + s[i];
vector<vector<ll>> dp(n, vector<ll>(n, 0));
vector<vector<int>> opt(n, vector<int>(n, 0));
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;
int lo = opt[l][r - 1], hi = min(opt[l + 1][r], r - 1);
ll best = LLONG_MAX;
int bo = lo;
for (int m = lo; m <= hi; ++m) { // left part is l..m, right part is m+1..r
ll c = dp[l][m] + dp[m + 1][r];
if (c < best) {
best = c;
bo = m;
}
}
dp[l][r] = best + (pre[r + 1] - pre[l]);
opt[l][r] = bo;
}
return dp[0][n - 1];
}The sample gives 20. Complexity is O(n^2) time and memory. It matched every welding order (every binary tree over the strips) for n at most 7 on 300 random inputs, and the plain O(n^3) interval DP on 300 random inputs with n up to 120. For n = 300 both printed 1240658. Without the cap at r - 1, a length-2 interval would try the split m = r and read dp[r + 1][r], a cell outside the table.
The bounds need the cost to satisfy the quadrangle inequality. Here the weld cost is a sum of lengths. Both sides then equal the same sum of prefix sums, so the inequality holds with equality. A cost that breaks it breaks the bounds, and the O(n^3) version is the safe choice then.
Problem 13: Pick the technique
This problem has no code. For each situation, name the technique and the complexity you aim for, and say which limit decided it.
(a) Twenty tasks. Each is done once, the order is free, and the cost depends on which tasks were done before the last one.
(b) Count integers in a range [L, R], with R up to 10^18, whose digits follow a rule such as an even number of 7s.
(c) n = 200000 points with x_1 < x_2 < ... < x_n, all at most 10^6. Compute dp[i] = min over j < i of dp[j] + (x_i - x_j)^2.
(d) n = 3000 numbers in a row, split into exactly k = 100 pieces. The piece cost satisfies the quadrangle inequality.
(e) n = 3000 strips in a fixed order. Welding two neighbours costs their total length, until one group is left.
(f) n = 10^6. Compute dp[i] as the sum of dp[j] for j from i - K to i - 1, with K fixed.
(g) n = 100 kinds of item, counts up to 1000, capacity 10^4.
(h) n = 25 items. Choose a subset with total weight at most W and the largest value.
Show the answer
(a) Bitmask DP over sets of tasks, O(2^n * n). With n = 20 that is about 2 * 10^7 steps. The state must remember which tasks are done, so a set is the natural state.
(b) Digit DP. The range is too large to list, and the rule is about digits.
(c) Convex hull trick with a moving pointer, O(n). Expanding the square gives dp[j] + x_j^2 - 2 x_j x_i + x_i^2. The last term does not depend on j, so it is added after the minimum. The slopes -2 x_j decrease as j grows, and the queries x_i increase, so a pointer works. A Li Chao tree also works, in O(n log C). A plain O(n^2) loop is too slow at this limit.
(d) Divide and conquer optimisation, O(k * n * log n). That is about 3.5 * 10^6 steps. The condition in the statement is what makes it valid.
(e) Knuth's optimisation, O(n^2), if the cost satisfies the quadrangle inequality. This is the shape of Problem 12. A plain interval DP does about n^3 / 6 steps, which is about 4.5 * 10^9 at n = 3000, too slow.
(f) Prefix sums of dp, O(n). A window of fixed width is a sum that moves one step at a time.
(g) Bounded knapsack by binary splitting, O(n * W * log C). With W = 10^4 and counts up to 1000 this is about 10^7 steps, as in Problem 7.
(h) A plain bitmask DP does not fit. 2^25 masks times 25 items is about 8.4 * 10^8 steps, with a table of 2^25 entries. The module's bitmask lesson covers the range where that method works, about 20 items. For n = 25 the answer is another idea, which you should look up, not guess.
Problem 14: Prefix subset sums
Given n numbers a_1 to a_n. For each query (k, T), answer YES if some subset of a_1 to a_k has sum exactly T. The empty subset has sum 0. Otherwise answer NO.
Input: the first line holds n. The second line holds a_1 to a_n. The third line holds q. Then q lines follow, each with k and T. Limits: 1 at most n at most 200, 1 at most a_i at most 100, 1 at most q at most 20000, 0 at most k at most n, 0 at most T at most 20000.
Sample input:
4
3 5 2 7
4
2 8
3 10
4 12
1 6Sample output, one line per query: YES, YES, YES, NO.
Hint, read after a first attempt: keep one bitset per prefix. Bit t of the bitset for prefix k says whether sum t can be made. Adding a number a means each reachable sum either stays reachable or moves up by a.
Show the answer
The bitset for prefix k is the bitset for prefix k - 1 ORed with itself shifted left by a_k. The table is built once, and each query is one bit lookup.
const int MAXS = 20000;
vector<bitset<MAXS + 1>> pre(n + 1);
pre[0][0] = 1; // the empty subset makes sum 0
for (int k = 1; k <= n; ++k) pre[k] = pre[k - 1] | (pre[k - 1] << a[k]);
// query (k, T): print YES when pre[k][T] is set, NO otherwiseThis is the core. Read the input as the statement gives it, with a indexed from 1. The sample gives YES, YES, YES, NO. Complexity is O(n * S / 64) to build, where S = 20000, and O(1) per query. With n = 200 and 20000 random queries the program ran in 0.01 s. Checked against a loop over all subsets of the first k numbers on 300 random inputs with n at most 12.
Common mistakes
- Overflow. Problem 3 needs 64-bit sums. The same program with
intin place oflong longprinted -132770369 on an input whose correct answer is 193140757951. There was no crash and no warning. Check that the answer fits the type you use. - Quadratic at the top limit. Problem 9 with a loop over every earlier j does about 2 * 10^10 steps at n = 200000. The five-number sample runs instantly, so the sample hides the problem.
- Missing empty choice. In Problem 5 the answer must be at least 0. Starting from the best single node prints a negative number for an all-negative tree.
- Wrong bound at length 2. In Problem 12 the upper bound of the split search must stay at r - 1.
- Domain mismatch. In Problem 10 the tree covers only -10^4 to 10^4. Keep the constants in step with the statement.
- Untested monotone claims. An AI answer may say that a monotone or convex condition holds without a test. For Problems 11 and 12 the test is a comparison with a slower method on random inputs.
Checklist
- Read the limits, then write the complexity you need before any code.
- Write a brute force that follows the statement literally.
- Check the sample, then compare the two programs on 300 random small inputs.
- Test the all-negative and all-zero cases.
- Time the program at the largest limit, and check the answer fits the type and the modulus.
- Test every monotone or convexity claim before you rely on it.
- Keep the input format exactly as the statement gives it.
Check an AI answer
Give the model the statement with this prompt:
Solve this competitive programming problem in C++17. [paste the statement, with limits]
Before the code, write:
(1) the DP state and the transition, in one line each;
(2) the operation count at the largest limit;
(3) the technique you chose, and the property it needs.
Then give:
(a) a brute force that follows the statement literally, run when the program gets the argument brute;
(b) the fast solution;
(c) the output of both on the sample.
Mark each claim that you did not test as untested.A good answer names the state and the transition, gives an operation count that fits the limit, and separates the brute force from the fast solution. A bad answer skips the operation count, claims monotonicity without a test, and shows only the sample. Run both programs on 300 random small inputs, then time the fast one at the largest limit. An answer that passes only the sample is not finished.
Summary
Fourteen problems cover the module. Each needs a technique chosen from its limits and transition, a brute force to test against, and a timing at the largest size. The reference solutions were checked on random inputs and timed on one machine, and the samples were run and checked by hand.