USACO 2018 December · Bronze · all three problems

← Full December 2018 set · Official results

Problem 1 — Mixing Milk

Statement

Three buckets each have a capacity c_i and an initial milk amount m_i. Farmer John performs 100 pours in cyclic order: pour 1 sends bucket 1 into bucket 2, pour 2 sends bucket 2 into bucket 3, pour 3 sends bucket 3 into bucket 1, and so on. Each pour transfers as much milk as possible until the source empties or the destination fills. Output the milk amounts after all 100 pours.

Constraints

• 1 ≤ c_i, m_i ≤ 10⁹, m_i ≤ c_i.
• Exactly 100 pours, cyclic order 1→2, 2→3, 3→1, 1→2, …
• Time limit: 2s (standard USACO Bronze).

Key idea

Pure simulation. For each pour, the amount moved is min(source, destination_capacity − destination). No clever observation needed — 100 iterations is trivially fast.

Complexity target

O(1) — exactly 100 pours regardless of input.

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);
    array<ll, 3> cap{}, milk{};
    for (int i = 0; i < 3; ++i) cin >> cap[i] >> milk[i];

    for (int step = 0; step < 100; ++step) {
        int a = step % 3;            // source
        int b = (step + 1) % 3;      // destination
        ll move = min(milk[a], cap[b] - milk[b]);
        milk[a] -= move;
        milk[b] += move;
    }
    for (int i = 0; i < 3; ++i) cout << milk[i] << "\n";
}

Pitfalls

• 64-bit. Capacities go up to 10⁹; while sums stay bounded by 3·10⁹, use long long defensively.
• Cycle direction. The pours rotate 1→2→3→1, not 1→2 and 2→1 alternately.
• Bucket ordering in output. Print bucket 1 first, then 2, then 3.
• Don't try to detect a fixed point. 100 steps is small; simulating is shorter and bug-free.

Problem 2 — The Bucket List

Statement

Farmer John has N cows. Cow i needs to be milked from time s_i to time t_i (inclusive on the open interval [s_i, t_i)) and requires b_i buckets during that window. Buckets can be reused once a cow finishes. Find the minimum total number of buckets Farmer John needs.

Constraints

• 1 ≤ N ≤ 100.
• 1 ≤ s_i, t_i ≤ 1000, s_i < t_i.
• 1 ≤ b_i ≤ 10.
• Time limit: 2s.

Key idea

Classic sweep-line / difference array. At time s_i, add b_i; at time t_i, subtract b_i. The answer is the maximum prefix sum. Equivalently: for each time t in [1, 1000], sum b_i over cows whose interval contains t, and take the max.

Complexity target

O(T + N) where T = 1000. Even O(N·T) = 10⁵ brute-force is fine.

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;
    const int T = 1002;
    vector<int> diff(T + 2, 0);
    for (int i = 0; i < N; ++i) {
        int s, t, b; cin >> s >> t >> b;
        // Cow occupies [s, t]; she releases buckets at t+1 (or use [s, t) — see pitfalls).
        diff[s]     += b;
        diff[t + 1] -= b;
    }
    int cur = 0, ans = 0;
    for (int i = 1; i < T; ++i) {
        cur += diff[i];
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}

Pitfalls

• Endpoint inclusion. Re-read the statement: "from s_i to t_i" is typically inclusive in USACO. The −b at t+1 assumes inclusive; if it's exclusive, use t.
• Time bound. t_i ≤ 1000, so a fixed-size array works; no coordinate compression needed.
• Bucket numbering rule is a red herring. The "lowest-numbered available bucket" rule is only there to anchor intuition; the answer is the peak concurrent demand.
• Small N temptation. N ≤ 100 invites O(N²) — fine, but the sweep is simpler.

Problem 3 — Back and Forth

Statement

Each barn starts with 1000 gallons and 10 buckets (sizes given). On four consecutive days Farmer John walks one bucket between the barns: Tue barn 1 → 2, Wed barn 2 → 1, Thu barn 1 → 2, Fri barn 2 → 1. On each trip he fills the chosen bucket from the source tank and empties it into the destination tank (the bucket is then in the destination barn's closet for future trips). Output the number of distinct amounts of milk barn 1 can have on Saturday morning.

Constraints

• Exactly 10 buckets at each barn; sizes 1–1000.
• Search space: 10 · 10 · 11 · 11 ≈ 12100 ordered choices (after Tue, barn 2 has 11 buckets).
• Time limit: 2s.

Key idea

Brute-force DFS over the four trips. State after each trip is determined by (barn-1 tank, which buckets are at each barn). But because tank amounts depend only on signed sums of bucket sizes, you can collapse state to the running barn-1 amount and the multisets at each barn. Insert each final barn-1 value into a set<int>; output its size.

Complexity target

O(10⁴) DFS leaves; each operation is an O(1) multiset swap. Fits in well under 1s.

Reference solution (C++)

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

set<int> results;
vector<int> A, B;  // buckets currently at barn 1, barn 2

// day = 0..3; direction[d] = source barn (0 -> 1, 1 -> 0, 0 -> 1, 1 -> 0)
const int dir[4] = {0, 1, 0, 1};

void dfs(int day, int milk1) {
    if (day == 4) { results.insert(milk1); return; }
    vector<int>& src = (dir[day] == 0) ? A : B;
    vector<int>& dst = (dir[day] == 0) ? B : A;
    int sign = (dir[day] == 0) ? -1 : +1;  // barn-1 change

    for (int i = 0; i < (int)src.size(); ++i) {
        int bucket = src[i];
        src.erase(src.begin() + i);
        dst.push_back(bucket);
        dfs(day + 1, milk1 + sign * bucket);
        dst.pop_back();
        src.insert(src.begin() + i, bucket);
    }
}

int main() {
    A.resize(10); B.resize(10);
    for (auto& x : A) cin >> x;
    for (auto& x : B) cin >> x;
    dfs(0, 1000);
    cout << results.size() << "\n";
}

Pitfalls

• Buckets travel with the milk. After Tuesday, barn 2 has 11 buckets and barn 1 has 9. Forgetting to move the bucket inflates the answer.
• Direction signs. Tue and Thu lower barn 1; Wed and Fri raise it.
• Distinct values, not pours. A set deduplicates final amounts that arrive via different bucket sequences.
• Don't precompute "net change" without tracking which buckets are where. The same bucket can be used on later trips only from its current barn.

What Bronze December 2018 was actually testing

• P1 — pure simulation discipline. Read the rule once, code it once, submit.
• P2 — sweep line / difference array. The "lowest-numbered bucket" framing hides a standard concurrency-peak problem.
• P3 — exhaustive search with shared mutable state. Push/pop on the bucket lists rather than copying.