Round 6: hard mix

Why this matters when you build with AI

On a hard problem, an AI tool often gives a confident greedy rule: "sort by profit and take the best one that still fits". The rule can pass the sample and still be wrong on a case with five items. The code looks finished, so the mistake is easy to miss. The fix is a proof of the rule, or a brute force check on small inputs. When the two disagree, the rule is wrong.

This round trains that check. Each problem has a brute force program that tries every answer on small inputs. Your solution is trusted only when it matches the brute force on many random small cases, and when you can explain why the key claim holds.

Use this prompt to get a plan from an AI tool. A good answer ranks the problems by expected value, names the claim each solution depends on, and gives a brute force plan for each.

I have 2 hours and five hard problems. Before any code, for each problem write:
1. The key claim the solution depends on, in one sentence.
2. A small case (n at most 6) where a wrong greedy would fail.
3. A brute force idea that checks the claim.
Then rank the problems by expected points per minute and say which two to attempt first.

Check the answer for two things. The claim must be something you can test, not "this is a standard trick". The small case must be real: write it down and trace it by hand before you trust the ranking.

The two-hour plan

The first ten minutes of the round are for a written plan. Do not start coding before it is done. The plan has four lines per problem:

Problem N: <short name>
Bet: attempt / skip / partial only
First idea and the claim it relies on:
Brute force I will write first:
Stop time (minutes from the start):

Use the stop time as the rule. If a problem has no working approach at its stop time, move on and come back only if time remains. A plan written in ten minutes will look like this for one problem:

Problem 2: unit jobs with profits
Bet: attempt. Expect the greedy to be right, but I will check it.
First idea: take jobs by profit, each into the latest free slot before its deadline.
Claim: the feasible job sets form a matroid, so the greedy is optimal.
Brute: try all subsets for n up to 8.
Stop: minute 45.

Techniques in this round

Each technique is defined here and used in one or more problems.

Exchange argument. To prove a greedy choice, show that any optimal answer can be changed, one swap at a time, into the greedy answer without losing value. For example, if an optimal answer uses a job with a lower profit where a higher one fits, swapping them does not reduce the total.

Matroid. A matroid is a family of sets with two properties: subsets of a feasible set are feasible, and when a smaller feasible set A is paired with a larger feasible set B, some element of B that is not in A can be added to A and stay feasible. For such a family, taking items in order of value and keeping each one that stays feasible gives the best total. Unit jobs with deadlines form one, shown in problem 2.

Penalty (the Aliens trick). Suppose you need exactly K special edges in a spanning tree, and you know the best cost as a function of K is convex, meaning the steps between neighbouring values never shrink. Then you can add a penalty lambda to every special edge, solve the easy unconstrained problem, and search for the lambda that makes K an optimal count. The name is informal. It is also called Lagrangian relaxation in the literature.

Möbius inversion for gcd. The Möbius function mu(d) takes values 1, -1 or 0. The identity sum over d dividing g of mu(d) equals 1 when g is 1 and 0 otherwise. This turns "count pairs with gcd exactly 1" into a sum over multiples.

Layered shortest path. When you may use at most K free edges, make one copy of the graph for each count of free edges used. Edges move a state from count j to count j or j + 1. Dijkstra on the copies is correct because all weights are non-negative.

Tree knapsack with a size cap. For a rooted tree, let dp[v][j] be the best value of a connected piece with root v and exactly j nodes. Merging children with a cap of K on the sizes gives O(n K) total work.

Worked problem: an exact-k cheap tree

Statement. You get a connected undirected graph with n nodes and m edges. Each edge has a weight w and a flag c, where c is 1 for a special edge and 0 otherwise. You also get K. Find the smallest total weight of a spanning tree (a set of n - 1 edges that connects all nodes with no cycle) that has exactly K special edges. Print -1 if no such tree exists.

Input. The first line has n, m and K. Each of the next m lines has u, v, w and c, with nodes numbered from 1.

Brute force. Try every set of n - 1 edges, keep the ones that form a tree with exactly K special edges, and take the smallest weight. This is correct and fits n up to 5 and m up to 7.

Method. Give each special edge a penalty lambda, so its effective cost is w + lambda. Run Kruskal's algorithm (sort edges by cost, add each edge that does not form a cycle) on the penalized costs. Let s(lambda) be the largest number of special edges in a tree that Kruskal can build when ties are broken in favour of special edges. As lambda grows, special edges get more expensive, so s(lambda) does not increase. Find the largest lambda with s(lambda) at least K, using binary search over integers. Then the answer is the penalized cost of the tree found at that lambda, minus lambda times K.

The code below does exactly this. Its run function returns the penalized cost, the true weight, the special count and whether the tree spans all nodes.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct Edge {
    int u, v;
    ll w;
    int c;  // 1 if the edge is special
};
 
int n, m;
ll K;
vector<Edge> es;
vector<int> par;
 
int findp(int x) { return par[x] == x ? x : par[x] = findp(par[x]); }
 
struct Res {
    ll pen;     // sum of w + lam * c over the tree
    ll trueW;   // sum of w over the tree
    int spec;   // number of special edges in the tree
    bool ok;    // true if the tree spans all nodes
};
 
// Kruskal with penalty lam on special edges. Ties go to special edges,
// so spec is the largest special count among minimum-penalty trees.
Res run(ll lam) {
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        ll pa = es[a].w + lam * es[a].c, pb = es[b].w + lam * es[b].c;
        if (pa != pb) return pa < pb;
        return es[a].c > es[b].c;
    });
    par.assign(n + 1, 0);
    iota(par.begin(), par.end(), 0);
    Res r{0, 0, 0, false};
    int taken = 0;
    for (int i : idx) {
        int a = findp(es[i].u), b = findp(es[i].v);
        if (a == b) continue;
        par[a] = b;
        r.pen += es[i].w + lam * es[i].c;
        r.trueW += es[i].w;
        r.spec += es[i].c;
        taken++;
    }
    r.ok = taken == n - 1;
    return r;
}
 
int main() {
    cin >> n >> m >> K;
    es.resize(m);
    for (auto& e : es) cin >> e.u >> e.v >> e.w >> e.c;
    const ll LIM = 2000002;  // larger than any weight difference, so the extremes are reached
    if (!run(0).ok) {
        cout << -1 << "\n";
        return 0;
    }
    // smax(lam) is non-increasing in lam. Find the largest lam with smax(lam) >= K.
    if (run(-LIM).spec < K || run(LIM).spec > K) {
        cout << -1 << "\n";
        return 0;
    }
    ll lo = -LIM, hi = LIM;
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1) / 2;
        if (run(mid).spec >= K) lo = mid;
        else hi = mid - 1;
    }
    Res best = run(lo);
    cout << best.pen - lo * K << "\n";
}

Sample input (saved as h1_ex1.txt), with K = 1:

Real output of the program:

The tree 1-2, 3-4, 2-3 has weight 1 + 1 + 2 = 4 and exactly one special edge (2-3). The same sample with K = 0 prints 6, and with K = 2 prints 6. The brute force program prints the same three values. I also compared the program with the brute force on 300 random graphs with up to 5 nodes, up to 7 edges, weights 0 to 10, and random K. All 300 matched.

The key claim. Let f(k) be the smallest weight of a spanning tree with exactly k special edges. The penalty method is correct when f is convex, meaning f(k - 1) + f(k + 1) is at least 2 f(k). I did not find a published source for this claim to cite, so treat the argument below as a sketch. I expect a matroid exchange argument gives it, but I did not verify that, and the random tests above support it on small graphs only. Do not rely on this sketch for a contest where the claim is part of the scoring. Prove it for your own version of the problem, or test it on small cases first.

Complexity. Each run sorts the edges, which is O(m log m). The binary search takes about 22 steps for lambda in the range, so the total is O(m log m log C), where C is the largest weight.

The timed set

Give yourself 120 minutes. Write the plan in the first 10 minutes. Stop on each problem at its stop time, and write a note on what you tried.

Problem 1: exact-k cheap tree. The statement is the worked problem above. Its sample is h1_ex1.txt. The sample output is 4.

Problem 2: unit jobs with profits. You get n jobs, where n is at most 2 * 10^5. Job i has a deadline d_i between 1 and n, and a profit p_i of at most 10^9. Each job takes one time slot, and a job must finish in a slot at most d_i. Choose a set of jobs that can all be scheduled, to maximise total profit.

Sample input:

Sample output:

Problem 3: coprime pairs. You get n values a_i, where n is at most 2 * 10^5 and each value is between 1 and 10^6. Count pairs of positions i < j with gcd(a_i, a_j) equal to 1.

Sample input:

6
1 2 3 4 5 6

Sample output:

Problem 4: one free road ride. You get a directed graph with n nodes and m edges, where n and m are at most 2 * 10^5. Each edge has a non-negative weight. You may use at most K free edges (K is at most 10), where a free edge costs 0 instead of its weight. Find the least total cost of a walk from node 1 to node n, or -1 if none exists.

Sample input:

Sample output:

Problem 5: connected pruning. You get a tree with n nodes, where n is at most 2 * 10^5, and K with 1 at most K at most n. Each node has a weight of at least 0. Choose a set of at most K nodes that contains node 1 and is connected, to maximise the total weight. Print the largest total.

Sample input:

Sample output:

Editorial

Problem 1: exact-k cheap tree

Use the penalty method from the worked problem. The code is the same. The stop rule: if your binary search does not agree with the brute force on the first small case, check the tie-break first, because the tie-break decides which special count the search sees.

Problem 2: a matroid greedy

Sort jobs by profit, highest first. For each job, put it in the latest free slot at or before its deadline. If no slot is free, skip it. The code uses a union-find structure where up[t] points to the latest free slot at or before t, with 0 meaning none.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> up;
int findslot(int x) { return up[x] == x ? x : up[x] = findslot(up[x]); }
int main() {
    int n;
    cin >> n;
    vector<pair<ll, int>> jobs(n);  // (profit, deadline)
    for (auto& j : jobs) cin >> j.second >> j.first;
    sort(jobs.begin(), jobs.end(), greater<pair<ll, int>>());
    up.resize(n + 1);
    iota(up.begin(), up.end(), 0);  // up[t] = latest free slot <= t, 0 means none
    ll total = 0;
    for (auto [p, d] : jobs) {
        int s = findslot(min(d, n));
        if (s == 0) continue;
        total += p;
        up[s] = s - 1;
    }
    cout << total << "\n";
}

Output on the sample: 75. The brute force program that tries all subsets gives the same output on 300 random inputs with up to 8 jobs.

Proof of the greedy. A set of jobs is feasible when, for every t, the number of jobs with deadline at most t is at most t. Call such sets independent. Two facts give the greedy.

First, the independent sets have the augmentation property. Let A and B be independent with |A| less than |B|. Let t1 be the largest t with exactly t jobs of A having deadline at most t, or t1 = 0 if there is none. For every t above t1, A has fewer than t jobs with deadline at most t, so adding one job with deadline above t1 cannot break any constraint. B has at most t1 jobs with deadline at most t1, because B is feasible. A has exactly t1 of them, so B has at least |B| - t1 jobs with deadline above t1, and A has at most |A| - t1 such jobs. Since |B| > |A|, B has more jobs above t1 than A does. So some job of B with deadline above t1 is not in A, and adding it keeps A feasible.

Second, when a family has the augmentation property, taking items in decreasing profit and keeping each one that keeps the set independent gives the largest total profit. Proof: let G be the greedy set and O an optimal set. Take the first item of G that is not in O and swap it into O along the augmentation property. The swap does not lower the profit, because the greedy item had the higher profit at that step. Repeating the swap turns O into G without losing profit, so G is optimal.

The DSU check decides independence: putting a job in the latest free slot at or before its deadline succeeds exactly when the current set plus this job stays feasible.

Complexity. Sorting dominates: O(n log n) with near-constant union-find work.

Problem 3: Möbius inversion

Let cnt[v] be how many a_i equal v. For each d, let S(d) be the number of values divisible by d. The pairs of positions whose values are both divisible by d are C(S(d), 2). By the identity for the Möbius function, the number of pairs with gcd exactly 1 is the sum over d of mu(d) times C(S(d), 2). The code builds mu with a linear sieve.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int M = 1;
    for (auto& x : a) { cin >> x; M = max(M, x); }
    vector<int> cnt(M + 1, 0);
    for (int x : a) cnt[x]++;
    // Linear sieve for the Mobius function up to M.
    vector<int> mu(M + 1, 0), primes;
    vector<bool> comp(M + 1, false);
    mu[1] = 1;
    for (int i = 2; i <= M; i++) {
        if (!comp[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if ((ll)p * i > M) break;
            comp[p * i] = true;
            if (i % p == 0) { mu[p * i] = 0; break; }
            mu[p * i] = -mu[i];
        }
    }
    ll ans = 0;
    for (int d = 1; d <= M; d++) {
        if (mu[d] == 0) continue;
        ll S = 0;  // how many values are divisible by d
        for (int v = d; v <= M; v += d) S += cnt[v];
        ans += mu[d] * (S * (S - 1) / 2);
    }
    cout << ans << "\n";
}

Output on the sample: 11. Check by hand: among the 15 pairs of 1 to 6, the four pairs (2,4), (2,6), (3,6) and (4,6) share a factor, so 11 remain. The brute force program agrees on 300 random inputs with values up to 30.

Timing: with n = 200000 and values up to 10^6, one run on this machine took about 0.22 seconds. Timings differ by machine.

Partial-credit idea: an O(n^2) double loop over pairs solves n up to about 3000. The stop rule: if the Möbius sum disagrees with the double loop on a small case, check the sieve first, because mu must be exactly -1, 0 or 1.

Problem 4: layered Dijkstra

Create one state per (node, free edges used). Every edge from node u at count j goes to node v at count j with cost w, or to count j + 1 with cost 0 when j is below K. Run Dijkstra on the states. Because all costs are non-negative, the first time a state is popped its distance is final.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, m, K;
    cin >> n >> m >> K;
    vector<vector<pair<int, ll>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u - 1].push_back({v - 1, w});
    }
    const ll INF = LLONG_MAX / 4;
    int S = K + 1;
    vector<ll> dist((size_t)n * S, INF);
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    dist[0] = 0;
    pq.push({0, 0, 0});  // (distance, node, used)
    while (!pq.empty()) {
        auto [d, u, j] = pq.top();
        pq.pop();
        if (d != dist[(size_t)u * S + j]) continue;
        for (auto [v, w] : g[u]) {
            // pay the full weight
            if (d + w < dist[(size_t)v * S + j]) {
                dist[(size_t)v * S + j] = d + w;
                pq.push({d + w, v, j});
            }
            // use one of the free edges
            if (j < K && d < dist[(size_t)v * S + j + 1]) {
                dist[(size_t)v * S + j + 1] = d;
                pq.push({d, v, j + 1});
            }
        }
    }
    ll best = INF;
    for (int j = 0; j <= K; j++) best = min(best, dist[(size_t)(n - 1) * S + j]);
    cout << (best == INF ? -1 : best) << "\n";
}

Output on the sample: 2. Check by hand: the route 1 to 3 is free (cost 0), then 3 to 4 costs 2, so the total is 2. The brute force program enumerates simple paths, paying or using a free edge for each step. It gives the same output on 300 random small graphs.

Why a simple path is enough for the brute force: all weights are non-negative, so cutting a cycle out of a walk never raises the cost or the number of free edges used.

Partial-credit idea: with K = 0 this is plain Dijkstra, which covers the subtask where no free edges are allowed. I ran the full program only, not the partial version.

Problem 5: tree knapsack

Root the tree at node 1. Let dp[v][j] be the largest total weight of a connected set with root v and exactly j nodes. Merging a child c into v takes the best of two options for each size: skip the child, or take j nodes from it. Cap the sizes at K. The code processes nodes from the leaves up using a BFS order, so no recursion is needed.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = LLONG_MIN / 4;
int main() {
    int n, K;
    cin >> n >> K;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }
    vector<ll> w(n);
    for (auto& x : w) cin >> x;
    // BFS order from the root, then process nodes in reverse so children come first.
    vector<int> order, parent(n, -1);
    order.reserve(n);
    vector<bool> seen(n, false);
    order.push_back(0);
    seen[0] = true;
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (!seen[v]) { seen[v] = true; parent[v] = u; order.push_back(v); }
    }
    // dp[v][j] = largest weight of a connected set with root v and exactly j nodes (1 <= j <= min(K, size)).
    vector<vector<ll>> dp(n);
    vector<int> sz(n, 1);
    for (int idx = n - 1; idx >= 0; idx--) {
        int v = order[idx];
        dp[v].assign(2, NEG);
        dp[v][1] = w[v];
        for (int c : adj[v]) {
            if (c == parent[v]) continue;
            int newSz = min(K, sz[v] + sz[c]);
            vector<ll> nd(newSz + 1, NEG);
            for (int x = 1; x <= min(sz[v], newSz); x++) nd[x] = dp[v][x];  // skip the child
            for (int x = 1; x <= min(sz[v], K); x++)
                for (int j = 1; j <= min(sz[c], newSz - x); j++)
                    nd[x + j] = max(nd[x + j], dp[v][x] + dp[c][j]);  // take j nodes from child c
            dp[v] = nd;
            sz[v] = min(K, sz[v] + sz[c]);
            vector<ll>().swap(dp[c]);  // free the child's table
        }
        sz[v] = (int)dp[v].size() - 1;
    }
    ll best = NEG;
    for (int j = 1; j < (int)dp[0].size(); j++) best = max(best, dp[0][j]);
    cout << best << "\n";
}

Output on the sample: 15, from the set {1, 3, 5} with weight 4 + 2 + 9. The brute force program tries every subset that contains the root, is connected and has at most K nodes. It gives the same output on 300 random trees with up to 9 nodes.

Why it runs in O(n K). Each merge of a part of size a with a part of size b costs about a times b steps, and sizes are capped at K. Charge each step to a pair of nodes that the merge joins. Each pair of nodes is joined at most once, and each merge with a cap of K costs at most K times the size of the smaller side. This sketch gives O(n K), which is the standard bound for this kind of tree knapsack. I did not measure it at the full limits.

Partial-credit idea: without the cap, the same DP runs in O(n^2) and covers n up to a few thousand. I did not test this partial version. Symptom of a bug in the full version: an answer that is too large when K is smaller than the best set, which means the cap check is missing.

Partial scores and when to stop

Each problem has a cheap partial solution. Write it first, because it is worth points and it gives you a brute-force-tested fallback. I tested only the full solutions, so the partial versions below are plans, not checked code.

Problem	Partial solution	Full solution
1	Kruskal on the non-special edges, for K = 0	penalty search
2	feasibility check per subset, n up to about 20	matroid greedy
3	double loop over pairs, n up to about 3000	Möbius sum
4	Dijkstra with K = 0	layered Dijkstra
5	DP without the size cap, n up to a few thousand	capped tree knapsack

Abandon a problem when all three hold: your brute force and your method disagree on a small case, you cannot find the wrong step within 15 minutes, and the stop time has passed. Then keep the partial solution and move on.

Common mistakes

A greedy without a proof. A rule that passes the sample can fail on a small case. Symptom: a wrong answer on a case with three items where two conflict. Fix: write the brute force first, and run it on random small inputs before you submit.

A tie-break that hides the special count. If the penalty search breaks ties toward non-special edges, the binary search sees the wrong count. Symptom: -1 for a feasible K, or an answer off by the penalty. Fix: break ties toward special edges, as the code does.

A slot off by one in the union-find. If up[s] is not set to s - 1, a slot is used twice. Symptom: the total counts two jobs in the same slot. Fix: check the sample by hand.

Negative modulo in the Möbius sum. mu is -1, 0 or 1. If you compute the sum with a modulus, a negative remainder shows up. Symptom: a negative count. Fix: keep the sum as a plain 64-bit integer. The answer counts pairs, so it is at most n(n - 1) / 2, about 2 * 10^10 for n = 2 * 10^5.

Dijkstra with a state that does not increase. If a free edge does not move the state to j + 1, the search can use unlimited free edges. Symptom: an answer that is too small. Fix: the state must increase by one for every free edge.

Tree DP without the cap. Forgetting to limit the sizes to K makes the table grow past K, which costs more time and can give wrong totals when K is smaller than the set you build. Symptom: time limit exceeded at n = 2 * 10^5.

Hands-on exercise

On your own machine, save the problem 2 code as h2.cpp, and the sample as h2.txt. Compile with g++ -std=c++17 -O2 -o h2 h2.cpp, then run ./h2 < h2.txt. Expect 75. Then write a brute force program that tries every subset, and compare the two on 200 random inputs with up to 8 jobs. Write down any input where they differ and trace the greedy by hand. Timings differ by machine.

Checklist

Write the plan in the first 10 minutes, with a stop time for each problem.
For each greedy rule, write the claim in one sentence and a small case that could break it.
Write a brute force program first, and use it on random small inputs.
For penalty searches, check the tie-break and check the search on a small K.
Keep a partial solution for every problem, and bank it before moving on.
Stop a problem when its stop time passes and the brute force still disagrees.

Practice problems

Practice 1: earliest slot or latest slot. Two jobs: A has deadline 2 and profit 5, and B has deadline 1 and profit 4. Taking jobs by profit, what total does each slot rule give, and which one is best?

Show the answer

The earliest-slot rule puts A in slot 1. B then needs a slot at or before 1, which is taken, so B is skipped. The total is 5. The latest-slot rule puts A in slot 2 and B in slot 1, for a total of 9. The best possible total is 9, so only the latest-slot rule is right.

Practice 2: coprime pairs by hand. For the values 2, 3, 4, 5, count the pairs with gcd 1 using the Möbius sum, then check by listing the pairs.

Show the answer

The pairs are (2,3), (2,5), (3,4), (3,5), (4,5). That is 5. In the sum, d = 1 gives mu(1) times C(4,2) = 6. d = 2 gives mu(2) times C(2,2) = -1, since 2 and 4 are the values divisible by 2. For d = 3 and d = 5, S(d) = 1, so C(1,2) = 0. For d = 4, mu(4) = 0. The total is 6 - 1 = 5.

Practice 3: free edges. In the sample graph of problem 4, what is the answer with K = 0?

Show the answer

With no free edges, the cheapest route from 1 to 4 is 1 to 3 (cost 4) then 3 to 4 (cost 2), total 6. The direct 1 to 2, 2 to 3 route costs 5 + 1 = 6 and then 3 to 4 adds 2, so it is 8. The answer is 6.

Practice 4: when the brute force is wrong. Name one way the brute force for problem 4 could be wrong, and how you would catch it.

Show the answer

If the brute force only tried paths that visit each node once, it would be correct for non-negative weights. If it allowed cycles without a visited check, it would loop forever. Catch it with a time limit on the brute force, and a check that the sample gives 2.

Summary

The hard round is about choosing which problems to attempt and checking each greedy or formula before trusting it. The plan takes ten minutes and sets a stop time for each problem. A matroid greedy needs an augmentation proof. A penalty search needs a convexity claim, which in this lesson is a sketch backed by brute force tests. Möbius inversion, layered shortest paths and capped tree DP each have a partial solution that is worth points.