U USACO Prep

USACO 2024 December · Gold · all three problems

← Full December 2024 set · Official results · Focused notes on Cowdependence

Source. Titles and constraints below are from usaco.org/index.php?page=dec24results. Approaches are my reading of the problems; treat editorials on usaco.org as authoritative.

Problem 1 — Cowdependence

Statement

N cows in a line each carry a label ai. A "group" must consist of cows that all share a label and all sit within a span of x positions of each other. Every cow joins exactly one group. For each x from 1 to N, report the minimum number of groups across the whole line.

Constraints

Key idea

Per label independently: given the sorted positions p1 < p2 < … < pm, the minimum number of groups at window size x is the count of "breaks" where consecutive pi+1 − pi + (already-spanned width within the current group) exceeds x, plus 1. Equivalently, greedy: start a group at p1, extend while pj − group_start ≤ x. Across all x simultaneously, use the fact that the answer for label L as a function of x is non-increasing and changes only at O(occurrences²) breakpoints in the worst case — but the sum across labels can be computed by a difference-array sweep over x: each gap d = pi+1 − pi contributes +1 to the group count for all x < d.

[verify] The "greedy per label, contribute gaps to diff array" reading matches the intended O((N + max_freq) log N) editorial; check the official write-up for the exact accounting when groups overlap multiple gaps.

Complexity target

O(N · α(N)) or O(N log N) across all x.

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;
    vector<int> a(N);
    for (auto& v : a) cin >> v;

    // positions[label] = sorted list of 1-indexed positions
    unordered_map<int, vector<int>> pos;
    for (int i = 0; i < N; ++i) pos[a[i]].push_back(i + 1);

    // diff[x] += contribution of "another group needed" when window size = x.
    // For each label with positions p_1..p_m, at window size x the greedy
    // group count = 1 + (# of gaps p_{i+1} - group_start that exceed x).
    // A safe upper-bound formulation: each adjacent gap d contributes +1 for
    // every x in [1, d - 1].
    vector<long long> diff(N + 2, 0);
    long long totalLabels = pos.size();

    for (auto& [lab, ps] : pos) {
        // At minimum one group per label at any x >= max span.
        for (int i = 0; i + 1 < (int)ps.size(); ++i) {
            int d = ps[i + 1] - ps[i];
            // a new group is forced when x < d
            diff[1] += 1;
            diff[d] -= 1;
        }
    }
    // groups(x) = totalLabels + prefix_sum(diff[1..x])
    long long running = 0;
    for (int x = 1; x <= N; ++x) {
        running += diff[x];
        cout << (totalLabels + running) << "\n";
    }
}

[verify] This counts every adjacent gap as one mandatory break; the actual greedy may collapse multiple gaps inside a single window of width x and is tighter. Use this as a baseline and refine after reading the editorial.

Pitfalls

Problem 2 — Interstellar Intervals

Statement

Positions 1..N each have a preference in {R, B, X} (X = either). Bessie picks a set of disjoint sub-intervals of [1, N], all of the same length; alternately paints them red and blue (starting color is her choice); positions not covered may take any color. Count the colorings of 1..N consistent with the R/B/X preferences and with some valid interval scheme, modulo a prime.

Constraints

Key idea

Iterate over the common interval length L (1 ≤ L ≤ N). For fixed L, the coloring is determined by an integer offset (where the first interval starts), a starting color, and how many intervals you place. Validity reduces to a per-position check of whether the forced color (R if covered by an odd-indexed interval, B if even-indexed, free otherwise) matches the preference. Compute valid interval counts via prefix sums; total work is O(N / L) per L → harmonic O(N log N).

[verify] The exact "free positions between intervals" rule and what "valid coloring" must include for uncovered positions needs careful reading of the PDF; the harmonic O(N log N) framing is the typical Gold pattern but the details depend on whether uncovered positions are X-only or free.

Complexity target

O(N log N).

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    string s; cin >> s;

    // forced[i] = 'R' or 'B' if position i must be that color, else 'X'
    // For an interval length L starting at p with starting color C, positions
    // p..p+L-1 are color C, p+L..p+2L-1 are the opposite, etc.
    // Number of free positions per coloring = number of X positions not covered.
    // Each X contributes a factor of 2 (independent red/blue choice if free).

    // pow2[k] precomputed
    vector<ll> pow2(N + 1, 1);
    for (int i = 1; i <= N; ++i) pow2[i] = pow2[i - 1] * 2 % MOD;

    // prefR[i]/prefB[i]/prefX[i] = counts of R/B/X in s[0..i-1]
    vector<int> pR(N+1,0), pB(N+1,0), pX(N+1,0);
    for (int i = 0; i < N; ++i) {
        pR[i+1] = pR[i] + (s[i]=='R');
        pB[i+1] = pB[i] + (s[i]=='B');
        pX[i+1] = pX[i] + (s[i]=='X');
    }

    ll ans = 0;
    // Enumerate interval length L.
    for (int L = 1; L <= N; ++L) {
        // For each start position p in [0, L) and each starting color, count
        // packings where stripes of length L alternate over [p, N).
        // Validity: in each red stripe, count of B must be 0; in each blue
        // stripe, count of R must be 0; X is always fine.
        for (int p = 0; p < L && p < N; ++p) {
            for (int startColor = 0; startColor < 2; ++startColor) {
                bool ok = true;
                int xCovered = 0;
                int k = 0; // stripe index
                for (int seg = p; seg < N; seg += L, ++k) {
                    int lo = seg, hi = min(N, seg + L);
                    int rcnt = pR[hi]-pR[lo], bcnt = pB[hi]-pB[lo], xcnt = pX[hi]-pX[lo];
                    int color = (startColor + k) & 1; // 0=R, 1=B
                    if (color==0 && bcnt) { ok = false; break; }
                    if (color==1 && rcnt) { ok = false; break; }
                    xCovered += xcnt;
                }
                if (!ok) continue;
                int xTotal = pX[N];
                int xFree  = xTotal - xCovered;
                ans = (ans + pow2[xFree]) % MOD;
            }
        }
    }
    cout << ans << "\n";
}

[verify] The above is O(N²/L) per L → O(N² H_N). For N=5·105 that's too slow; the intended solution likely fixes a single starting offset per L and uses prefix sums to jump-test stripes in O(1) each, giving harmonic O(N log N). Treat as a correctness baseline.

Pitfalls

Problem 3 — Job Completion

Statement

N jobs are given. Each job i has a release time si (earliest time at which it becomes available) and a duration ti. You work serially without pause; at any moment after a job has started you can't switch. Pick a subset and order of jobs to maximize the count of jobs completed (a job counts only if started ≥ si and finished before the next one starts).

Constraints

Key idea

Classic "maximum number of deadline jobs" pattern (Earliest-Deadline-First with a swap heap). Sort jobs by release time s. Sweep; maintain a max-heap of accepted durations. Try to take the next job: advance current time to max(time, si), add ti, push ti onto the heap. If the new completion time exceeds the next job's release time — well, that's only a problem if you later regret it; instead use the variant where you keep the heap of accepted durations and, when adding a job would violate the constraint, pop the heaviest duration if it exceeds ti. Here the "deadline" is "starts before its successor's release," so we sort by s and greedily pack.

Complexity target

O(N log N) per test case.

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 T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<pair<ll,ll>> jobs(N); // (s_i, t_i)
        for (auto& [s, t] : jobs) cin >> s >> t;
        sort(jobs.begin(), jobs.end()); // by release time ascending

        priority_queue<ll> heap; // max-heap of accepted durations
        ll cur = 0;              // current wall-clock time
        ll totalDur = 0;
        for (auto [s, t] : jobs) {
            // We may idle until s, but only if cur < s.
            ll newCur = max(cur, s) + t;
            // Tentatively accept this job.
            heap.push(t);
            cur = newCur;
            totalDur += t;
            // If our current time has somehow exceeded the next job's release
            // we're forced to drop the worst duration. (Captured by checking
            // cur > s of *next* job in the outer loop -- here we check post-hoc.)
            // The cleanest invariant: if at any point cur > s_i for the i'th
            // job we are about to consider, we've over-spent; pop the biggest
            // duration on the heap to recover.
        }
        // The above tentative-accept logic still needs the "regret" step:
        // walk jobs again and enforce cur(after i) <= s(i+1).
        // (Editorial-style: rebuild with regret.)
        // For clarity, we redo with regret inline:
        while (!heap.empty()) heap.pop();
        cur = 0; ll accepted = 0;
        for (int i = 0; i < N; ++i) {
            auto [s, t] = jobs[i];
            ll start = max(cur, s);
            // Tentative accept
            heap.push(t);
            cur = start + t;
            ++accepted;
            // If after accepting, we have over-committed past the NEXT job's
            // release, we may need to drop the longest job so far.
            if (i + 1 < N && cur > jobs[i + 1].first) {
                ll worst = heap.top(); heap.pop();
                cur -= worst;
                --accepted;
            }
        }
        cout << accepted << "\n";
    }
}

[verify] The exact "what counts as a completed job" rule (does the last job need to finish before some global deadline, or just respect successor release times?) needs the PDF. The EDF-with-regret heap pattern is the standard tool either way.

Pitfalls

What Gold December 2024 was actually testing