U USACO Prep

USACO 2016 February · Silver · all three problems

← Full February 2016 set · Official results

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

Statement

n rooms in a ring, each holding exactly one cow at the end. ci cows are queued at the exterior door of room i (Σci = n). Each cow walks clockwise to her assigned room. If she walks d doors, her energy cost is d². Assign cows to rooms to minimize the total squared energy.

Constraints

Key idea

Walk once around the ring keeping a queue of "cows in transit." At each door i, push ci new cows onto the queue, then have one cow exit here (the front of the queue, who has walked the farthest). The key insight: starting the sweep at the right door matters. Try each of the n possible starting doors; for each one, simulate the greedy "first-in, first-out" assignment in O(n). With n ≤ 1000, O(n²) ≈ 106 is fine.

Complexity target

O(n²) time, O(n) memory. (Tighter O(n log n) solutions exist but are unnecessary here.)

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<int> c(n);
    for (auto& x : c) cin >> x;

    ll best = LLONG_MAX;
    for (int s = 0; s < n; ++s) {
        // Simulate sweep starting at door s. queue holds entry positions of cows in transit.
        queue<int> q;
        ll cost = 0;
        bool ok = true;
        for (int k = 0; k < n; ++k) {
            int door = (s + k) % n;
            for (int j = 0; j < c[door]; ++j) q.push(k);
            if (q.empty()) { ok = false; break; }
            int entry = q.front(); q.pop();
            ll d = k - entry;
            cost += d * d;
        }
        if (ok) best = min(best, cost);
    }
    cout << best << "\n";
}

Pitfalls

Problem 2 — Load Balancing

Statement

Same setup as Bronze P3 but bigger: N cows at distinct odd-coordinate points, place a vertical fence at even x = a and a horizontal fence at even y = b. Minimize M = max cows in any of the four quadrants.

Constraints

Key idea

Coordinate-compress: only N distinct x-values and N distinct y-values matter, so there are O(N²) candidate (a, b) splits. For each fixed a, sort cows by y and sweep b through the N+1 horizontal candidates, updating four counters incrementally. That gives O(N² log N) overall. Alternative: fix a (N choices), then for each cow compute "left vs right of a," then for each candidate b count by sweep — O(N²) per a, O(N³) total ≈ 109, too slow; the per-a sweep version is the right fit.

Complexity target

O(N² log N) time, O(N) memory. Comfortably under 2s for N ≤ 1000.

Reference solution (C++)

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

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

    vector<int> xs = X, ys = Y;
    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());

    int best = N;
    for (int xv : xs) {
        // Fence a = xv - 1 (even). Partition cows by left/right of a.
        vector<int> leftY, rightY;
        for (int i = 0; i < N; ++i)
            (X[i] < xv ? leftY : rightY).push_back(Y[i]);
        sort(leftY.begin(), leftY.end());
        sort(rightY.begin(), rightY.end());

        for (int yv : ys) {
            int lb = lower_bound(leftY.begin(),  leftY.end(),  yv) - leftY.begin();
            int rb = lower_bound(rightY.begin(), rightY.end(), yv) - rightY.begin();
            int q1 = lb, q2 = (int)leftY.size()  - lb;
            int q3 = rb, q4 = (int)rightY.size() - rb;
            best = min(best, max({q1, q2, q3, q4}));
        }
    }
    cout << best << "\n";
}

Pitfalls

Problem 3 — Milk Pails

Statement

Two pails of sizes X and Y. At each step you may fill a pail, empty a pail, or pour from one pail into the other (until source empty or destination full). After at most K such operations, output the minimum |M − (x + y)| achievable, where (x, y) are the contents of the two pails.

Constraints

Key idea

The state is (x, y, step). There are ≤ (X+1)(Y+1) ≤ 10201 reachable (x, y) pairs and K ≤ 100 steps. BFS from (0, 0): for each state, the 6 transitions are fill-X, fill-Y, empty-X, empty-Y, pour X→Y, pour Y→X. Track the minimum step at which each (x, y) is first reached; if step ≤ K, the state contributes |M − (x+y)| to the answer.

Complexity target

O(X · Y) states, 6 transitions each. ~6·104 operations, instantaneous.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int X, Y, K, M;
    cin >> X >> Y >> K >> M;

    vector<vector<int>> dist(X+1, vector<int>(Y+1, INT_MAX));
    queue<pair<int,int>> q;
    dist[0][0] = 0; q.push({0,0});
    int best = abs(M - 0);

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        int d = dist[x][y];
        best = min(best, abs(M - (x + y)));
        if (d == K) continue;
        // 6 transitions
        int p = min(X - x, y);   // pour Y -> X
        int r = min(Y - y, x);   // pour X -> Y
        pair<int,int> nb[6] = {
            {X, y}, {x, Y}, {0, y}, {x, 0},
            {x + p, y - p}, {x - r, y + r}
        };
        for (auto [nx, ny] : nb) {
            if (dist[nx][ny] > d + 1) {
                dist[nx][ny] = d + 1;
                q.push({nx, ny});
            }
        }
    }
    cout << best << "\n";
}

Pitfalls

What Silver February 2016 was actually testing