U USACO Prep

USACO 2022 December · Bronze · all three problems

← Full December 2022 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec22results. 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 — Cow College

Statement

Farmer John opens a university for cows. Cow i is willing to pay at most ci in tuition. FJ must set a single price p that applies to every cow; only cows with ci ≥ p enroll, and each enrolled cow pays exactly p. Maximize total revenue p · #{i : ci ≥ p}, and print that maximum together with the smallest p achieving it.

Constraints

Key idea

The optimal price is always equal to some ci (raising p past a ci drops that cow, lowering past one only loses money). Sort the willingness values in descending order; if the sorted array is w1 ≥ w2 ≥ …, then choosing p = wk yields revenue k · wk. Take the maximum, breaking ties by smaller p.

Complexity target

O(N log N) for the sort, O(N) sweep. Trivially fast at N = 105.

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

    // Sort descending: the k-th value (1-indexed) is the price that
    // exactly k cows are willing to pay.
    sort(c.begin(), c.end(), greater<ll>());

    ll bestRev = 0, bestPrice = 0;
    for (int k = 1; k <= N; ++k) {
        ll p = c[k - 1];
        ll rev = (ll)k * p;
        // Strictly greater revenue, OR equal revenue at a smaller price.
        if (rev > bestRev || (rev == bestRev && p < bestPrice)) {
            bestRev = rev;
            bestPrice = p;
        }
    }
    cout << bestRev << " " << bestPrice << "\n";
}

Pitfalls

Problem 2 — Feeding the Cows

Statement

N cows stand at positions 1..N along a line; cow i is either a Guernsey (G) or a Holstein (H). FJ plants grass patches at integer positions; each patch is either G-type or H-type. A cow of breed B must reach a B-type patch within distance K. Output the minimum number of patches and one valid placement (positions and breeds).

Constraints

Key idea

Handle each breed independently. Sweep cows of breed B from left to right; whenever the leftmost uncovered cow at position x has no patch within K, plant a B-patch at x + K — this is the rightmost legal spot that still covers x and is the greediest choice. Skip to the first cow past (x + 2K). The answer is the sum of patches over both breeds.

Complexity target

O(N) per test case after a linear scan of positions for each breed.

Reference solution (C++)

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

// For a sorted list of cow positions of one breed, greedily cover them with
// patches: every uncovered leftmost cow at x forces a patch at x+K, which
// then covers [x, x+2K].
int coverGreedy(const vector<int>& pos, int K, vector<int>& outPatches) {
    int n = pos.size(), i = 0, placed = 0;
    while (i < n) {
        int patch = pos[i] + K;          // rightmost legal spot covering pos[i]
        outPatches.push_back(patch);
        ++placed;
        // Advance past all cows in [patch-K, patch+K] = [pos[i], pos[i]+2K].
        int limit = patch + K;
        while (i < n && pos[i] <= limit) ++i;
    }
    return placed;
}

void solve() {
    int N, K; cin >> N >> K;
    string s; cin >> s;
    vector<int> gp, hp;
    for (int i = 0; i < N; ++i) (s[i] == 'G' ? gp : hp).push_back(i + 1);
    vector<int> gPatch, hPatch;
    int total = coverGreedy(gp, K, gPatch) + coverGreedy(hp, K, hPatch);
    cout << total << "\n";
    for (int p : gPatch) cout << p << " G\n";
    for (int p : hPatch) cout << p << " H\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}

Pitfalls

Problem 3 — Reverse Engineering

Statement

Elsie claims to have written a program of nested if/else statements, where each condition tests a single boolean input variable; every leaf returns 0 or 1. She shows M (input, output) examples on N variables. Decide whether some such program is consistent with all M examples (print OK) or whether her claims must contradict (print LIE).

Constraints

Key idea

Such a program is exactly a decision tree on the N variables, which can represent any function as long as no two examples have identical inputs but different outputs. Stronger: it's consistent iff at every splittable subset we can find one variable that partitions it into smaller subsets whose outputs are each consistent. Equivalent shortcut: as long as no two rows have the same N-bit input and different outputs, "OK"; otherwise "LIE". (Variables aren't restricted in usage count.)

Complexity target

O(M² · N) checking pairs — trivial at N, M ≤ 100.

Reference solution (C++)

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

// A nested if/else over single-variable tests is a decision tree; it can
// realize any function on the inputs that actually appear, PROVIDED no two
// identical input rows have conflicting outputs.
void solve() {
    int N, M; cin >> N >> M;
    vector<string> in(M);
    vector<int>    out(M);
    for (int i = 0; i < M; ++i) cin >> in[i] >> out[i];

    // Recursive: pick any variable that splits the current subset into two
    // non-trivial groups whose outputs are each consistent.
    function<bool(vector<int>&)> ok = [&](vector<int>& rows) -> bool {
        if (rows.empty()) return true;
        int v0 = out[rows[0]];
        bool same = true;
        for (int r : rows) if (out[r] != v0) { same = false; break; }
        if (same) return true;
        for (int j = 0; j < N; ++j) {
            vector<int> A, B;
            for (int r : rows) (in[r][j] == '0' ? A : B).push_back(r);
            if (A.empty() || B.empty()) continue;   // didn't split
            if (ok(A) && ok(B)) return true;
        }
        return false;
    };

    vector<int> all(M);
    iota(all.begin(), all.end(), 0);
    cout << (ok(all) ? "OK" : "LIE") << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}

Pitfalls

What Bronze December 2022 was actually testing