Round 3: medium graphs and DP

Why this matters when you build with AI

When an AI tool writes a dynamic programming (DP) solution, the usual failure is the state, not the loop. DP means solving a problem by storing answers to smaller sub-problems in a table and reusing them. The state is the meaning of one table entry. If the state leaves out a value that the answer depends on, the program runs fast and gives wrong answers on some inputs. If the state carries too much, the table is too large for the limits, and the program times out or runs out of memory.

Here is a concrete case. Ask a tool for "the cheapest route from town 1 to town n using at most K coupons", and one wrong answer to watch for is a plain Dijkstra search over the towns. That search has no coupon count in its state, so it returns routes that use too many coupons. The code compiles, runs and prints a number. Only a brute force on a tiny map shows the mistake.

Ask for the state in words first. This prompt makes the tool commit to a state before any code:

Solve this in C++17. Before any code, write one comment with:
1. the state, in words: what one table entry means, including every count the limit depends on;
2. the transition: how one entry is computed from earlier entries;
3. the base case;
4. the order in which entries are filled.
Then give the time and memory in terms of n, m and K. Do not write code until items 1 to 4 are written.

A good answer for a coupon problem has a coupon count in the state and a time that includes the factor K + 1. A bad answer has a state with only the vertex. Check it by asking yourself which number the limit depends on, then checking that the state has it.

How the round works

This is a practice round you run on your own. The 90-minute timer is a choice made for this lesson, not a rule of any site. Follow these steps.

Start the timer. Read all five statements first, for about five minutes, and decide an order by how much work each one looks like.
For each problem, write four lines as a comment in your code file: state, transition, base case, complexity. Only then write code.
Test each solution against a brute force on small random inputs before you submit it.
Stop at 90 minutes. Then read the editorials, not before.
Fill in the post-round log (template in the section "Post-round log").

Terms used in this lesson:

A state is what one entry of a DP table means. A transition is the rule that fills one entry from others.
A base case is an entry you set directly, without a transition, such as the starting vertex.
A brute force is a slow program that is easy to trust, used only to check your fast program on small inputs.
A spanning tree of a connected graph is a set of edges that connects every vertex, with no cycle. A minimum spanning tree (MST) is one with the smallest total weight.
A disjoint set union (DSU) keeps groups of vertices and answers "are these two in the same group?" and "join these two groups" quickly.
A tree DP computes values on a rooted tree, one vertex at a time, from its children.
A knapsack problem picks items with a weight and a value to fit a capacity. A bounded knapsack allows up to a fixed number of copies of each item type.
An interval DP stores answers for every contiguous piece of a sequence, from length 1 up to the full length.

Shortest paths with non-negative weights are covered in the lesson "Shortest paths: Dijkstra, 0-1 BFS and Floyd-Warshall" in the advanced graphs module. This round assumes you know it.

The idea: state first, then the table

Take a small bounded knapsack. Bag capacity W = 10. Item types, given as weight, value and number of copies:

type 1: weight 4, value 7, 2 copies
type 2: weight 3, value 4, 3 copies
type 3: weight 5, value 9, 1 copy

The state is dp[x]: the best value that fits in a total weight of at most x, using the item types handled so far. The base case is dp[x] = 0 for every x, because the empty bag has value 0. The transition handles one copy at a time. For each copy of the current type, go through x from W down to the item weight w, and set dp[x] = max(dp[x], dp[x - w] + v).

The loop goes downward on purpose. Going down means dp[x - w] still holds the value before this copy, so each copy is used at most once. The program below (problem D in this round) fills the table this way. Running it on the sample gives 16, and this is the table it builds, which I computed by a script and checked by hand:

start           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
after type 1    [0, 0, 0, 0, 7, 7, 7, 7, 14, 14, 14]
after type 2    [0, 0, 0, 4, 7, 7, 8, 11, 14, 14, 15]
after type 3    [0, 0, 0, 4, 7, 9, 9, 11, 14, 16, 16]

Read the last row at x = 10. The answer is 16, from one item of type 3 (weight 5, value 9) and one item of type 1 (weight 4, value 7), total weight 9. The entry 15 after type 2 at x = 10 comes from one item of type 1 and two items of type 2 (weight 4 + 3 + 3 = 10, value 7 + 4 + 4 = 15). Writing the state first is what made each row easy to read.

The same habit applies to every problem below. If you cannot say what one entry means in one sentence, you are not ready to write the loop.

The round

Five original problems. Statements use the input and output shown. Each sample was run through the solution and the brute force, and both printed the same answer.

Problem A: Coupons on a road map

There are n towns, numbered 1 to n, and m one-way roads. Road i goes from town u to town v and costs w. You start in town 1 and want to reach town n. You hold K coupons. A coupon used on one traversal of one road makes that traversal cost 0, and each coupon can be used once. A route uses at most K coupons. Output the least total cost, or -1 if town n cannot be reached.

Limits: 2 <= n <= 2000, 1 <= m <= 6000, 0 <= K <= 5, 1 <= w <= 10^9.

Input: a first line n m K, then m lines u v w.

Sample input:

Sample output: 1 (route 1 to 3, cost 1, then 3 to 4 with the coupon, cost 0).

Problem B: The cheapest road network

There are n cities and m roads. Road i joins cities u and v (roads go both ways) and costs w. Connect all cities with a set of roads so that every city can reach every other. Output the least total cost, or -1 if that is impossible.

Limits: 1 <= n <= 200000, 0 <= m <= 200000, 1 <= w <= 10^9.

Input: n m, then m lines u v w.

Sample input:

Sample output: 9.

Problem C: The committee with a size limit

A company has n employees, numbered 1 to n. Employee i has a value w_i (its fun value). The reporting lines form a tree: n - 1 pairs of employees, each pair a boss and a report. Choose at most K employees so that no two chosen employees are directly connected (no boss and report are both chosen). Maximise the total value. Output that total.

Limits: 1 <= n <= 2000, 0 <= K <= n, 1 <= w_i <= 10^6.

Input: n K, then the n values on one line, then n - 1 lines u v.

Sample input:

Sample output: 10.

Problem D: The bag of stock

There are n item types. Type i has a weight w (1 to 100), a value v (1 to 10^6) and c copies (1 to 100). Choose how many copies of each type to take, from 0 up to c, so that the total weight is at most W. Output the largest total value.

Limits: 1 <= n <= 100, 1 <= W <= 2000.

Input: n W, then n lines w v c.

Sample input:

Sample output: 16.

Problem E: Remove the matching pairs

A string s of n lowercase letters is on a board. Scores are given for the letters a to z. One move: choose two positions on the board, the first to the left of the second, with the same letter, where every position between them has already been removed. Remove both and gain the score of that letter. You may stop at any time. Output the largest total gain.

Limits: 1 <= n <= 200, each score is between 1 and 10^6.

Input: a line with n, a line with s, then one line with the 26 scores for a to z.

Sample input:

6
abbaca
5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample output: 7 (remove the two b letters for 2, then the two a letters for 5, which are now next to each other).

Editorial A: shortest paths with coupons

State: dist[v][j] is the least cost to stand at town v after using exactly j coupons. Transition: a road from u to v with cost w moves (u, j) to (v, j) at cost w, and moves (u, j) to (v, j + 1) at cost 0 when j < K. Base case: dist[1][0] = 0. Answer: the smallest dist[n][j] over j.

The state has n * (K + 1) entries. The state that blows up is "which roads have been made free so far", a subset of the m roads, which has 2^m possibilities. With m = 6000 that is hopeless. The coupon count is enough, because a route that uses j coupons is the only thing the rest of the problem needs to know.

A coupon never makes a route worse, and a shortest route in this graph never repeats a town. A route that repeats a town can be cut down to a simpler one with no higher cost and no more coupons. So the state is complete.

The program is a Dijkstra search on the n * (K + 1) states, with the coupon edges added. Time is O((n + m) * (K + 1) * log), memory O(n * (K + 1) + m).

// State: dp[v][j] = least cost to stand at vertex v after using exactly j coupons (j from 0 to K).
// Transition: a directed edge u -> v of weight w moves (u, j) to (v, j) at cost w,
// and to (v, j + 1) at cost 0 when j < K (the coupon makes this traversal free).
// The layers form one Dijkstra graph with n * (K + 1) nodes.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m, K;
    scanf("%d %d %d", &n, &m, &K);
    vector<vector<pair<int, long long>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        scanf("%d %d %lld", &u, &v, &w);
        adj[u - 1].push_back({v - 1, w});
    }
    const long long INF = LLONG_MAX / 4;
    int L = K + 1;
    vector<long long> dist((size_t)n * L, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, s] = pq.top();
        pq.pop();
        if (d > dist[s]) continue;
        int u = s / L, j = s % L;
        for (auto [v, w] : adj[u]) {
            int t = v * L + j;
            if (d + w < dist[t]) {
                dist[t] = d + w;
                pq.push({dist[t], t});
            }
            if (j < K) {
                int t2 = v * L + j + 1;
                if (d < dist[t2]) {
                    dist[t2] = d;
                    pq.push({d, t2});
                }
            }
        }
    }
    long long best = INF;
    for (int j = 0; j <= K; j++) best = min(best, dist[(size_t)(n - 1) * L + j]);
    printf("%lld\n", best == INF ? -1LL : best);
    return 0;
}

Output on the sample: 1. The brute force tries every set of at most K roads as free, runs Bellman-Ford on each set, and keeps the best. I ran both on 400 random graphs with at most 5 towns and 7 roads, and they agreed on all of them.

Editorial B: spanning trees with DSU

State: a DSU array where par[v] names the group of v, using the roads taken so far. Transition: take roads in order of increasing cost, and take road (u, v) only if u and v are in different groups, then join those groups and add the cost. Base case: every city is its own group. Answer: the total, if the number of taken roads is n - 1, else -1.

The state that blows up here is "every subset of n - 1 roads", which has C(m, n - 1) possibilities. With m = 200000 that number is far beyond any computer. Kruskal's rule avoids it, because the greedy order is correct for minimum spanning trees. You do not need to check subsets at all.

The total can reach 200000 times 10^9 = 2 * 10^14, which does not fit in a 32-bit int, so the total uses long long.

// State: par[v] = the group representative of v, using the edges taken so far.
// Transition: sort edges by cost; take edge (u, v) only when u and v are in different groups,
// then join the two groups. Each taken edge adds its cost to the total.
#include <bits/stdc++.h>
using namespace std;
 
int par[200005];
 
int findp(int x) {
    while (par[x] != x) {
        par[x] = par[par[x]];
        x = par[x];
    }
    return x;
}
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<tuple<long long, int, int>> e;
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        scanf("%d %d %lld", &u, &v, &w);
        e.emplace_back(w, u - 1, v - 1);
    }
    sort(e.begin(), e.end());
    for (int i = 0; i < n; i++) par[i] = i;
    long long total = 0;
    int taken = 0;
    for (auto [w, u, v] : e) {
        int a = findp(u), b = findp(v);
        if (a != b) {
            par[a] = b;
            total += w;
            taken++;
        }
    }
    printf("%lld\n", taken == n - 1 ? total : -1LL);
    return 0;
}

Output on the sample: 9 (roads 2-3 cost 1, 1-3 cost 2, and 2-4 cost 6). The brute force tries every subset of exactly n - 1 roads, checks that the subset connects all cities with its own search, and keeps the cheapest. Both agreed on 400 random inputs with at most 5 cities and 7 roads.

Editorial C: tree DP with a count limit (worked problem)

This is the problem to read most slowly. It is the one whose full solution is shown with a real sample output, and the state here is the one you have to design yourself.

State: dp[v][j][c] is the best total value inside the subtree of v when exactly j employees are chosen there, and c = 1 if v itself is chosen, c = 0 if not. Only j up to K is kept. Base case: the single vertex v gives dp[v][0][0] = 0 and dp[v][1][1] = w_v (if K is at least 1).

Transition, merging a child x into v. If v is chosen (c = 1), the child cannot be chosen. If v is not chosen (c = 0), the child may be chosen or not. So the merge is:

new[i + j][0] = max over the child's either choice of (cur[i][0] + best child value for j)
new[i + j][1] = cur[i][1] + dp[x][j][0]

Here the child's count j is added to the count i already merged. The answer is the best value over all j at the root, for both c values.

The state that blows up is "the set of chosen employees so far", which has 2^n possibilities. The count j is what keeps the state small. A second blow-up is storing every array at its full subtree size: a chain of 2000 employees then needs about 2000 times 2000 merge steps, and that gets slow fast as n grows. Capping each array at min(subtree size, K) + 1 entries keeps the total merge work at O(n * K).

// Input: n K, then the n node weights, then n - 1 edges. Output the largest total weight of at most K nodes
// with no two chosen nodes adjacent.
// State: dp[v][j][c] = best weight inside the subtree of v when exactly j nodes are chosen,
// with c = 1 if v itself is chosen and c = 0 if it is not. Only j <= K is kept.
// Transition (merge child x into v): if v is chosen, the child must not be chosen;
// if v is not chosen, the child may be either way.
// Each array is capped at min(subtree size, K) + 1 entries, which keeps the total work at O(n * K).
#include <bits/stdc++.h>
using namespace std;
 
const long long NEG = LLONG_MIN / 4;
int n, K;
vector<long long> w;
vector<vector<int>> adj;
typedef vector<array<long long, 2>> DP;
 
DP dfs(int v, int p) {
    DP cur(min(1, K) + 1, array<long long, 2>{NEG, NEG});
    cur[0][0] = 0;
    if (K >= 1) cur[1][1] = w[v];
    for (int x : adj[v]) {
        if (x == p) continue;
        DP dc = dfs(x, v);
        int sz = min((int)cur.size() - 1 + (int)dc.size() - 1, K) + 1;
        DP nx(sz, array<long long, 2>{NEG, NEG});
        for (int i = 0; i < (int)cur.size(); i++)
            for (int j = 0; j < (int)dc.size(); j++) {
                if (i + j > K) break;
                long long anyc = max(dc[j][0], dc[j][1]);
                if (cur[i][0] > NEG && anyc > NEG) nx[i + j][0] = max(nx[i + j][0], cur[i][0] + anyc);
                if (cur[i][1] > NEG && dc[j][0] > NEG) nx[i + j][1] = max(nx[i + j][1], cur[i][1] + dc[j][0]);
            }
        cur = nx;
    }
    return cur;
}
 
int main() {
    scanf("%d %d", &n, &K);
    w.resize(n);
    for (int i = 0; i < n; i++) scanf("%lld", &w[i]);
    adj.assign(n, {});
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }
    DP root = dfs(0, -1);
    long long best = 0;
    for (auto &row : root) best = max(best, max(row[0], row[1]));
    printf("%lld\n", best);
    return 0;
}

Output on the sample: 10. Check it by hand: with K = 2 and weights 3 5 4 2 6, the best pair is employees 3 and 5 (weights 4 and 6). Employee 3 reports to 1 and employee 5 reports to 2, so they are not directly connected, and the total is 10. Other allowed pairs give less, for example 4 and 5 give 8 and 1 and 5 give 9. The brute force enumerates every subset of the 5 employees, keeps those with at most 2 members and no adjacent pair, and gets the same 10. The two agreed on 400 random trees with at most 10 employees.

Editorial D: bounded knapsack with copies

State: dp[x] is the best value with a total weight of at most x, over the item types handled so far. Transition: each copy of a type is a separate 0/1 item. For each copy, loop x from W down to w and set dp[x] = max(dp[x], dp[x - w] + v). Base case: dp[x] = 0 for all x. Answer: dp[W].

The state that blows up is "how many copies of each type", a vector of counts. There are (c + 1)^n such vectors, so with n = 100 and c = 100 there is no way to list them. The table over capacity avoids that. The work is O(n * c * W), which is 100 * 100 * 2000 = 2 * 10^7 steps at the limits.

// Input: n W, then n lines "w v c": weight, value and number of copies of each item type.
// Output the largest value of a bag whose total weight is at most W.
// State: dp[x] = best value found so far with a total weight of at most x.
// Transition: every copy is a separate 0/1 item. For each copy, go from x = W down to the item weight w
// and set dp[x] = max(dp[x], dp[x - w] + v). Going downward means one copy is used at most once.
// Work: O(n * c * W) with n item types, at most c copies each, capacity W.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, W;
    scanf("%d %d", &n, &W);
    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int w, c;
        long long v;
        scanf("%d %lld %d", &w, &v, &c);
        for (int k = 0; k < c; k++)
            for (int x = W; x >= w; x--) dp[x] = max(dp[x], dp[x - w] + v);
    }
    printf("%lld\n", dp[W]);
    return 0;
}

Output on the sample: 16, the same as the table in the section "The idea". The brute force tries every number of copies for every type and keeps the best feasible value. The two agreed on 400 random inputs with at most 3 types.

Editorial E: interval DP for removing pairs

State: f[l][r] is the most score from removing every character of s[l..r] completely, or -infinity if that is impossible. Transition: the character at l is removed with a partner at k, where k - l is odd and s[k] equals s[l]. Everything strictly between l and k must be removed first, which is f[l + 1][k - 1], and s[k + 1..r] is removed on its own, which is f[k + 1][r]. Base case: an empty segment has score 0.

After the full segments are known, a second table g[i] gives the best score for the first i characters. A character left on the board splits the string, because no pair may span it. So g[i] is either g[i - 1] (leave character i - 1) or g[j] + f[j][i - 1] for a fully removable segment that ends at i - 1.

The state that blows up is "the set of positions removed so far", which is a bitmask with 2^n values. The literal search in the brute force visits one bitmask per reachable set. I counted them with a version of the brute force that prints its memo size:

n = 8,  all letters 'a':  states visited 34
n = 12, all letters 'a':  states visited 233
n = 14, all letters 'a':  states visited 610
n = 16, all letters 'a':  states visited 1597

Each step of two extra letters multiplies the count by about 2.6, so the search cannot reach n = 200. Random strings look easier (10, 18 and 64 states for n = 8, 12 and 16), which is why the stress test needs the worst-case inputs too. The interval table needs O(n^2) entries and O(n^3) steps, about 8 * 10^6 at n = 200.

// Input: n, the string s of n lowercase letters, then 26 scores (score of a, b, ..., z).
// Rule: pick i < j with s[i] == s[j] and every position strictly between them already removed;
// remove both and gain the score of that letter. Output the largest total gain.
// State f[l][r] = the most score from removing every character of s[l..r] (-inf if that is impossible).
// Transition: the character at l is removed with a partner s[k] (same letter, k - l odd).
// Everything strictly between l and k must be removed first, and s[k+1..r] is removed on its own.
// g[i] = the best score for the first i characters; a character left on the board splits the string,
// because no pair may span it.
#include <bits/stdc++.h>
using namespace std;
 
const long long NEG = LLONG_MIN / 4;
int n;
string s;
long long sc[26];
vector<vector<long long>> f;
 
long long get(int l, int r) {
    if (l > r) return 0;
    return f[l][r];
}
 
int main() {
    cin >> n >> s;
    for (int i = 0; i < 26; i++) cin >> sc[i];
    f.assign(n + 1, vector<long long>(n + 1, NEG));
    for (int len = 2; len <= n; len += 2)
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            long long best = NEG;
            for (int k = l + 1; k <= r; k += 2) {
                if (s[k] != s[l]) continue;
                long long in = get(l + 1, k - 1), out = get(k + 1, r);
                if (in <= NEG || out <= NEG) continue;
                best = max(best, sc[s[l] - 'a'] + in + out);
            }
            f[l][r] = best;
        }
    vector<long long> g(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        g[i] = g[i - 1];
        for (int j = i - 2; j >= 0; j -= 2)
            if (f[j][i - 1] > NEG) g[i] = max(g[i], g[j] + f[j][i - 1]);
    }
    printf("%lld\n", g[n]);
    return 0;
}

Output on the sample: 7. The brute force searches over the set of removed positions with a memo, following the rule literally. The two agreed on 400 random strings of length 1 to 8 over the letters a, b and c.

Common mistakes

Mistakes 1 to 3 were reproduced by running the broken version on this machine (g++ 15.2.0 on Linux, with -O2 for the output lines and -fsanitize=address for the stack trace). The other two are checks to make before you submit.

Passing the wrong argument in a recursive walk. In the first draft of Editorial C, the child call was dfs(x, p), passing the parent of v instead of v. The walk then went back and forth between two vertices forever. The run failed with exit code 139 (segmentation fault), and AddressSanitizer reported stack-overflow with the dfs frame repeating. The fix is dfs(x, v). Catch it by running the sample by hand and reading the first recursive call.
Looping the wrong way in a 0/1 table. If the capacity loop in Editorial D runs upward, one copy can be used many times in one pass. The program prints 18 on the sample, where the correct answer is 16, because it has silently changed the bounded knapsack into an unbounded one. Catch it with the sample: the answer is bigger than any combination the counts allow.
Forgetting to sort before a greedy step. Kruskal's rule needs the roads in order of cost. Without the sort, the program takes roads in input order, 1-2 (cost 4), 1-3 (cost 2) and 3-4 (cost 7), and prints 13 on the sample of problem B, where the correct answer is 9 (roads 2-3, 1-3 and 2-4). Catch it with the sample and the brute force.
Overflow in a total. The weights reach 10^9 and there can be 200000 of them. Their sum is up to 2 * 10^14. Use long long for every total, including the answer of the DP.
Missing the "no answer" case. Problems A and B print -1 when the target cannot be reached. Test a disconnected graph by hand, and check the code path that prints -1.

Checklist

Write the state in one sentence before any code, and check it includes every count or value that the limit depends on.
Write the base case and the order in which entries are filled.
For a 0/1 table, check the loop direction. For copies, check that each copy is used once.
Use long long for every sum that can pass 2 * 10^9.
Compare the program with a brute force on at least 300 small random inputs, including the worst-case shapes such as all letters the same.
Count the states, and check that the count fits the limit before you write the loop.

Post-round log

Fill one line per problem right after the round, before you read the editorial. The log is how you find the state habits that cost you time.

Problem | solved (yes/no) | minutes used | state (one line) | transition (one line) | first wrong idea | bugs found
A       |                 |              |                  |                       |                  |
B       |                 |              |                  |                       |                  |
C       |                 |              |                  |                       |                  |
D       |                 |              |                  |                       |                  |
E       |                 |              |                  |                       |                  |

Read the log after three rounds. If the same type of state keeps being wrong, for example a count missing from a tree DP, practise that type first.

A stress loop for your own solutions

A stress loop generates random small inputs, runs your solution and the brute force on each, and reports any difference. This is the minimal version used to check problem E. Replace the generator for the other problems. It needs two programs: e_sol, the program in Editorial E, and e_brute, the brute force below.

// Brute force: depth-first search over the set of removed positions (a bitmask), following the rule literally.
#include <bits/stdc++.h>
using namespace std;
 
int n;
string s;
long long sc[26];
map<int, long long> memo;
 
long long go(int mask) {
    auto it = memo.find(mask);
    if (it != memo.end()) return it->second;
    long long best = 0;
    for (int i = 0; i < n; i++) {
        if ((mask >> i) & 1) continue;
        for (int j = i + 1; j < n; j++) {
            if (((mask >> j) & 1) || s[i] != s[j]) continue;
            bool ok = true;
            for (int k = i + 1; k < j; k++)
                if (!((mask >> k) & 1)) {
                    ok = false;
                    break;
                }
            if (ok) best = max(best, sc[s[i] - 'a'] + go(mask | (1 << i) | (1 << j)));
        }
    }
    memo[mask] = best;
    return best;
}
 
int main() {
    cin >> n >> s;
    for (int i = 0; i < 26; i++) cin >> sc[i];
    printf("%lld\n", go(0));
    return 0;
}

import random
import subprocess
 
rng = random.Random(42)
bad = 0
for t in range(300):
    n = rng.randint(1, 8)
    s = "".join(rng.choice("abc") for _ in range(n))
    txt = f"{n}\n{s}\n" + " ".join(str(rng.randint(1, 10)) for _ in range(26)) + "\n"
    a = subprocess.run(["./e_sol"], input=txt, capture_output=True, text=True, timeout=10).stdout.strip()
    b = subprocess.run(["./e_brute"], input=txt, capture_output=True, text=True, timeout=10).stdout.strip()
    bad += a != b
print("300 tests, mismatches:", bad)

Output on the machine used for this lesson: 300 tests, mismatches: 0.

Summary

Each problem in this round has one state that the limits can afford and one that they cannot. The coupon count, the count of chosen employees and the capacity are the values the answer depends on. The subset of roads, the subset of employees and the set of removed positions are the values that explode. The brute force is what tells you the difference, so run it on random small inputs before every submission.

Practice

Practice 1: change a coupon rule

Problem A changes so that a coupon halves the cost of a road, rounded down, instead of making it free. What changes in the state and in the transition?

Show the answer

The state stays dist[v][j], because the number of coupons used still limits the search. Only the cost of the coupon transition changes from 0 to w / 2 (integer division). One line in the program changes, and the complexity is the same.

Practice 2: Kruskal by hand

Four cities, four roads: 1-2 costs 3, 2-3 costs 1, 3-4 costs 2, 1-3 costs 4. Use Kruskal's rule to find the cheapest road network that connects all four cities.

Show the answer

Sorted by cost: 2-3 (1), 3-4 (2), 1-2 (3), 1-3 (4). Take 2-3, then 3-4, then 1-2, which joins city 1 to the group of cities 2, 3 and 4. The road 1-3 is skipped because 1 and 3 are already connected. The total is 1 + 2 + 3 = 6. The program prints 6 on this input.

Practice 3: tree DP with a limit of one

Use the sample of problem C with K changed to 1: weights 3 5 4 2 6 and the same four edges. What is the answer, and why?

Show the answer

The answer is 6. With K = 1 only one employee can be chosen, so the answer is the largest single weight, which is employee 5 with weight 6. The program prints 6.

Practice 4: knapsack with a smaller bag

Use the sample of problem D with W changed to 9. What is the answer? Which items does it use?

Show the answer

The answer is 16. One item of type 3 (weight 5, value 9) and one of type 1 (weight 4, value 7) fill weight 9 with value 16. The program prints 16.

Practice 5: interval DP on a pair string

Four letters, all the same: aabb, with every score equal to 1. Find the largest total gain.

Show the answer

Remove the pair of a letters at positions 1 and 2 for 1, then the pair of b letters at positions 3 and 4 for 1. The total is 2. The program prints 2, and so does the brute force.