U USACO Prep

USACO 2023 December · Silver · all three problems

← Full December 2023 set · Official results

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

Statement

Farmer John has cows in N distinct weight classes; class i has ai cows of weight wi. He builds at most M towers; in a tower, each cow above another must weigh at least K less than the cow beneath it. Maximize the total number of cows used across all towers.

Constraints

Key idea

Sort weights ascending. Sweep through classes maintaining a queue of "available capacity": when you reach weight class i, every tower whose current top has weight ≤ wi − K is eligible to receive one of the new cows. Greedily place min(ai, eligible capacity + spare new towers) cows, where spare new towers = M − (towers in use). Each placement uses one tower-slot; bookkeep with a queue of (weight, count) pairs of currently-top cows.

Complexity target

O(N log N) for the sort; O(N) sweep.

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; ll M, K;
    cin >> N >> M >> K;
    vector<pair<ll, ll>> cows(N); // (weight, count)
    for (auto& [w, a] : cows) cin >> w >> a;
    sort(cows.begin(), cows.end());

    queue<pair<ll, ll>> available; // tops whose weight allows stacking, FIFO by weight
    ll towersInUse = 0, ans = 0;

    for (auto [w, a] : cows) {
        // Move newly-eligible tops into the "available" pool.
        // (Since we sweep in increasing w, anything with top ≤ w − K is eligible.)
        ll eligible = 0;
        // Re-scan from the front of `available`: all entries with weight ≤ w − K stay eligible.
        // Sum them.
        queue<pair<ll, ll>> keep;
        while (!available.empty()) {
            auto [tw, tc] = available.front(); available.pop();
            if (tw <= w - K) eligible += tc;
            else keep.push({tw, tc});
        }
        available = keep;

        ll spareNew = M - towersInUse;       // can also start new towers
        ll place = min(a, eligible + spareNew);
        ans += place;

        ll useNew = max<ll>(0, place - eligible);
        towersInUse += useNew;
        // Every placed cow becomes a new "top" at weight w.
        available.push({w, place});
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Cycle Correspondence

Statement

Two people independently number N barns with labels 1..N. Each picks the same set of K barns and lays out a cycle on them in some cyclic order. Given the two cyclic sequences (each a permutation of K of the labels 1..N), maximize the number of barns that can receive the same label under both schemes — i.e. choose a single global relabeling that "agrees" with both cyclic structures on as many barns as possible.

Constraints

Key idea

A cycle of length K admits 2K symmetries (K rotations × 2 reflections). For each of the 2K alignments of cycle A onto cycle B, count fixed points (barns whose label matches). The answer is max over alignments. Brute force is O(K2), too slow at K=5·105. Build the permutation that maps "position in A" → "position in B", then for each rotation r, count i with B[(i+r) mod K] = A[i]; that's a circular convolution / FFT, or a clever counting argument with a difference array on the cyclic shift values.

Complexity target

O(K log K) with FFT, or O(N + K) with a difference-array trick on shift counts.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<int> A(K), B(K);
    for (auto& x : A) cin >> x;
    for (auto& x : B) cin >> x;

    // posB[label] = index of that label in B's cycle (only for labels appearing in B).
    vector<int> posB(N + 1, -1);
    for (int i = 0; i < K; ++i) posB[B[i]] = i;

    // For each i in A's cycle, if A[i] also appears in B at position p = posB[A[i]],
    // then a rotation of r = (p - i) mod K aligns this label across both cycles.
    auto best = [&](bool reflect) {
        vector<int> cnt(K, 0);
        for (int i = 0; i < K; ++i) {
            int lab = A[i];
            int p = posB[lab];
            if (p < 0) continue;
            int j = reflect ? (K - 1 - i) : i;
            int r = ((p - j) % K + K) % K;
            cnt[r]++;
        }
        return *max_element(cnt.begin(), cnt.end());
    };

    cout << max(best(false), best(true)) << "\n";
}

Pitfalls

Problem 3 — Target Practice

Statement

Bessie the robot vine starts at position 0 and executes a string of C commands: L moves her one unit left, R one unit right, F fires (hitting whatever target sits at her current position; each target can be hit at most once). T distinct targets sit at integer positions in [−C, C]. You may change at most one command in the string before execution. Maximize the number of targets hit.

Constraints

Key idea

Simulate the original string once, record the position pj after each step. A "change at step k from old → new" shifts all subsequent positions: if old=L, new=R, positions j ≥ k shift by +2; if old=R, new=L, by −2; L↔F or R↔F shifts by ±1; F↔F is a no-op. For each (k, old→new) we want to know: with the shifted trajectory, how many distinct targets get hit by the F-commands? Encode each "would hit target at q" as the multiset of (step j, position pj) at F-steps; after the shift, the F at step j hits position pj + δ if j > k, else pj. Bucket Fs by whether they happen before or after the change point and use prefix/suffix counts indexed by position.

Complexity target

O((T + C) · constant). Each of O(C) candidate changes is processed in amortized O(1) using precomputed histograms over [−C, C].

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, C; cin >> T >> C;
    string cmd; cin >> cmd;
    vector<int> tgt(T);
    set<int> targets;
    for (auto& x : tgt) { cin >> x; targets.insert(x); }

    // Simulate original positions.
    vector<int> pos(C + 1, 0);
    for (int i = 0; i < C; ++i) {
        pos[i + 1] = pos[i] + (cmd[i] == 'L' ? -1 : cmd[i] == 'R' ? 1 : 0);
    }

    auto countHits = [&](int changePos, char newCh) {
        // O(C) — fine for the small subtask, replace with a histogram for full.
        set<int> hit;
        int p = 0;
        for (int i = 0; i < C; ++i) {
            char c = (i == changePos) ? newCh : cmd[i];
            if (c == 'L') --p;
            else if (c == 'R') ++p;
            else if (targets.count(p)) hit.insert(p);
        }
        return (int)hit.size();
    };

    int best = countHits(-1, 'F'); // no change
    for (int i = 0; i < C; ++i)
        for (char nc : {'L', 'R', 'F'})
            if (cmd[i] != nc) best = max(best, countHits(i, nc));
    cout << best << "\n";
    // Full-credit solution replaces countHits with a precomputed
    // count-of-F-hits-per-shift histogram in O(C). [verify editorial]
}

Pitfalls

What Silver December 2023 was actually testing