U USACO Prep

USACO 2021 January · Bronze · all three problems

← Full January 2021 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan21results. 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 — Uddered but not Herd

Statement

Bessie has a fixed "cowphabet" — a permutation of the 26 lowercase letters — that she recites repeatedly. Farmer John hears a subset of those letters in order, forming a target string T. Given the cowphabet ordering and T, compute the minimum number of complete cowphabet recitations needed to produce T.

Constraints

Key idea

Build pos[c] = position of letter c in the cowphabet. Walk through T; maintain the position of the last letter heard. If the next letter's pos is strictly greater than the previous, we stay in the same recitation. Otherwise we must start a new one — increment the counter. The answer starts at 1.

Complexity target

O(|T| + 26): a single linear scan.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string alpha, t;
    cin >> alpha >> t;

    int pos[26];
    for (int i = 0; i < 26; ++i) pos[alpha[i] - 'a'] = i;

    // Walk T. Each time we cannot stay strictly to the right of
    // the previous position in the cowphabet, start a new recitation.
    int recitations = 1;
    int last = -1;
    for (char c : t) {
        int p = pos[c - 'a'];
        if (p <= last) ++recitations;   // need to restart
        last = (p <= last) ? p : p;     // updated either way
    }
    cout << recitations << "\n";
}

Pitfalls

Problem 2 — Even More Odd Photos

Statement

Farmer John has N cows with breed IDs. He wants to partition them into a sequence of non-empty groups G1, G2, …, GK such that sum(G1) is even, sum(G2) is odd, sum(G3) is even, alternating, and every cow is used exactly once. Maximize K.

Constraints

Key idea

Only parities matter. Let E = #even cows, O = #odd cows. Each "even group" can be a single even cow, or a pair of odds (since odd+odd = even). Each "odd group" needs an odd count of odd-parity cows; the cheapest is a single odd cow. Simulate: alternately consume an even group (prefer one even, otherwise two odds) then an odd group (one odd). Stop when the next required type can't be formed. The final group is allowed to merge all remaining cows of the right parity into one big group (since the leftovers must still match parity).

Complexity target

O(N) — bounded number of alternations.

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;
    int E = 0, O = 0;
    for (int i = 0; i < N; ++i) {
        int x; cin >> x;
        if (x & 1) ++O; else ++E;
    }

    // Greedy: alternate forming an "even" group then an "odd" group.
    // - even group : 1 even cow, OR 2 odd cows.
    // - odd group  : 1 odd cow.
    int groups = 0;
    bool needEven = true;
    while (true) {
        if (needEven) {
            if (E > 0) { --E; ++groups; }
            else if (O >= 2) { O -= 2; ++groups; }
            else break;
        } else {
            if (O >= 1) { --O; ++groups; }
            else break;
        }
        needEven = !needEven;
    }
    // Remaining leftovers must keep the parity of the LAST group still
    // valid — i.e. they all join the last group. They don't change its
    // parity if they're (leftover evens) or (an even number of odds);
    // an extra odd would flip parity, which is fine only if it matches
    // the slot we just produced.
    cout << groups << "\n";
}

Pitfalls

Problem 3 — Just Stalling

Statement

Farmer John has N cows with heights hi and N stalls with height limits sj. A cow can occupy stall j only if hi ≤ sj. Count the number of distinct assignments (bijections from cows to stalls) such that every cow fits in its stall.

Constraints

Key idea

Sort cows by height descending. The tallest cow can go in any stall that fits her — say there are c1 such stalls. The next-tallest has c2 fitting stalls, but one of those is already used, so she gets c2 − 1 choices. In general, the i-th cow (1-indexed in sorted order) has ci − (i − 1) choices. Multiply them. If any factor is ≤ 0 the answer is 0.

Complexity target

O(N²) — for each cow, scan stalls to count fits. Trivially fast for N ≤ 20.

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

    // Sort cows tallest -> shortest. For the i-th cow (0-indexed in
    // this order), count stalls that fit her, subtract i (already used
    // by taller cows). Multiply.
    sort(h.begin(), h.end(), greater<ll>());
    ll ans = 1;
    for (int i = 0; i < N; ++i) {
        ll fits = 0;
        for (ll v : s) if (v >= h[i]) ++fits;
        ll choices = fits - i;
        if (choices <= 0) { ans = 0; break; }
        ans *= choices;
    }
    cout << ans << "\n";
}

Pitfalls

What Bronze January 2021 was actually testing