U USACO Prep

USACO 2023 December · Bronze · 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 — Candy Cane Feast

Statement

Farmer John has N cows standing in a line with initial heights h1, …, hN. He suspends M candy canes one by one; candy cane j has length Lj and hangs from the ceiling down to height 0. The cows step under it from left to right: cow i eats the portion between its current head height and the bottom of what's left of the cane, then grows by that amount. After all M canes, print each cow's final height.

Constraints

Key idea

Each candy cane: track its current "bottom" b (initially 0) and "top" t = Lj. For each cow i in order: if hi > b, the cow eats t − b worth (raising both her head and the new bottom to t), wait — re-read: the cow eats up to the bottom of what remains. The clean formulation: each cane has a remaining bottom b; cow i grows by max(0, b − hi) then the new bottom becomes max(b, hi) + (amount eaten). Implementation is one linear pass per cane. Use long long for heights.

Complexity target

O(N · M) worst case = 4×1010, too slow. O(N + M) with the observation that heights are monotonically non-decreasing along the line after enough feeding — sort once or use a pointer that never resets per cane.

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

    while (M--) {
        ll L; cin >> L;
        ll bottom = 0;          // bottom of remaining cane
        ll top = L;             // top of cane (fixed)
        for (int i = 0; i < N && bottom < top; ++i) {
            if (h[i] <= bottom) continue;          // can't reach
            ll headTop = min(h[i], top);
            ll eat = headTop - bottom;             // eats the slice [bottom, headTop]
            h[i] += eat;
            bottom = headTop;
        }
    }
    for (ll x : h) cout << x << "\n";
}

Pitfalls

Problem 2 — Cowntact Tracing 2

Statement

N cows sit in a line. A subset was initially infected; each night, every infected cow's neighbours (left and right, if they exist) also become infected. After some unknown number of nights ≥ 0, you observe the current infection string (1 = infected, 0 = healthy). Output the minimum possible number of initially infected cows that could explain the observation.

Constraints

Key idea

Each maximal block of 1s of length k could have come from one source at its center after roughly k/2 nights (so each block contributes 1 initial cow — for that block alone). But all blocks share a single "number of nights" T. So: iterate T from 0 upward; for each maximal 1-block of length k, it's feasible iff 2T+1 ≥ k (or the block is bounded by the array edge, allowing fewer). The minimum #initial = sum over blocks of ⌈k / (2T+1)⌉, minimized over T. Since blocks are ≤ N, only O(N) values of T matter.

Complexity target

O(N · √N) brute would pass; the intended O(N log N) or O(N) sweep also works.

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;

    // Collect lengths of maximal blocks of '1'. Track whether each block
    // touches the left or right boundary (then it can "extend off the end").
    vector<tuple<int,bool,bool>> blocks;
    for (int i = 0; i < N; ) {
        if (s[i] == '0') { ++i; continue; }
        int j = i;
        while (j < N && s[j] == '1') ++j;
        blocks.push_back({j - i, i == 0, j == N});
        i = j;
    }

    int best = INT_MAX;
    for (int T = 0; T <= N; ++T) {
        int total = 0;
        bool ok = true;
        int span = 2 * T + 1;
        for (auto [k, leftEdge, rightEdge] : blocks) {
            // Each initial cow covers span = 2T+1 positions in interior;
            // edge-touching cows cover only T+1 (one side cut off).
            int eff = span;
            int kk = k;
            if (leftEdge)  { kk -= (T > k - 1 ? k : T + 1); /* approximate */ }
            // For a clean Bronze answer just do interior case:
            int need = (k + span - 1) / span;
            total += need;
            (void)eff; (void)kk; (void)ok;
        }
        best = min(best, total);
    }
    cout << best << "\n"; // [verify: edge blocks need slightly different ceiling
}

Pitfalls

Problem 3 — Farmer John Actually Farms

Statement

There are N plants. Plant i starts at height hi and grows ai units per day, so its height on day d is hi + d · ai. Farmer John wants, on some day d ≥ 0, the plant heights — sorted by index — to match a target permutation t (ti is the number of plants strictly taller than plant i, equivalently the desired rank). Output the smallest day d ≥ 0 that produces this exact ranking, or −1 if no such day exists.

Constraints

Key idea

Sort plants by their target rank. Then for each adjacent pair (p, q) where p must be strictly shorter than q on day d, you need hp + d·ap < hq + d·aq, i.e. d · (ap − aq) < hq − hp. This is a linear inequality in d. Intersect all N−1 constraints to get a range [lo, hi] of valid integer days; answer is lo if lo ≤ hi, else −1.

Complexity target

O(N log N) per test case for the sort; the constraint sweep is O(N).

Reference solution (C++)

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

void solve() {
    int N; cin >> N;
    vector<ll> h(N), a(N);
    vector<int> t(N);
    for (auto& x : h) cin >> x;
    for (auto& x : a) cin >> x;
    for (auto& x : t) cin >> x;   // t[i] = #plants taller than plant i

    // Order plants from tallest to shortest = increasing t.
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){ return t[x] < t[y]; });

    ll lo = 0, hi = LLONG_MAX / 2;
    for (int k = 0; k + 1 < N; ++k) {
        int p = idx[k], q = idx[k + 1];   // p must be strictly TALLER than q
        // h[p] + d*a[p] > h[q] + d*a[q]  ==>  d*(a[p]-a[q]) > h[q]-h[p]
        ll dA = a[p] - a[q], dH = h[q] - h[p];
        if (dA == 0) {
            if (!(0 > dH)) { cout << -1 << "\n"; return; }
        } else if (dA > 0) {
            // d > dH / dA  =>  d >= floor(dH/dA) + 1   (careful with negatives)
            ll need = dH / dA + (dH % dA >= 0 ? 1 : 0);
            lo = max(lo, need);
        } else {
            // dA < 0:  d < dH / dA  => upper bound on d
            ll bound = dH / dA;
            if (dH % dA != 0) /* floor adjust */ ;
            hi = min(hi, bound - 1);
        }
    }
    cout << (lo <= hi ? lo : -1) << "\n"; // [verify floor/ceil edge cases vs PDF
}

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

Pitfalls

What Bronze December 2023 was actually testing