U USACO Prep

USACO 2017 January · Bronze · all three problems

← Full January 2017 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan17results. 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 — Don't Be Last!

Statement

Farmer John tracks N milking sessions across his seven cows (Bessie, Elsie, Daisy, Gertie, Annabelle, Maggie, Henrietta). Each session contributes a positive amount of milk to one named cow; cows that never appear contribute zero. Output the name of the cow with the second-smallest total milk. If there is a tie for that position (or every cow ties for least), print Tie.

Constraints

Key idea

Map names to totals with an unordered_map<string,int> seeded at 0 for all 7 cows. Sort the totals. The answer is the unique cow whose total equals the second-smallest distinct total — i.e., the smallest total strictly greater than the minimum. If two or more cows share that total, or every cow ties at the minimum, print Tie.

Complexity target

O(N + 7 log 7). Trivial.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> cows = {
        "Bessie","Elsie","Daisy","Gertie","Annabelle","Maggie","Henrietta"
    };
    unordered_map<string,int> total;
    for (auto& c : cows) total[c] = 0;

    int N; cin >> N;
    for (int i = 0; i < N; ++i) {
        string name; int m; cin >> name >> m;
        total[name] += m;
    }

    // Find minimum, then the smallest value strictly greater than min.
    int mn = INT_MAX;
    for (auto& c : cows) mn = min(mn, total[c]);
    int second = INT_MAX;
    for (auto& c : cows)
        if (total[c] > mn) second = min(second, total[c]);

    if (second == INT_MAX) { cout << "Tie\n"; return 0; }

    string ans; int count = 0;
    for (auto& c : cows) if (total[c] == second) { ans = c; ++count; }
    cout << (count == 1 ? ans : string("Tie")) << "\n";
}

Pitfalls

Problem 2 — Hoof, Paper, Scissors

Statement

Two cows play N rounds of a rock-paper-scissors variant. The input lists each round as two integers in {1, 2, 3}, the first cow's gesture and the second cow's. The rules form a 3-cycle (one beats another, that one beats the third, the third beats the first), but Farmer John doesn't know which integer corresponds to which gesture. Compute the maximum number of rounds the first cow can win over all 6 possible mappings of integers ↔ gestures (Hoof, Paper, Scissors).

Constraints

Key idea

Brute force: try all 6 permutations of (1,2,3) → (H,P,S). For each, count rounds where cow 1's mapped gesture beats cow 2's. Output the max. Equivalent shortcut without permutations: for each ordered pair (a,b) with a ≠ b, count rounds with cow-1 gesture a and cow-2 gesture b; the answer is max over the 3 "winning" orientations of the sum of three such counts — but the 6-permutation brute force is simplest and easily fits in N = 100.

Complexity target

O(6 · N) ≈ 600 ops. Trivial.

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);
    for (int i = 0; i < N; ++i) cin >> a[i] >> b[i];

    // perm[g] = which gesture (0=H, 1=P, 2=S) integer g+1 maps to.
    // Winning relation in (H,P,S) space: H beats S, S beats P, P beats H.
    auto beats = [](int x, int y) {
        return (x == 0 && y == 2) ||
               (x == 2 && y == 1) ||
               (x == 1 && y == 0);
    };

    vector<int> perm = {0, 1, 2};
    int best = 0;
    do {
        int wins = 0;
        for (int i = 0; i < N; ++i)
            if (beats(perm[a[i] - 1], perm[b[i] - 1])) ++wins;
        best = max(best, wins);
    } while (next_permutation(perm.begin(), perm.end()));

    cout << best << "\n";
}

Pitfalls

Problem 3 — Cow Tipping

Statement

An N×N grid records each cow as 0 (upright) or 1 (tipped). Farmer John has a machine that, when applied at cell (i, j), flips every cell in the upper-left rectangle [1..i] × [1..j]. Compute the minimum number of machine applications needed to turn every cell to 0. (Applying the same rectangle twice cancels out, so each of the N² rectangles is used at most once.)

Constraints

Key idea

Sweep from the bottom-right corner toward the top-left. At cell (i, j), the only remaining operation that can change it is the one anchored at (i, j) itself (every operation anchored at a (i', j') with i' < i or j' < j has already been decided in this reverse order, and operations anchored further down-right don't touch (i, j)). So if the current value of (i, j) is 1, you must apply the (i, j) rectangle and XOR-flip all cells in [1..i] × [1..j]. This greedy is optimal because the choice at (i, j) is forced.

Complexity target

O(N4) ≈ 10⁴ for N = 10. Plenty.

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<string> g(N);
    for (auto& r : g) cin >> r;

    int ops = 0;
    // Sweep from (N-1, N-1) up to (0, 0).
    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            if (g[i][j] == '1') {
                ++ops;
                // Flip the entire upper-left rectangle [0..i] x [0..j].
                for (int r = 0; r <= i; ++r)
                    for (int c = 0; c <= j; ++c)
                        g[r][c] = (g[r][c] == '0') ? '1' : '0';
            }
        }
    }
    cout << ops << "\n";
}

Pitfalls

What Bronze January 2017 was actually testing