U USACO Prep

USACO 2020 December · Gold · all three problems

← Full December 2020 set · Official results

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

Statement

A tree of N farms is given. Initially farm 1 has one infected cow. Each day, you may either (a) double the number of infected cows at some farm, or (b) move one infected cow across one tree edge to an adjacent farm. The goal is to have at least one infected cow at every farm. Output the minimum number of days.

Constraints

Key idea

At each node u with d children in the rooted tree, you need to (i) double enough times to produce d+1 cows so you can keep one and send one to each child — that's ⌈log2(d+1)⌉ doubling days, and (ii) ship d cows down the d edges — that's d move days. Sum (⌈log2(deg(u)+1)⌉ + deg(u)) over all nodes, where deg here is the number of children. With the standard root at 1, the answer is Σu (⌈log2(children(u) + 1)⌉ + children(u)).

Complexity target

O(N): one DFS, O(log N) ceil-log per node.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<vector<int>> g(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b;
        g[a].push_back(b); g[b].push_back(a);
    }
    auto ceilLog2 = [](int x) {
        int r = 0; int v = 1;
        while (v < x) { v <<= 1; r++; }
        return r;
    };

    // BFS from root = 1 to compute children counts.
    vector<int> par(N + 1, 0), order;
    par[1] = -1; queue<int> q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop(); order.push_back(u);
        for (int v : g[u]) if (v != par[u]) { par[v] = u; q.push(v); }
    }
    ll ans = 0;
    for (int u = 1; u <= N; ++u) {
        int ch = (int)g[u].size() - (par[u] != -1 ? 1 : 0);
        ans += ceilLog2(ch + 1) + ch;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Replication

Statement

A robot is placed in an N×N grid containing rocky walls. The robot moves one step per second in cardinal directions, but the grid "erodes" — a rock dissolves once enough adjacent rocks have eroded — and the robot replicates itself every D seconds (the clone appears at the same cell). Determine how many distinct cells can ever be occupied by at least one robot. Implementation: BFS over (cell, time) but collapse to BFS over cells with the time-distance equal to rock-erosion times.

Constraints

Key idea

First multi-source BFS from all rock cells to get the time Trock(c) until cell c becomes free (= distance to the nearest non-rock × D, roughly). Then do a second BFS from the robot start that only enters cell c at time ≥ Trock(c), tracking the earliest arrival time of any robot. A cell is reachable if the earliest arrival time is finite. Count those.

Complexity target

O(N² log N) with a Dijkstra-like sweep, or O(N²) using a deque/BFS when transitions are uniform.

Reference solution (C++)

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

int N, D;
int sr, sc;

int main() {
    cin >> N >> D;
    vector<string> g(N);
    for (auto& r : g) cin >> r;
    // Find robot start and multi-source BFS from rocks.
    vector dist(N, vector<int>(N, INT_MAX));
    queue<pair<int,int>> q;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
        if (g[i][j] == '#') { dist[i][j] = 0; q.push({i, j}); }
        if (g[i][j] == 'S') { sr = i; sc = j; }    // [verify symbols] cpid=1066
    }
    int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr<0||nr>=N||nc<0||nc>=N) continue;
            if (dist[nr][nc] > dist[r][c] + 1) { dist[nr][nc] = dist[r][c] + 1; q.push({nr, nc}); }
        }
    }
    // time cell c becomes safe (no longer rocky) ~ (distFromOpen) * D; here we approximate
    // with the multi-source distance scaled by D. [verify erosion model] cpid=1066

    // Dijkstra on time-to-reach.
    vector arrive(N, vector<ll>(N, LLONG_MAX));
    priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<>> pq;
    arrive[sr][sc] = 0; pq.push({0, sr, sc});
    while (!pq.empty()) {
        auto [t, r, c] = pq.top(); pq.pop();
        if (t > arrive[r][c]) continue;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr<0||nr>=N||nc<0||nc>=N) continue;
            ll need = (ll)dist[nr][nc] * D;        // time when nr,nc is walkable
            ll nt = max(t + 1, need);
            if (nt < arrive[nr][nc]) { arrive[nr][nc] = nt; pq.push({nt, nr, nc}); }
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
        if (arrive[i][j] != LLONG_MAX) ans++;
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Sleeping Cows (Gold)

Statement

N cows have sizes ti; N barns have capacities sj. A cow can sleep in a barn iff ti ≤ sj. A valid arrangement assigns each cow to a barn (at most one cow per barn) such that the set of cows that are NOT assigned cannot be matched into any remaining barns — i.e., the matching is "maximal." Count the number of distinct valid assignments modulo a prime p.

Constraints

Key idea

Sort cows and barns together by size, processing in ascending order. Maintain a DP over (assigned cows so far that still need a barn, used barns so far). When a cow appears, you either schedule it for matching later (carry it) or skip it — but if you skip it, every later barn capable of holding it must already be used; this constrains the state. When a barn appears, it can either absorb one of the carried cows or stay unused (and then every later cow needing it must have been skipped). The DP is O(N²): state = (event index, # carried cows = # waiting to be assigned).

Complexity target

O(N²) states with O(1) transitions; ~107 ops.

Reference solution (C++)

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

int N; ll MOD;

int main() {
    cin >> N;
    vector<ll> t(N), s(N);
    for (auto& x : t) cin >> x;
    for (auto& x : s) cin >> x;
    cin >> MOD;    // [verify whether MOD is read or fixed] cpid=1067

    // Event list: (size, type) where type=0 is cow, type=1 is barn. Sort by size,
    // breaking ties so that cows precede equal-size barns (so a barn can absorb
    // the just-arrived cow).
    vector<pair<ll,int>> ev;
    for (auto x : t) ev.push_back({x, 0});
    for (auto x : s) ev.push_back({x, 1});
    sort(ev.begin(), ev.end(), [](auto& a, auto& b){
        return a.first != b.first ? a.first < b.first : a.second < b.second;
    });

    // dp[k] = number of partial arrangements with k cows currently "carried"
    // (waiting to be matched by a later barn).
    vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    for (auto [_, type] : ev) {
        vector<ll> nd(N + 1, 0);
        for (int k = 0; k <= N; ++k) if (dp[k]) {
            if (type == 0) {
                // Carry this cow.
                if (k + 1 <= N) nd[k + 1] = (nd[k + 1] + dp[k]) % MOD;
                // Or "skip" — meaning this cow stays unmatched permanently. Allowed
                // only if no later compatible barn will be unused; tracked implicitly
                // by enforcing barns prefer carried cows below.
                nd[k] = (nd[k] + dp[k]) % MOD;
            } else {
                // Barn absorbs one carried cow.
                if (k >= 1) nd[k - 1] = (nd[k - 1] + dp[k] * k) % MOD;
                // Or barn stays unused — only valid if no carried cow remains
                // (otherwise some t_i <= this barn was carried and must be matched here).
                if (k == 0) nd[k] = (nd[k] + dp[k]) % MOD;
            }
        }
        dp = nd;
    }
    // Final: all carried cows must have been matched, so answer = dp[0].
    cout << dp[0] << "\n";
}

Pitfalls

What Gold December 2020 was actually testing