USACO 2023 December · Platinum · all three problems

← Full December 2023 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec23results. Each problem heading links to the canonical statement on usaco.org. Code is my own reference C++ — cross-check the official editorial before trusting it under contest pressure.

Problem 1 — Cowntact Tracing

Statement

A tree on N cows. Some subset is currently infected (given). Infection spreads each night to all neighbours of infected cows. For each of Q query values k_j, output the minimum number of cows that could have been initially infected so that after exactly k_j nights the observed state is reached; or −1 if impossible.

Subtask structure

Inputs 4–5: N ≤ 10 (brute over all initial subsets).
Inputs 6–8: every cow is currently infected.
Inputs 9–11: N ≤ 400.
Inputs 12–23: full constraints.

Constraints

2 ≤ N ≤ 10⁵; 1 ≤ Q ≤ 20; 0 ≤ k_j ≤ N.
Time limit: 2s. Memory: 256 MB.

Key idea

For a fixed k, on a tree, a single initial source at vertex v explains exactly the closed k-neighbourhood B(v, k). The "infected" set S must be exactly the union of B(v_i, k) for some choice of initial sources; min #sources is a set-cover problem, but on a tree it's solvable greedily: root the tree, do DFS, at each node track the deepest uncovered descendant; when its depth forces a new source, place one and propagate coverage upward. The classical "minimum number of radius-k balls to cover all marked leaves" tree DP. Repeat for each query in O(N).

Complexity target

O(N · Q) = 2×10⁶. With Q ≤ 20 this is trivial in time; the trick is feasibility check (B(v, k) must stay inside the infected set — no healthy cow within radius k of an initial source).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;

int N, Q;
vector<vector<int>> G;
vector<int> inf;          // 1 if infected, 0 if not

// For a given k: greedy tree-DP. State per node = "deepest uncovered infected
// descendant" (distance from this node), or +inf if all covered. If that distance
// hits k, we MUST place a source here, covering up to k upward. If a node is
// healthy but is within k of any source/uncovered descendant, infeasible.

int K;
int sources;
bool feasible;

// returns: minimum "uncovered distance" of an infected node in subtree(u) that
//   still needs to be covered; or +INF if all already covered; or -INF as a flag
//   that subtree(u) is already covered up to distance (sources radius) above.
int dfs(int u, int parent) {
    int maxUnc = INT_MIN;   // deepest uncovered infected descendant distance
    int minCov = INT_MAX;   // closest "covered" radius reaching into u
    for (int v : G[u]) if (v != parent) {
        int r = dfs(v, u);
        if (r >= 0) maxUnc = max(maxUnc, r + 1);
        else        minCov = min(minCov, -r - 1 + 1);
    }
    if (inf[u]) maxUnc = max(maxUnc, 0);
    // If the closest cover reaches u, it covers everything within (K - minCov) of u.
    if (minCov <= K && maxUnc != INT_MIN && maxUnc + minCov <= K) {
        maxUnc = INT_MIN; // all in subtree already covered
    }
    if (maxUnc == K) {
        ++sources;
        // Verify the K-ball from here stays within infected set:
        // (omitted feasibility BFS — done separately).
        // Mark covered: return -(K) - 1 to signal "covered with K remaining radius".
        return -(K) - 1;
    }
    if (maxUnc != INT_MIN) return maxUnc;
    if (minCov != INT_MAX) return -(K - minCov) - 1;
    return INT_MAX / 2; // nothing to report
}

int solve(int k) {
    K = k;
    // Feasibility: every healthy cow must be at distance > k from every initial
    // source. Equivalently, the chosen K-balls must cover all infected and avoid
    // all healthy. Use multi-source BFS from healthy cows: if every "internal"
    // infected cow has a healthy neighbour within distance k, then no source
    // can be placed without contaminating a healthy cow ⇒ −1.
    // (Implementation omitted for brevity — see editorial.)  // [verify]
    sources = 0; feasible = true;
    dfs(0, -1);
    return feasible ? sources : -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    G.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        G[u].push_back(v); G[v].push_back(u);
    }
    inf.assign(N, 0);
    string s; cin >> s;
    for (int i = 0; i < N; ++i) inf[i] = (s[i] == '1');
    cin >> Q;
    while (Q--) {
        int k; cin >> k;
        cout << solve(k) << "\n";
    }
}

Pitfalls

Feasibility is the hard half. The greedy gives a number, but you must independently check that no chosen K-ball includes a healthy cow. Skip this and you'll output a positive number on infeasible cases.
k = 0 is special. Answer is popcount(infected) if feasible, else −1.
Stack depth. N = 10⁵; recursive DFS may overflow the default stack on Codeforces-like judges — USACO is fine but use an iterative DFS for safety.
Re-rooting is unnecessary; any root works since you're covering with balls of fixed radius.

Problem 2 — A Graph Problem

Statement

Connected undirected graph with N vertices and M edges, edges labeled 1..M. For each starting vertex s, simulate: S := {s}; repeatedly find the minimum-label edge with exactly one endpoint in S, add its other endpoint to S, append its label. After all N − 1 steps, you have a sequence of N − 1 labels; concatenate them (treat them as written-out base-10 numbers? Or as digits? — ) and report the result mod 10⁹+7. Output one value per starting vertex.

Subtask structure

Input 4: N, M ≤ 2000.
Inputs 5–6: N ≤ 2000.
Inputs 7–10: N ≤ 10⁴.
Inputs 11–14: linear graph (path).
Inputs 15–23: full constraints.

Constraints

2 ≤ N ≤ 2×10⁵, N−1 ≤ M ≤ 4×10⁵.
Time limit: 2s.

Key idea

The process is exactly Prim's MST starting from s with edge-label as weight. Because labels are 1..M distinct, the MST is unique and the order in which Prim adds edges from s is deterministic. Trick: the multiset of edges added is the same MST for every starting vertex — only the order differs. Use Borůvka / Kruskal to build the MST tree T once. For each vertex s, the order of edges added is a deterministic priority-DFS of T rooted at s; the sequence is recoverable from the structure of the MST. Aggregate with small-to-large merging on a treap-like structure that stores the concatenation hash mod p; total O((N + M) α(N) log N).

Complexity target

O((N + M) log N) for MST + O(N log N) for all-source hash via DSU-on-tree merging.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007;

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a; if (r[a] == r[b]) ++r[a];
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<tuple<int,int,int>> edges(M); // (label, u, v) — labels = 1..M, sorted already
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        edges[i] = {i + 1, u, v};
    }
    // Build MST (labels are the ascending weights).
    DSU dsu(N);
    vector<vector<pair<int,int>>> mst(N); // (neighbour, label)
    for (auto [w, u, v] : edges)
        if (dsu.unite(u, v)) { mst[u].push_back({v, w}); mst[v].push_back({u, w}); }

    // For each starting vertex s, BFS-Prim through the MST: at each step pick the
    // globally-cheapest crossing edge — but in the MST that's just walking edges
    // in ascending-label order from s's component. Equivalent to DSU-merge order.
    //
    // Output via offline Boruvka-style merge: maintain per-component hash of
    // label sequence; when merging components via the smallest edge between
    // them, both components' hashes mix.  // [verify exact merge semantics]
    //
    // Skeleton output (replace with full hash merging for AC):
    for (int s = 0; s < N; ++s) {
        // Tiny version: priority-queue Prim from s on the MST only.
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        vector<char> seen(N, 0);
        seen[s] = 1;
        for (auto [v, w] : mst[s]) pq.push({w, v});
        ll hash_ = 0;
        while (!pq.empty()) {
            auto [w, u] = pq.top(); pq.pop();
            if (seen[u]) continue;
            seen[u] = 1;
            // Treat label w as a decimal block of length floor(log10(w))+1.
            int digits = 0; ll t = w;
            while (t) { ++digits; t /= 10; }
            ll pw = 1;
            for (int i = 0; i < digits; ++i) pw = pw * 10 % MOD;
            hash_ = (hash_ * pw + w) % MOD;
            for (auto [v, ww] : mst[u]) if (!seen[v]) pq.push({ww, v});
        }
        cout << hash_ << "\n";
    }
    // O(N^2 log N) — passes the small subtasks. Full credit needs the offline
    // DSU-merge with linked-list hash concatenation. [verify editorial]
}

Pitfalls

Exact "concatenation" semantics. The PDF likely defines a specific way to interleave labels into a base-10 number; off-by-one on digit count or modular exponent is fatal.
Reusing Prim per vertex is O(N · M log N) — fits the partial subtasks but TLEs the full N=2×10⁵.
DSU-merge insight. Two components merge along the unique smallest crossing edge; that edge appears at the same "step number" for every starting vertex inside either component — this is the key to the offline solution.
Modular inverse not needed if you build the hash forward; if you go backward, precompute inverses of 10^k.

Problem 3 — Train Scheduling

Statement

A single track connects stations A and B; traversal takes T time, and at most one direction can use the track at any moment. N trains are given; train i wants to depart from station s_i ∈ {A, B} at the earliest at time t_i. You may delay each train (never make it earlier); pick actual departure times so that no two trains going opposite directions ever share the track. Minimize the total delay Σ (actual − t_i).

Subtask structure

Inputs 5–6: N ≤ 15 (bitmask DP).
Inputs 7–10: N ≤ 100.
Inputs 11–14: N ≤ 500.
Inputs 15–18: N ≤ 2000.
Inputs 19–24: N ≤ 5000.

Constraints

1 ≤ N ≤ 5000; 1 ≤ T ≤ 10¹²; 0 ≤ t_i ≤ 10¹².
Time limit: 2s. Memory: 512 MB (double default).

Key idea

Sort each direction's trains by t. Within a direction, never re-order (swapping doesn't help and only forces extra delay). The schedule alternates "A-batch, B-batch, A-batch, …": once a train departs at time τ in direction d, no train in the opposite direction can depart in [τ, τ + T]. DP over (i, j, dir): we've scheduled the first i A-trains and first j B-trains, the most recent train was in direction dir at the earliest valid time. State count O(N²); transition decides whether to extend the current batch or flip direction. Min total delay over all states with i = nA, j = nB.

Complexity target

O(N²) states, O(1) transitions = 2.5×10⁷. Memory O(N²) of 64-bit = 200 MB — hence the 512 MB cap.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; ll T; cin >> N >> T;
    vector<ll> tA, tB;
    for (int i = 0; i < N; ++i) {
        int s; ll t; cin >> s >> t;
        if (s == 0) tA.push_back(t); else tB.push_back(t);
    }
    sort(tA.begin(), tA.end());
    sort(tB.begin(), tB.end());
    int nA = tA.size(), nB = tB.size();

    // dp[i][j][d] = (min total delay, earliest-time-when-direction-d-batch-ends)
    // Compressed: store just min delay; the batch-end time is determined by
    // (last batch direction, last-train-index, T).
    //
    // For brevity, we encode just the delay; reconstruct times on the fly.
    // dp[i][j] = min delay having scheduled i A-trains and j B-trains, with
    // some last-batch info. Two layers for d ∈ {A, B}.

    vector<vector<array<ll, 2>>> dp(nA + 1, vector<array<ll, 2>>(nB + 1, {INF, INF}));
    // lastEnd[i][j][d] = end-of-track time of the most recent train in direction d
    vector<vector<array<ll, 2>>> last(nA + 1, vector<array<ll, 2>>(nB + 1, {0, 0}));
    // Base cases:
    dp[0][0][0] = dp[0][0][1] = 0;

    for (int i = 0; i <= nA; ++i)
        for (int j = 0; j <= nB; ++j)
            for (int d = 0; d < 2; ++d) {
                if (dp[i][j][d] == INF) continue;
                ll endTime = last[i][j][d];
                // Continue same direction: take next A or B if d == 0/1.
                if (d == 0 && i < nA) {
                    ll dep = max(tA[i], endTime); // back-to-back A is fine
                    ll cand = dp[i][j][d] + (dep - tA[i]);
                    if (cand < dp[i + 1][j][0]) {
                        dp[i + 1][j][0] = cand;
                        last[i + 1][j][0] = dep + T;
                    }
                } else if (d == 1 && j < nB) {
                    ll dep = max(tB[j], endTime);
                    ll cand = dp[i][j][d] + (dep - tB[j]);
                    if (cand < dp[i][j + 1][1]) {
                        dp[i][j + 1][1] = cand;
                        last[i][j + 1][1] = dep + T;
                    }
                }
                // Flip direction: next train must wait endTime.
                if (d == 0 && j < nB) {
                    ll dep = max(tB[j], endTime);
                    ll cand = dp[i][j][d] + (dep - tB[j]);
                    if (cand < dp[i][j + 1][1]) {
                        dp[i][j + 1][1] = cand;
                        last[i][j + 1][1] = dep + T;
                    }
                }
                if (d == 1 && i < nA) {
                    ll dep = max(tA[i], endTime);
                    ll cand = dp[i][j][d] + (dep - tA[i]);
                    if (cand < dp[i + 1][j][0]) {
                        dp[i + 1][j][0] = cand;
                        last[i + 1][j][0] = dep + T;
                    }
                }
            }
    cout << min(dp[nA][nB][0], dp[nA][nB][1]) << "\n";
    // [verify: full-credit may need an exchange-argument observation that
    //  reduces to O(N log N) or a convex 1D DP — N ≤ 5000 suggests N²
    //  with cheap states is the intended complexity.
}

Pitfalls

Times up to 10¹². 64-bit everywhere; total delay up to 5·10¹⁶, still fits.
"Back-to-back same direction" is free. A train going A can leave immediately after the previous A train (no track conflict). Only the opposite direction has to wait for T.
Sorting per direction is mandatory. Swapping two same-direction trains never reduces delay (classical exchange argument).
Memory. 5001 × 5001 × 2 × 8 bytes ≈ 400 MB — must compress; in practice store only the dp + last as two arrays each, not as vector<vector<array>>.
"Flip direction" cost is precisely making the new train wait until the previous batch's last train clears the track, i.e. its departure + T.

What Platinum December 2023 was actually testing

P1 — radius-k cover on a tree. Greedy DFS for the count; separate BFS for feasibility.
P2 — Prim ≡ MST. Recognize the procedure as MST construction and merge component hashes offline.
P3 — interval-batched scheduling DP. N ≤ 5000 announces "N² states, simple transition"; the 512 MB memory cap is the giveaway.