USACO 2016 February · Bronze · all three problems

← Full February 2016 set · Official results

Problem 1 — Milk Pails

Statement

Farmer John has a big pail of capacity M and two small pails of capacities X and Y (X < Y < M). He may repeatedly pick one of the two small pails, fill it completely, and pour it into the big pail — but only if doing so does not cause the big pail to overflow. Maximize the amount of milk in the big pail.

Constraints

• 1 ≤ M ≤ 1000.
• 1 ≤ X < Y < M.
• Time limit: 2s.

Key idea

Try every combination (a, b) where a is the number of X-pours and b is the number of Y-pours, with a·X + b·Y ≤ M. Since X ≥ 1, a ≤ M and b ≤ M, so the search space is at most ~M² = 10⁶. Track the maximum a·X + b·Y achieved.

Complexity target

O(M²) time, O(1) memory. Comfortably under the 2s limit.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int X, Y, M;
    cin >> X >> Y >> M;
    // Try a fills of X-pail and b fills of Y-pail; constraint a*X + b*Y <= M.
    int best = 0;
    for (int a = 0; a * X <= M; ++a) {
        int rem = M - a * X;
        int b = rem / Y;             // largest b with b*Y <= rem
        int total = a * X + b * Y;
        best = max(best, total);
    }
    cout << best << "\n";
}

Pitfalls

• "Without overflowing" is strict. The big pail cannot exceed M, even momentarily — so a·X + b·Y ≤ M, not <.
• You cannot partially pour. Each pour is a full small pail; rejecting a pour that would overflow is a no-op, not a partial fill.
• The brute force is fine. Don't over-engineer with Bezout / gcd — M ≤ 1000 makes the loop trivial.

Problem 2 — Circular Barn

Statement

A circular barn has n rooms in a ring. Room i needs exactly r_i cows. Farmer John unlocks exactly one exterior door; every cow enters through that door and walks clockwise to her room. Choose the door to minimize the total walking distance summed over all cows.

Constraints

• 3 ≤ n ≤ 1000.
• 1 ≤ r_i ≤ 100.
• Time limit: 2s.

Key idea

For a fixed entry door s, a cow heading to room (s+k) mod n walks k doors. Total cost from door s is Σ_k=0..n−1 k · r_{(s+k) mod n}. With n ≤ 1000, try all n candidate doors and compute each sum in O(n). O(n²) ≈ 10⁶ is comfortable.

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

    ll best = LLONG_MAX;
    for (int s = 0; s < n; ++s) {
        ll cost = 0;
        for (int k = 0; k < n; ++k) {
            cost += (ll)k * r[(s + k) % n];
        }
        best = min(best, cost);
    }
    cout << best << "\n";
}

Pitfalls

• Clockwise only. Cows cannot back up; the distance from door s to room (s+k) mod n is k, not min(k, n−k).
• Use long long defensively. Worst-case sum ≈ 1000 · 1000 · 100 = 10⁸, still fits in 32-bit but no reason to gamble.
• Modular index is easy to typo. Confirm (s + k) % n wraps the ring correctly when s + k ≥ n.

Problem 3 — Load Balancing

Statement

N cows sit at distinct points (x_i, y_i) with x_i, y_i positive odd integers. Place a vertical fence x = a and a horizontal fence y = b with a, b even integers, splitting the plane into four quadrants. Let M be the maximum number of cows in any of the four regions. Minimize M.

Constraints

• 1 ≤ N ≤ 100.
• Coordinates are positive odd integers ≤ B; B ≤ 10⁶ overall, ≤ 100 on the first five test cases.
• Time limit: 2s.

Key idea

The only candidate fence positions that matter are between consecutive cow coordinates. With N ≤ 100, there are at most N+1 useful values of a and N+1 of b. For each (a, b) pair, count cows in each quadrant in O(N). Total: O(N³) ≈ 10⁶, trivially fast.

Complexity target

O(N³) time, O(N) memory.

Reference solution (C++)

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

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

    // Candidate fence values: just below each cow's x (and y). x_i is odd, x_i - 1 is even.
    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 xi : xs) for (int yi : ys) {
        // Fence at a = xi - 1, b = yi - 1 (both even). Quadrants: x < a, x > a × y < b, y > b.
        int q[4] = {0,0,0,0};
        for (int i = 0; i < N; ++i) {
            int r = (X[i] > xi - 1) * 2 + (Y[i] > yi - 1);
            q[r]++;
        }
        best = min(best, max({q[0], q[1], q[2], q[3]}));
    }
    cout << best << "\n";
}

Pitfalls

• Parity matters. Cows are at odd coords, fences at even coords — so no cow ever sits on a fence. Generate candidates by subtracting 1 from each cow coord.
• Don't forget the "left of all cows" and "below all cows" fences. Including the smallest cow coord − 1 (or 0) covers degenerate splits.
• Read B but you don't really need it for Bronze. The candidate fences are determined by the cow positions, not by B.

What Bronze February 2016 was actually testing

• P1 — bounded brute force. Recognize when M ≤ 1000 makes a double loop the right answer.
• P2 — ring iteration with modular index. The contest staple of "try each rotation, sum a weighted offset."
• P3 — discrete fence placement. Candidate positions are between consecutive sorted cow coords — same idea that scales up to Silver, Platinum.