U USACO Prep

USACO 2022 December · Silver · all three problems

← Full December 2022 set · Official results

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

Statement

A tree of N barns; barn j holds hj bales of hay. In one operation, FJ picks an edge (u,v) and moves any number of bales from u to v (or v to u). The total sum is divisible by N. Find the minimum number of operations to equalize all barns to sum/N bales, and print one such sequence of operations (u v x meaning move x bales from u to v).

Constraints

Key idea

Root the tree anywhere. Compute target T = (Σh)/N and let dj = hj − T. Do a post-order DFS: for each non-root node v with parent p, after children have balanced themselves, v has accumulated some surplus/deficit sv. Make exactly one move on edge (v, p): if sv > 0 send sv from v to p, else send |sv| from p to v (do this "logically" by pushing it on a stack during the recursion). Number of operations equals the number of edges with non-zero flow — exactly one per "non-zero" subtree edge.

Complexity target

O(N) DFS, O(N) output.

Reference solution (C++)

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

int N;
vector<vector<int>> adj;
vector<ll>  h;
ll target;
vector<tuple<int,int,ll>> moves;   // (from, to, amount)

// Returns surplus pushed up to parent (signed). For each subtree edge with
// non-zero flow we emit exactly one move. Post-order so leaves resolve first.
ll dfs(int u, int par) {
    ll cur = h[u] - target;
    for (int v : adj[u]) if (v != par) cur += dfs(v, u);
    if (par != -1 && cur != 0) {
        if (cur > 0) moves.emplace_back(u, par, cur);
        else         moves.emplace_back(par, u, -cur);
    }
    return cur;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    h.assign(N + 1, 0); adj.assign(N + 1, {});
    ll sum = 0;
    for (int i = 1; i <= N; ++i) { cin >> h[i]; sum += h[i]; }
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a);
    }
    target = sum / N;
    dfs(1, -1);
    cout << moves.size() << "\n";
    for (auto [u, v, x] : moves) cout << u << " " << v << " " << x << "\n";
}

Pitfalls

Problem 2 — Circular Barn

Statement

N rooms in a circle, room i has ai cows. FJ and a rival alternate turns starting with FJ; on a turn the active player must remove either 1 cow or a prime number of cows from the current room (≤ remaining). When a room hits 0 the active player must move clockwise to the next room. The player who arrives at a room that is already empty loses. Determine the winner.

Constraints

Key idea

This is a sum of independent Nim-like games (one per room) under Sprague–Grundy, then XOR the per-room Grundy values. For a single room with a cows under the "subtract 1 or any prime ≤ a" rule, the Grundy values g(a) are bounded and become periodic — precompute g(0..5·106) once with a sieve of primes plus the standard mex-from-reachable-positions DP. FJ (first player) wins iff XORi g(ai) ≠ 0.

Complexity target

Sieve + Grundy table: O(A · π(A)) which is ~5·106 · ln-ratio — needs the mex done with a bitset/seen-array per position. Per test case: O(N) lookups.

Reference solution (C++)

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

// WARNING: this is the structural template. The exact game's Grundy pattern
// should be verified against small cases / the editorial. [verify cpid=1255]
static const int A = 5'000'001;
vector<int> primes;
int g[A];

void buildPrimes() {
    vector<char> comp(A, 0);
    for (int i = 2; i < A; ++i) {
        if (!comp[i]) { primes.push_back(i); for (long long j = 1LL*i*i; j < A; j += i) comp[j] = 1; }
    }
}

void buildGrundy() {
    g[0] = 0;
    vector<char> seen(64, 0);
    for (int a = 1; a < A; ++a) {
        fill(seen.begin(), seen.end(), 0);
        // Move 1: remove 1 cow -> g[a-1].
        if (g[a - 1] < (int)seen.size()) seen[g[a - 1]] = 1;
        // Move 2: remove a prime p <= a -> g[a - p].
        for (int p : primes) {
            if (p > a) break;
            int gv = g[a - p];
            if (gv < (int)seen.size()) seen[gv] = 1;
        }
        int m = 0; while (m < (int)seen.size() && seen[m]) ++m;
        g[a] = m;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    buildPrimes();
    buildGrundy();
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        int x = 0;
        for (int i = 0; i < N; ++i) { int a; cin >> a; x ^= g[a]; }
        cout << (x ? "Farmer John" : "Farmer Nhoj") << "\n";
    }
}

Pitfalls

Problem 3 — Range Reconstruction

Statement

Bessie has a hidden integer array a1..N. For every pair i ≤ j she tells you ri,j = max a[i..j] − min a[i..j]. Output any array with values in [−109, 109] that produces exactly these N(N+1)/2 ranges. A solution is guaranteed to exist.

Constraints

Key idea

Fix a[0] = 0. Walk i from 0 to N−2 and decide the sign of (a[i+1] − a[i]) from a single carefully chosen pair. The magnitude |a[i+1] − a[i]| is ri,i+1. To pin the sign, look at any j ≤ i with rj,i < rj,i+1: then a[i+1] is the new extreme of [j..i+1], extending in the direction farther from the current min/max — comparing rj,i+1 to rj,i determines whether a[i+1] is above max[j..i] or below min[j..i]. If no such j exists, the new value lies inside the current range of [j..i] for every j, so the sign is forced by being inside; default to "+" and continue. O(N²) overall.

Complexity target

O(N²) ≈ 9·104 operations.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<vector<ll>> r(N, vector<ll>(N, 0));
    for (int i = 0; i < N; ++i)
        for (int j = i; j < N; ++j) cin >> r[i][j];

    vector<ll> a(N, 0);
    ll lo = 0, hi = 0;                 // running min/max of a[0..i]
    for (int i = 0; i < N - 1; ++i) {
        ll diff = r[i][i + 1];
        // Decide sign: scan j from i downward; first j with r[j][i+1] != r[j][i]
        // tells us whether a[i+1] extends above hi or below lo of [j..i].
        int sign = 0;
        for (int j = i; j >= 0 && sign == 0; --j) {
            if (r[j][i + 1] == r[j][i]) continue;     // a[i+1] is inside [min,max] of [j..i]
            // r[j][i+1] - r[j][i] = diff if extending above, equals diff also if below — disambiguate
            // by comparing to (hi - a[i]) vs (a[i] - lo). [verify branch logic] cpid=1256
            ll above = (hi - a[i]) + diff;
            if (r[j][i + 1] == above) sign = +1;
            else                       sign = -1;
        }
        if (sign == 0) sign = +1;
        a[i + 1] = a[i] + (ll)sign * diff;
        lo = min(lo, a[i + 1]);
        hi = max(hi, a[i + 1]);
    }
    // Normalise so min is 0 (or any anchor in range). Optional.
    ll mn = *min_element(a.begin(), a.end());
    for (auto& x : a) x -= mn;
    for (int i = 0; i < N; ++i) cout << a[i] << " \n"[i == N - 1];
}

Pitfalls

What Silver December 2022 was actually testing