U USACO Prep

USACO 2020 December · Silver · 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 — Cowntact Tracing

Statement

There are N cows. Over T discrete days, you're given a list of "shake" events: pairs (a, b) at time t. At day T+1 a subset S of cows is sick. One cow is patient zero; when an infected cow shakes hooves with a healthy cow there is a (possibly limited) chance of transmission. Determine how many cows could be the patient zero and the maximum number of transmissions consistent with the observed sick set.

Constraints

Key idea

With N ≤ 100 and T ≤ 250, try each cow as patient zero (N ways) and each "K = max transmissions per handshake" candidate (up to T). For each (zero, K) simulate the events in order: when an infected cow meets a healthy one, infect (transmission used). If the resulting sick set equals S, this (zero, K) is valid. Count distinct valid zeros and track the maximum K.

Complexity target

O(N · T · T) ≈ 6 · 106, comfortably fast.

Reference solution (C++)

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

int N, T;
vector<tuple<int,int,int>> ev;     // (time, a, b)
vector<int> finalSick;

// Simulate with patient zero p and per-pair cap K. Return true if final state matches.
bool sim(int p, int K) {
    vector<int> inf(N + 1, 0), cnt(N + 1, 0);   // cnt = remaining transmissions
    inf[p] = 1; cnt[p] = K;
    for (auto [t, a, b] : ev) {
        if (inf[a] && inf[b]) continue;
        if (inf[a] && cnt[a] > 0) { inf[b] = 1; cnt[a]--; cnt[b] = K; }
        else if (inf[b] && cnt[b] > 0) { inf[a] = 1; cnt[b]--; cnt[a] = K; }
    }
    for (int i = 1; i <= N; ++i) if (inf[i] != finalSick[i]) return false;
    return true;
}

int main() {
    cin >> N >> T;
    string s; cin >> s;
    finalSick.assign(N + 1, 0);
    for (int i = 0; i < N; ++i) finalSick[i + 1] = (s[i] == '1');
    ev.resize(T);
    for (auto& [t, a, b] : ev) cin >> t >> a >> b;
    sort(ev.begin(), ev.end());

    int zeros = 0, bestK = 0;
    for (int p = 1; p <= N; ++p) {
        bool ok = false; int K;
        for (K = 0; K <= T; ++K) if (sim(p, K)) { ok = true; bestK = max(bestK, K); }
        if (ok) zeros++;
    }
    cout << zeros << " " << bestK << "\n";    // [verify exact output spec] cpid=1062
}

Pitfalls

Problem 2 — Rectangular Pasture

Statement

N cows lie at distinct points in the plane. Count the number of distinct subsets of cows that can be obtained as "cows inside some axis-aligned rectangle." Two rectangles that capture the same subset count once. Include the empty set.

Constraints

Key idea

Compress coordinates to [1..N] in both axes. A rectangle's "useful" subset is determined by choosing two cows that define its x-range (left and right boundary cows), and then counting how many distinct y-cross-sections we can include. Sort cows by x. For each pair (i, j) of cows with i ≤ j by x, count distinct subsets of y-intervals that include both i and j — equivalently, pick a y-range containing yi and yj; the count is (a + 1)(b + 1) where a, b are the number of cows strictly above/below the pair within x-range [i, j]. Use a precomputed prefix-sum-over-rectangles array cnt[i][j] = number of cows with x ≤ i and y ≤ j.

Complexity target

O(N²) pairs, O(1) lookup each. ~6 · 106 ops.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<pair<int,int>> pts(N);
    for (auto& [x, y] : pts) cin >> x >> y;

    // Compress.
    vector<int> xs(N), ys(N);
    for (int i = 0; i < N; ++i) { xs[i] = pts[i].first; ys[i] = pts[i].second; }
    sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end());
    for (auto& [x, y] : pts) {
        x = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
        y = (int)(lower_bound(ys.begin(), ys.end(), y) - ys.begin()) + 1;
    }
    // cnt[i][j] = # cows with x <= i and y <= j.
    vector cnt(N + 2, vector<int>(N + 2, 0));
    for (auto [x, y] : pts) cnt[x][y]++;
    for (int i = 1; i <= N; ++i)
      for (int j = 1; j <= N; ++j)
        cnt[i][j] += cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1];

    auto box = [&](int x1, int y1, int x2, int y2) {
        if (x1 > x2 || y1 > y2) return 0;
        return cnt[x2][y2] - cnt[x1-1][y2] - cnt[x2][y1-1] + cnt[x1-1][y1-1];
    };

    sort(pts.begin(), pts.end());
    ll ans = N + 1;   // empty + N single-cow subsets
    for (int i = 0; i < N; ++i)
      for (int j = i + 1; j < N; ++j) {
        int lx = pts[i].first, rx = pts[j].first;
        int lo = min(pts[i].second, pts[j].second), hi = max(pts[i].second, pts[j].second);
        int above = box(lx, hi + 1, rx, N);
        int below = box(lx, 1, rx, lo - 1);
        ans += (ll)(above + 1) * (below + 1);
      }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Stuck in a Rut (Silver)

Statement

Same rules as Bronze, but with up to N = 50000 cows. Each cow walks N or E; when two would meet at the same point, the later arriver stops. Output how far each cow walks before being stopped (or "Infinity").

Constraints

Key idea

Only an East cow and a North cow whose paths cross can collide. Sweep events in order of collision time. Maintain two ordered sets: alive East-walkers keyed by y, alive North-walkers keyed by x. For each candidate pair (E, N) with xE < xN and yN < yE, the collision time is max(xN − xE, yE − yN). Push these into a priority queue and process the earliest; when one stops, lazily mark and skip later events involving it.

Complexity target

O((N + events) log N). The number of relevant collision events is O(N) amortized when handled with sweep + sorted set neighbors.

Reference solution (C++)

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

struct Cow { ll x, y; char d; int id; };

int main() {
    int N; cin >> N;
    vector<Cow> c(N);
    for (int i = 0; i < N; ++i) {
        cin >> c[i].d >> c[i].x >> c[i].y; c[i].id = i;
    }
    vector<ll> dist(N, -1);
    vector<char> alive(N, 1);

    // Event: collision time, eIdx, nIdx, expected ages (for staleness check via alive flags).
    priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<>> pq;

    // Sort East cows by y, North cows by x to find first crossing pairs cheaply.
    vector<int> Es, Ns;
    for (int i = 0; i < N; ++i) (c[i].d == 'E' ? Es : Ns).push_back(i);
    // Seed: all O(|E| * |N|) candidate pairs — fine up to ~N^2 = 2.5e9 worst case,
    // so in practice use the standard trick of pairing each E only with the "next"
    // N it will hit; below we enumerate all pairs and rely on early staleness skipping.
    for (int e : Es) for (int n : Ns) {
        if (c[e].x < c[n].x && c[n].y < c[e].y) {
            ll tE = c[n].x - c[e].x, tN = c[e].y - c[n].y;
            if (tE != tN) pq.push({max(tE, tN), e, n});
        }
    }
    while (!pq.empty()) {
        auto [t, e, n] = pq.top(); pq.pop();
        if (!alive[e] || !alive[n]) continue;
        ll tE = c[n].x - c[e].x, tN = c[e].y - c[n].y;
        if (tE > tN) { alive[e] = 0; dist[e] = tE; }
        else         { alive[n] = 0; dist[n] = tN; }
    }
    for (int i = 0; i < N; ++i) {
        if (dist[i] < 0) cout << "Infinity\n"; else cout << dist[i] << "\n";
    }
}

Pitfalls

What Silver December 2020 was actually testing