U USACO Prep

2022 February Gold · All three problems

← Back to Feb 2022 hub · Official results

Canonical statements live at usaco.org. Statements below are my paraphrase — open the official problem PDFs before submitting your own solution. Each problem links to the official viewer.

Problem 1 · Redistributing Gifts

Official problem (cpid=1209)

Statement (paraphrased)

Gold version of the Silver problem. N ≤ 18 cows, each with a preference permutation; a reassignment must give every cow something she likes at least as much as her starting gift, AND a gift can only go to a cow of the same breed as its original owner. Each of Q ≤ min(105, 2N) breed strings is queried: count valid reassignments.

Constraints

Key idea

For each subset S ⊆ {1..N} let f(S) = number of perfect matchings of cows-in-S to gifts-in-S using only acceptable edges (cow i accepts gift j iff cow i ranks j ≤ rank of i's own gift in her list). Compute f(S) by bitmask DP: pick the lowest-indexed unmatched cow and try each acceptable gift in S; recurrence runs in O(2N · N). Now for a breed string, partition cows into G-set and H-set; the answer is f(G-set) · f(H-set) because reassignment is independent across breeds. Each query: O(N) bitmask construction then a table lookup. Total: O(2N·N + Q).

Complexity target

O(2N·N + Q). 218·18 ≈ 5·106.

C++ reference solution

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

int N;
int accept[20];   // accept[i] = bitmask of gifts cow i will accept

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; ++i) {
        vector<int> pref(N);
        int posSelf = -1;
        for (int k = 0; k < N; ++k) { cin >> pref[k]; --pref[k]; if (pref[k] == i) posSelf = k; }
        for (int k = 0; k <= posSelf; ++k) accept[i] |= (1 << pref[k]);
    }
    int FULL = 1 << N;
    vector<ll> f(FULL, 0);
    f[0] = 1;
    // Standard "match by popcount" matching DP.
    for (int S = 1; S < FULL; ++S) {
        int cow = __builtin_ctz(S & -S);                  // pick some cow in S
        // try giving cow `cow` any acceptable gift also in S
        int avail = accept[cow] & S;
        // but we need gifts indexed by S too — assume cow i's gift indices live in S
        for (int g = avail; g; g &= g - 1) {
            int bit = g & -g;
            f[S] += f[S ^ (1 << cow) ^ bit];
        }
    }
    int Q; cin >> Q;
    while (Q--) {
        string s; cin >> s;
        int G = 0, H = 0;
        for (int i = 0; i < N; ++i) (s[i]=='G' ? G : H) |= (1 << i);
        cout << f[G] * f[H] << '\n';
    }
    return 0;
}

Pitfalls

Problem 2 · Cow Camp

Official problem (cpid=1210)

Statement (paraphrased)

A contest has T test cases each yes/no; Bessie's solution is right on case 1 and random on the rest. She submits up to K times; after each submission she sees her score (number of cases passed) and may either stop or resubmit. Maximise her expected final score under the optimal threshold policy.

Constraints

Key idea

Let Ek = expected best score using at most k submissions. E1 = 1 + (T−1)/2 (sample case always right; other T−1 cases each correct with prob 1/2). For k+1: she submits once, observes random X (1 + Binomial(T−1, 1/2)), and stops if X ≥ Ek, otherwise resubmits with k more tries. So Ek+1 = Σx P(X=x) · max(x, Ek). Compute Binomial PMF once; iterate. Convergence: Ek increases monotonically and converges toward T. For K up to 109, stop early when |Ek+1 − Ek| < 10−9.

Complexity target

O(T · k*) where k* is iterations to converge — empirically a few thousand even for very large T.

C++ reference solution

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

int main(){
    int T; long long K;
    cin >> T >> K;
    // Precompute Binomial(T-1, x) / 2^(T-1) using log-factorials for stability
    int n = T - 1;
    vector<double> logf(n + 1, 0);
    for (int i = 1; i <= n; ++i) logf[i] = logf[i-1] + log((double)i);
    double logHalf = -n * log(2.0);
    vector<double> p(n + 1);
    for (int x = 0; x <= n; ++x)
        p[x] = exp(logf[n] - logf[x] - logf[n-x] + logHalf);

    double E = 1.0 + n / 2.0; // E_1
    for (long long k = 1; k < K; ++k) {
        double nxt = 0;
        for (int x = 0; x <= n; ++x) nxt += p[x] * max((double)(1 + x), E);
        if (nxt - E < 1e-12) { E = nxt; break; }
        E = nxt;
    }
    cout << fixed << setprecision(9) << E << '\n';
    return 0;
}

Pitfalls

Problem 3 · Moo Network

Official problem (cpid=1211)

Statement (paraphrased)

N ≤ 105 points in the plane with 0 ≤ x ≤ 106, 0 ≤ y ≤ 10. Cost of edge ij is squared Euclidean distance. Compute the minimum spanning tree weight.

Constraints

Key idea

y is tiny (0..10), so for each point we only need edges to a small neighbourhood. Sort by x. For each point, generate edges to the next ~22 points in the sorted order (covers the 11 possible y-values · ~2 lookahead) — that's 22N candidate edges, which is enough for the MST because any MST edge must compete with the shortest x-difference neighbour at each y-level. Run Kruskal with DSU. The classic editorial trick: keep, per y-level, the most recent point seen, and add an edge to it as you sweep — but the simpler "next 22 in sorted-by-x order" works.

Complexity target

O(N · α · log N) with ≈22N edges, sort + Kruskal dominate.

C++ reference solution

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

struct DSU {
    vector<int> p, r;
    DSU(int n):p(n),r(n,0){ iota(p.begin(),p.end(),0); }
    int f(int x){ return p[x]==x ? x : p[x]=f(p[x]); }
    bool u(int a,int b){ a=f(a); b=f(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::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<array<int,3>> pts(N); // x,y,id
    for (int i = 0; i < N; ++i){ cin >> pts[i][0] >> pts[i][1]; pts[i][2] = i; }
    sort(pts.begin(), pts.end()); // by x then y

    vector<tuple<ll,int,int>> edges;
    edges.reserve((size_t)N * 22);
    for (int i = 0; i < N; ++i)
        for (int j = i + 1; j < min(N, i + 23); ++j) {
            ll dx = pts[i][0] - pts[j][0];
            ll dy = pts[i][1] - pts[j][1];
            edges.push_back({dx*dx + dy*dy, pts[i][2], pts[j][2]});
        }
    sort(edges.begin(), edges.end());

    DSU dsu(N);
    ll cost = 0; int cnt = 0;
    for (auto& [w, a, b] : edges) {
        if (dsu.u(a, b)) { cost += w; if (++cnt == N - 1) break; }
    }
    cout << cost << '\n';
    return 0;
}

Pitfalls