USACO 2019 December · Gold · all three problems

← Full December 2019 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec19results. 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 — Milk Pumping

Statement

A directed/undirected weighted graph on N nodes and M edges. Each edge has a cost c and a capacity f. Find a path from 1 to N maximizing (min edge capacity along the path) / (sum of edge costs along the path). Output ⌊10⁶ · max ratio⌋.

Constraints

2 ≤ N ≤ 1000, 1 ≤ M ≤ 1000.
1 ≤ c, f ≤ 1000.
Time limit: 2s.

Key idea

Enumerate the candidate "bottleneck" capacity f* by trying each edge's capacity. For each f*, run Dijkstra from 1 to N using only edges with capacity ≥ f*; the shortest cost-path gives candidate ratio f* / dist[N]. Maximize across all M candidates.

Complexity target

O(M · (N + M) log N). With N, M ≤ 1000, ~10⁷ log — comfortable.

Reference solution (C++)

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

int N, M;
struct E { int v, c, f; };
vector<E> G[1005];

ll dijkstra(int minF) {
    vector<ll> dist(N + 1, LLONG_MAX);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[1] = 0; pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto& e : G[u]) if (e.f >= minF) {
            ll nd = d + e.c;
            if (nd < dist[e.v]) { dist[e.v] = nd; pq.push({nd, e.v}); }
        }
    }
    return dist[N];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    vector<int> caps;
    for (int i = 0; i < M; ++i) {
        int a, b, c, f; cin >> a >> b >> c >> f;
        G[a].push_back({b, c, f});
        G[b].push_back({a, c, f});
        caps.push_back(f);
    }
    ll bestNum = 0, bestDen = 1;
    for (int f : caps) {
        ll d = dijkstra(f);
        if (d == LLONG_MAX) continue;
        // Compare f/d vs bestNum/bestDen using cross-multiply (positive values).
        if ((ll)f * bestDen > bestNum * d) { bestNum = f; bestDen = d; }
    }
    cout << (1000000LL * bestNum) / bestDen << "\n";
}

Pitfalls

Enumerate over edge capacities, not all f from 1..1000. The optimum f* is always realized by an edge.
Floor, not round. Integer division 10⁶·num/den already floors for positive ints.
Edges are undirected (push both directions).
Don't binary-search the ratio. Direct enumeration is simpler and fast enough.

Problem 2 — Milk Visits

Statement

Gold version of Silver's Milk Visits. Now each node has one of up to N milk types (arbitrary integers), and queries (a, b, c) again ask whether the path from a to b contains a node of type c.

Constraints

1 ≤ N, M ≤ 10⁵.
1 ≤ t_i, c ≤ N.
Time limit: 2s.

Key idea

Offline by query. For each type t, run DSU only over edges where at least one endpoint has type t (or equivalently, root each query at the closer endpoint and small-to-large merge node sets by type). A clean approach: process the tree with Euler tour + sets-per-node and, at each query, check whether any ancestor of LCA(a,b) ... actually simplest: for each query (a, b, c), the answer is yes iff a's nearest ancestor of type c is on the a-LCA-b path, or b's nearest ancestor of type c is on that path. Implement using offline DFS with a per-type stack and persistent "last seen depth" per type.

Complexity target

O((N + M) log N) with LCA + offline per-type tracking.

Reference solution (C++)

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

const int MAXN = 100005;
int N, M, t[MAXN], par[MAXN][17], dep[MAXN];
vector<int> adj[MAXN];

// queries grouped by both endpoints; for each query (a,b,c) we need to know
// the deepest ancestor of a of type c (call it Ac) and deepest ancestor of b
// of type c (Bc). Answer is yes iff Ac or Bc has depth >= depth(LCA(a,b)).
struct Q { int b, c, id; };
vector<Q> qa[MAXN];   // queries indexed by their 'a' endpoint
vector<Q> qb[MAXN];   // by 'b'
int lcaOf[MAXN];      // precomputed per query
int ansDepthA[MAXN], ansDepthB[MAXN];
int curDepthOfType[MAXN];  // current deepest ancestor depth of each type
vector<int> stkPrev[MAXN]; // not used; we restore on exit

void dfs(int u, int p, int d) {
    par[u][0] = p; dep[u] = d;
    int saved = curDepthOfType[t[u]];
    curDepthOfType[t[u]] = d;
    for (auto& q : qa[u]) ansDepthA[q.id] = curDepthOfType[q.c];
    for (auto& q : qb[u]) ansDepthB[q.id] = curDepthOfType[q.c];
    for (int v : adj[u]) if (v != p) dfs(v, u, d + 1);
    curDepthOfType[t[u]] = saved;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < 17; ++k) if (diff >> k & 1) u = par[u][k];
    if (u == v) return u;
    for (int k = 16; k >= 0; --k)
        if (par[u][k] != par[v][k]) { u = par[u][k]; v = par[v][k]; }
    return par[u][0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) cin >> t[i];
    for (int i = 0; i < N - 1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    vector<tuple<int,int,int>> Q(M);
    for (int i = 0; i < M; ++i) {
        auto& [a, b, c] = Q[i];
        cin >> a >> b >> c;
        qa[a].push_back({b, c, i});
        qb[b].push_back({a, c, i});
    }
    dfs(1, 0, 0);
    for (int k = 1; k < 17; ++k)
        for (int v = 1; v <= N; ++v) par[v][k] = par[par[v][k - 1]][k - 1];
    string ans;
    for (int i = 0; i < M; ++i) {
        auto [a, b, c] = Q[i];
        int L = lca(a, b);
        bool ok = ansDepthA[i] >= dep[L] || ansDepthB[i] >= dep[L];
        ans += ok ? '1' : '0';
    }
    cout << ans << "\n";
}

Pitfalls

Iterative DFS may be needed at N = 10⁵ to avoid stack overflow; recursive works if you bump stack size or compile with -O2 + larger stacks.
"Deepest ancestor of type c" is computed at the moment we visit each query endpoint, not after the subtree — save/restore the per-type depth around the DFS frame.
Check both endpoints. Type c may appear on a-to-LCA but not b-to-LCA or vice versa.
Self-LCA edge case. If a == b the path is one node; just compare t[a] to c.

Problem 3 — Moortal Cowmbat

Statement

String S of length N over an alphabet of 26 letters. A 26×26 cost matrix gives the cost to change letter i to letter j (not necessarily symmetric, but transitive in the "shortest-path" sense via Floyd–Warshall). Rewrite S into a string where every maximal run has length ≥ K, minimizing total change cost.

Constraints

1 ≤ N ≤ 10⁵, 1 ≤ K ≤ N.
Cost matrix entries in [0, 10³].
Time limit: 2s.

Key idea

First run Floyd–Warshall on the 26×26 matrix so cost[a][b] is the cheapest way to morph a into b. For each letter c precompute prefix sums P_c[i] = total cost to convert S[0..i−1] to all c. Let f(i, c) = minimum cost to rewrite S[0..i] such that S[i] is part of a final c-run that ends at i. Then f(i, c) = min(f(i − K, c), min over c' ≠ c of best(i − K, c')) + (P_c[i+1] − P_c[i+1−K]), where best(j, c') = min_{j' ≤ j} f(j', c'). Maintain prefix mins of f per letter as you sweep i.

Complexity target

O(26³ + N · 26) ≈ 2.6 · 10⁶.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, K; cin >> N >> M >> K; // M = 26 typically
    string s; cin >> s;
    vector<vector<ll>> c(M, vector<ll>(M));
    for (int i = 0; i < M; ++i) for (int j = 0; j < M; ++j) cin >> c[i][j];
    for (int k = 0; k < M; ++k) for (int i = 0; i < M; ++i) for (int j = 0; j < M; ++j)
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

    // P[ch][i] = cost to convert s[0..i-1] entirely to ch.
    vector<vector<ll>> P(M, vector<ll>(N + 1, 0));
    for (int ch = 0; ch < M; ++ch)
        for (int i = 0; i < N; ++i) P[ch][i + 1] = P[ch][i] + c[s[i] - 'a'][ch];

    // f[i][ch] = min cost so position i (0-indexed, last) ends a run of ch.
    // prefMin[i][ch] = min over j<=i of f[j][ch] (run can extend past length K).
    // Recurrence: f[i][ch] = (cost convert s[i-K+1..i] to ch) +
    //                        min(prefMin[i-K][ch],   // extend an existing ch run
    //                            min_{c'!=ch} prefMin[i-K][c']); // start fresh
    vector<vector<ll>> f(N, vector<ll>(M, INF));
    vector<vector<ll>> pm(N, vector<ll>(M, INF));
    for (int i = K - 1; i < N; ++i) {
        for (int ch = 0; ch < M; ++ch) {
            ll segCost = P[ch][i + 1] - P[ch][i + 1 - K];
            ll best = INF;
            if (i - K < 0) {
                if (i + 1 == K) best = 0;        // first K characters form the first run
            } else {
                // extend ch run: prefMin[i-K][ch] (allowing run started anywhere <= i-K)
                best = pm[i - K][ch];
                // start fresh after a different letter ending at <= i-K
                for (int c2 = 0; c2 < M; ++c2) if (c2 != ch)
                    best = min(best, pm[i - K][c2]);
            }
            if (best < INF) f[i][ch] = best + segCost;
        }
        for (int ch = 0; ch < M; ++ch) {
            // also allow continuing the current ch run by one more char (cost to convert s[i] to ch).
            if (i > 0 && f[i - 1][ch] < INF)
                f[i][ch] = min(f[i][ch], f[i - 1][ch] + c[s[i] - 'a'][ch]);
            pm[i][ch] = (i ? min(pm[i - 1][ch], f[i][ch]) : f[i][ch]);
        }
    }
    ll ans = INF;
    for (int ch = 0; ch < M; ++ch) ans = min(ans, f[N - 1][ch]);
    cout << ans << "\n";
}

Pitfalls

Floyd–Warshall first. The naive cost[i][j] is not the real cheapest morph; an A→B detour through C can be cheaper.
Two transitions matter. "Append one more c" (cost c[s[i]][c]) and "start a fresh c-run of length K" (segment cost). Forgetting either gives WA.
Prefix-min per letter makes the "start fresh" min O(26) per i, not O(N · 26).
K can equal N. Make sure i + 1 == K base case (whole string becomes one run) is allowed.

What Gold December 2019 was actually testing

P1 — enumerate the bottleneck, Dijkstra on the rest. Classic "fractional objective" trick.
P2 — offline tree queries with LCA + per-type ancestor tracking. Generalizing Silver's DSU to many types.
P3 — DP with prefix mins. Floyd–Warshall on the alphabet + run-length DP with sliding minima.