USACO 2019 December · Bronze · all three problems

← Full December 2019 set · Official results

Problem 1 — Cow Gymnastics

Statement

There are K practice sessions, in each of which N cows are ranked 1..N (best to worst). A pair of cows (a, b) is "consistent" if a outranks b in every one of the K sessions. Count the number of consistent unordered pairs.

Constraints

• 1 ≤ K ≤ 10, 1 ≤ N ≤ 20.
• Each session is a permutation of 1..N.
• Time limit: 2s.

Key idea

With N ≤ 20 just brute-force every ordered pair (a, b) and check whether a is ranked before b in all K sessions. Precompute pos[k][cow] = position of cow in session k. Total work is O(K · N²) ≈ 4000 — trivial.

Complexity target

O(K · N²) time, O(K · N) memory.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int K, N; cin >> K >> N;
    // pos[k][cow] = rank of cow in session k (0 = best).
    vector<vector<int>> pos(K, vector<int>(N + 1, 0));
    for (int k = 0; k < K; ++k) {
        for (int r = 0; r < N; ++r) {
            int c; cin >> c;
            pos[k][c] = r;
        }
    }
    int ans = 0;
    for (int a = 1; a <= N; ++a)
      for (int b = 1; b <= N; ++b) if (a != b) {
        bool ok = true;
        for (int k = 0; k < K && ok; ++k)
            if (pos[k][a] >= pos[k][b]) ok = false;
        if (ok) ++ans;
      }
    cout << ans << "\n";
}

Pitfalls

• Pairs are unordered in the answer but the natural loop is ordered. Iterating ordered (a, b) with a outranking b counts each consistent pair exactly once already — don't divide by 2.
• Input is "best to worst" per session, so the first cow listed has rank 0.
• Don't overengineer. N ≤ 20 makes any clever DP overkill.

Problem 2 — Where Am I?

Statement

A road has N mailboxes painted with letters forming a string S. Find the smallest K such that every length-K substring of S is distinct. (Each contiguous window of K mailboxes uniquely identifies its location.)

Constraints

• 1 ≤ N ≤ 100.
• S consists of uppercase letters A–Z.
• Time limit: 2s.

Key idea

Try K = 1, 2, …, N. For each K collect all length-K substrings into a set<string>; if the set size equals N − K + 1 (no duplicates), output K. Worst case ~N³ string compares which at N = 100 is well under a second.

Complexity target

O(N² log N) using set<string>, easily fast enough.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; string s; cin >> N >> s;
    for (int K = 1; K <= N; ++K) {
        set<string> seen;
        bool ok = true;
        for (int i = 0; i + K <= N; ++i) {
            string t = s.substr(i, K);
            if (!seen.insert(t).second) { ok = false; break; }
        }
        if (ok) { cout << K << "\n"; return 0; }
    }
    cout << N << "\n";  // unreachable but safe
}

Pitfalls

• "Distinct" means every pair of windows differs. A set insert check is the simplest correctness test.
• K = N is always valid (only one substring), so the loop always terminates with an answer.
• Don't reinvent suffix automata for N ≤ 100 — the brute force is the right call.

Problem 3 — Livestock Lineup

Statement

Farmer John must line up 8 cows (Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, Sue) for milking. There are N constraints of the form "cow X must stand next to cow Y." Among all valid lineups, output the lexicographically earliest by cow name.

Constraints

• Exactly 8 cows with the fixed name set above.
• 0 ≤ N ≤ 7 adjacency constraints.
• Time limit: 2s.

Key idea

8! = 40320 permutations. Sort the 8 names lexicographically, iterate next_permutation in alphabetical order, check each adjacency constraint, output the first valid permutation. First-hit guarantees lex-min.

Complexity target

O(8! · N) ≈ 3 · 10⁵ ops — instant.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> cows = {"Beatrice","Belinda","Bella","Bessie","Betsy","Blue","Buttercup","Sue"};
    int N; cin >> N;
    vector<pair<string,string>> req(N);
    for (auto& r : req) {
        string a, b, junk;
        // Form: "A must be milked beside B"
        cin >> a;
        for (int i = 0; i < 4; ++i) cin >> junk;
        cin >> b;
        r = {a, b};
    }
    // cows already sorted alphabetically.
    do {
        bool ok = true;
        for (auto& [a, b] : req) {
            int pa = find(cows.begin(), cows.end(), a) - cows.begin();
            int pb = find(cows.begin(), cows.end(), b) - cows.begin();
            if (abs(pa - pb) != 1) { ok = false; break; }
        }
        if (ok) { for (auto& c : cows) cout << c << "\n"; return 0; }
    } while (next_permutation(cows.begin(), cows.end()));
}

Pitfalls

• Input parsing is the trap. The constraint is a sentence — skip the boilerplate words between the two cow names.
• Adjacency is unordered. |pa − pb| == 1 covers both A-then-B and B-then-A.
• Start sorted. next_permutation only enumerates in lex order from the current state.
• Don't build a graph. Tempting, but the permutation brute force is six lines and bullet-proof.

What Bronze December 2019 was actually testing

• P1 — small-N brute force with the right precomputation. Translating "ranks before in every session" to a rank table.
• P2 — incremental search over K with a duplicate-detection set.
• P3 — permutation brute force + lex-first. Recognize 8! is tiny and pick the simplest correct enumeration.