USACO 2019 January · Bronze · all three problems

← Full January 2019 set · Official results

Problem 1 — Shell Game

Statement

Bessie plays the shell game with Elsie. The pebble starts under shell 1. In each of N rounds Bessie swaps the contents of two shells (positions a and b), then Elsie guesses a shell g; she wins a point if her guess matches the shell that currently hides the pebble. Bessie wants to maximize Elsie's score by choosing the best initial shell for the pebble (out of {1, 2, 3}); print that maximum score.

Constraints

• 1 ≤ N ≤ 100.
• Each swap and guess is in {1, 2, 3}.
• Time limit: 2s.

Key idea

The initial pebble position has only three choices. For each of the three starting positions, simulate all N swaps with a tiny array pos[1..3] that tracks where the pebble currently is, then increment a counter when the guess equals the pebble's current shell. Return the max of the three totals.

Complexity target

O(N) per start × 3 starts = O(N). Trivially fits.

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> A(N), B(N), G(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i] >> G[i];

    int best = 0;
    for (int start = 1; start <= 3; ++start) {
        // shell[i] = which "labelled marker" currently sits under shell i.
        // Marker 'start' is the pebble; we just track its position.
        int pos = start;
        int score = 0;
        for (int i = 0; i < N; ++i) {
            if (pos == A[i]) pos = B[i];
            else if (pos == B[i]) pos = A[i];
            if (G[i] == pos) ++score;
        }
        best = max(best, score);
    }
    cout << best << "\n";
}

Pitfalls

• Swap before guess. The guess is checked after the swap in that round.
• "a swap of a and a" can appear. The pebble stays put — your else if branch must not double-fire.
• Don't shuffle the whole array of 3. Only the pebble's position matters; tracking three labelled markers wastes code.

Problem 2 — Mixing Milk

Statement

There are 4 buckets with capacities c_i and current amounts m_i (i = 1..4). In minute t (starting from t = 1) bucket ((t−1) mod 4) + 1 pours into bucket (t mod 4) + 1: as much milk as the source has, capped by the destination's remaining capacity. Print the contents of every bucket after 100 minutes.

Constraints

• 4 buckets, capacities and initial volumes 0 ≤ m_i ≤ c_i ≤ 1000.
• Exactly 100 simulated pours.
• Time limit: 2s.

Key idea

Pure simulation. Maintain volumes m[] and capacities c[]; for each step compute the transfer amount min(m[src], c[dst] − m[dst]), subtract from src, add to dst. Print after 100 iterations.

Complexity target

O(100) — constant.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    const int B = 4;
    vector<long long> cap(B), m(B);
    for (int i = 0; i < B; ++i) cin >> cap[i] >> m[i];

    for (int t = 1; t <= 100; ++t) {
        int src = (t - 1) % B;
        int dst = t % B;
        long long room = cap[dst] - m[dst];
        long long pour = min(m[src], room);
        m[src] -= pour;
        m[dst] += pour;
    }
    for (int i = 0; i < B; ++i) cout << m[i] << "\n";
}

Pitfalls

• Cycle order is fixed. Bucket 1 → 2 → 3 → 4 → 1 → … on minutes 1, 2, 3, 4, 5, …
• Destination cap matters. The destination won't overflow; excess milk stays in the source.
• Read input order carefully. Each line typically gives capacity then current.

Problem 3 — Sleepy Cow Sorting (Bronze)

Statement

Bessie has a permutation of cows labelled 1..N. In one operation she takes the first cow in the line and inserts it anywhere into the remaining N−1 cows. Output the minimum number of such operations to sort the line into increasing order.

Constraints

• 1 ≤ N ≤ 100.
• Input is a permutation of 1..N.
• Time limit: 2s.

Key idea

The cows we never touch must already be in sorted order, and they must sit at the end of the array (front cows are the ones that get pulled out and re-inserted). So find the longest already-sorted suffix: walk from the right while a_i < a_i+1. If that suffix has length L, the answer is N − L.

Complexity target

O(N).

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> a(N);
    for (auto& x : a) cin >> x;

    // Find longest sorted suffix.
    int i = N - 1;
    while (i > 0 && a[i - 1] < a[i]) --i;
    // Suffix is a[i..N-1], length N - i. Answer = N - (N - i) = i.
    cout << i << "\n";
}

Pitfalls

• Strict inequality. Since values are a permutation of 1..N, ties never occur — but writing <= still works.
• It's the suffix, not the LIS. Don't compute an LIS; only the already-sorted tail matters because the operation always removes from the front.
• N = 1. Answer is 0 — handle the empty-loop case naturally with the index initialization above.

What Bronze January 2019 was actually testing

• P1 — disciplined simulation. Run three independent simulations and take the max; don't overthink it.
• P2 — capacity-aware simulation. One careful min per transfer is the whole problem.
• P3 — observation over algorithm. The answer is just "where does the sorted suffix start?".