U USACO Prep

USACO 2016 February · Gold · 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 with one cow per room at the end. ci cows are queued at door i (Σci = n). Cows walk clockwise to their rooms; energy cost is (distance walked)². Minimize total energy. Same problem as Silver P1 but at scale.

Constraints

Key idea

Find a "starting door" s such that the running balance bk = Σj=0..k (c(s+j) mod n − 1) is non-negative for all k (this is the classic "gas station" lemma — a unique rotation gives no deficit). From s, simulate FIFO assignment with a queue or a stack of entry positions; cost is Σ (k − entry)². O(n) sweep after finding s; finding s is O(n) by tracking the minimum prefix-sum index.

Complexity target

O(n) time, O(n) memory.

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;

    // Find the door s where prefix sums of (c_i - 1) hit their minimum -- that's the unique safe start.
    int s = 0; ll cur = 0, mn = 0;
    for (int i = 0; i < n; ++i) {
        cur += c[i] - 1;
        if (cur < mn) { mn = cur; s = (i + 1) % n; }
    }

    // Sweep from s with a FIFO of entry positions of in-transit cows.
    queue<int> q;
    ll cost = 0;
    for (int k = 0; k < n; ++k) {
        int door = (s + k) % n;
        for (int j = 0; j < c[door]; ++j) q.push(k);
        ll d = k - q.front(); q.pop();
        cost += d * d;
    }
    cout << cost << "\n";
}

Pitfalls

Problem 2 — Circular Barn Revisited

Statement

n rooms in a ring, room i needs ri cows. Farmer John unlocks exactly k exterior doors; each cow enters through some unlocked door and walks clockwise. Choose which k doors to unlock to minimize total walking distance.

Constraints

Key idea

If we fix the unlocked door positions d1 < … < dk on the ring, each room is served by the nearest unlocked door at or before it (clockwise). So the n rooms split into k clockwise arcs, each from one unlocked door up to the next. The cost of an arc starting at door d covering rooms rd, rd+1, …, rd+L−1 is Σj=0..L−1 j · rd+j. Enumerate starting-door positions and split the ring into k arcs. With n ≤ 100 and k ≤ 7, "fix the first door" (n choices), then DP over (current position, arcs used). O(n³ · k) ≈ 7·106.

Complexity target

O(n · n² · k) time, O(n · k) memory after precomputing arc costs.

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, k; cin >> n >> k;
    vector<ll> r(n);
    for (auto& x : r) cin >> x;

    ll ans = LLONG_MAX;
    // Try each starting door s as the first unlocked one.
    for (int s = 0; s < n; ++s) {
        // arc[i][len] = cost of arc of length len starting at offset i from s.
        vector<vector<ll>> arc(n, vector<ll>(n + 1, 0));
        for (int i = 0; i < n; ++i) {
            ll c = 0;
            for (int L = 1; i + L <= n; ++L) {
                c += (ll)(L - 1) * r[(s + i + L - 1) % n];
                arc[i][L] = c;
            }
        }
        // dp[i][j] = min cost to cover first i rooms using j arcs (j-th arc ends just before room i).
        vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, LLONG_MAX));
        dp[0][0] = 0;
        for (int i = 0; i < n; ++i)
          for (int j = 0; j < k; ++j) if (dp[i][j] != LLONG_MAX)
            for (int L = 1; i + L <= n; ++L)
              dp[i + L][j + 1] = min(dp[i + L][j + 1], dp[i][j] + arc[i][L]);
        ans = min(ans, dp[n][k]);
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Fenced In

Statement

An A×B rectangular field has n internal vertical fences at x = a1, …, an and m internal horizontal fences at y = b1, …, bm, creating (n+1)(m+1) rectangular regions. Compute the minimum total length of fencing to remove so that all regions are connected (the regions, viewed as cells, become 4-connected after removing fence segments).

Constraints

Key idea

Model as MST: each cell is a node, each fence segment between adjacent cells is a candidate edge with weight equal to that segment's length. A vertical fence at x = ai contributes horizontal-cut edges of weight (bj − bj−1) — one per row strip. Symmetric for horizontal fences. Equivalently: sort the n+1 column widths W and the m+1 row heights H in increasing order. Kruskal greedily picks the smallest gap repeatedly; the closed form is Σ Wi · (count of row strips still un-merged at that step) + symmetric for rows. The standard trick: process all (n+m) "small gaps" in sorted order, alternating between bridging a column and a row, multiplying each by the count of remaining strips on the opposite axis.

Complexity target

O((n + m) log(n + m)) time, O(n + m) memory.

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);
    ll A, B; int n, m;
    cin >> A >> B >> n >> m;
    vector<ll> a(n), b(m);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    sort(a.begin(), a.end()); sort(b.begin(), b.end());

    // Column widths W (size n+1) and row heights H (size m+1).
    vector<ll> W, H;
    { ll prev = 0; for (ll x : a) { W.push_back(x - prev); prev = x; } W.push_back(A - prev); }
    { ll prev = 0; for (ll y : b) { H.push_back(y - prev); prev = y; } H.push_back(B - prev); }
    sort(W.begin(), W.end()); sort(H.begin(), H.end());

    // Always connect via the smallest gap of width W[0] or H[0] first (these are "free" in count terms).
    // Then merge remaining: each remaining width W[i] (i >= 1) is used (m+1) times if we have not yet
    // started rows, else (number of row-strips still un-merged).
    ll ans = 0;
    int i = 1, j = 1;        // pointers into W and H past the minimums
    ll colRem = n, rowRem = m;  // remaining merges needed on each axis
    // Anchor: spend W[0] to glue all (m+1) row strips along the thinnest column gap, and
    // H[0] to glue all (n+1) col strips along the thinnest row gap.
    ans += W[0] * rowRem;    // merges rowRem rows once each via the cheapest column gap
    ans += H[0] * colRem;    // merges colRem cols once each via the cheapest row gap
    // Note: above is the canonical closed-form for this problem.

    while (i <= n && j <= m) {
        if (W[i] < H[j]) { ans += W[i] * rowRem; --colRem; ++i; }
        else             { ans += H[j] * colRem; --rowRem; ++j; }
    }
    while (i <= n) { ans += W[i] * rowRem; ++i; }
    while (j <= m) { ans += H[j] * colRem; ++j; }

    cout << ans << "\n";
}

Pitfalls

What Gold February 2016 was actually testing