U USACO Prep

2024 US Open · Silver

← Back to 2024 US Open · Official results page

Silver this round was a classic Silver toolkit: simulation with priority queues, sorting + prefix counts on a cyclic structure, and a tight observation about lexicographically minimal substrings. None require advanced data structures, but each punishes O(N²) implementations.

Paraphrase warning. Statements are summarized from the official problems. Always verify on usaco.org.

S1 · Bessie's Interview

Official statement (cpid=1422)

Statement (paraphrase)

There are N cows applying and K farmers. Cow i needs tᵢ minutes to be interviewed. Farmer j starts with cow j, then immediately picks the lowest-index unassigned cow when free. Bessie is cow N+1. When farmers finish simultaneously, ties are broken so that the cow gets to choose any of the free farmers. Output Bessie's start time, and the bitmask of farmers who could potentially conduct her interview.

Constraints & subtasks

Key idea

Simulate the schedule with a min-heap keyed on (finish_time, farmer_id). Pop the earliest farmer, assign them the next cow, push back with new finish time. When the cow you'd assign next is cow N+1 (Bessie), record the time as her start. For the "which farmers could interview her" mask: at Bessie's start time, every farmer whose finish time equals that minimum could be her interviewer. So pop all farmers with that tied minimum from the heap and mark their IDs.

Complexity

O((N + K) log K) — one heap operation per cow.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<long long> t(N + 1);
    for (int i = 1; i <= N; i++) cin >> t[i];

    // Min-heap of (finish_time, farmer_id). Farmer j starts on cow j (1..K).
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    for (int j = 1; j <= K; j++) pq.push({t[j], j});

    int next_cow = K + 1; // next cow to assign
    long long bessie_start = -1;
    vector<int> mask(K + 1, 0);

    while (!pq.empty()) {
        auto [time, fid] = pq.top();
        if (next_cow == N + 1) {
            // Bessie is up. Collect all farmers tied at this time.
            bessie_start = time;
            while (!pq.empty() && pq.top().first == time) {
                mask[pq.top().second] = 1;
                pq.pop();
            }
            break;
        }
        pq.pop();
        // Assign farmer `fid` to cow `next_cow`.
        long long new_finish = time + t[next_cow];
        pq.push({new_finish, fid});
        next_cow++;
    }

    cout << bessie_start << "\n";
    for (int j = 1; j <= K; j++) cout << mask[j];
    cout << "\n";
}

Pitfalls

S2 · Painting Fence Posts

Official statement (cpid=1423)

Statement (paraphrase)

Same fence as Bronze 2 but bigger: P posts, N cows, coords up to 10⁹. Each cow walks the shorter direction along the closed rectilinear loop between its start and end points. Count, for each post, how many cows pass it (start/end inclusive).

Constraints & subtasks

Key idea

Parameterize each post by arc-length offset around the perimeter (same trick as Bronze 2). Each cow becomes an interval on a cyclic axis of length perimeter, chosen as the shorter of two complementary arcs. Add 1 to that interval and 0 to its complement; we want a range-update, point-query at each post offset. Standard difference-array on the sorted post offsets does it. Watch for the wrap-around when the cow's interval crosses offset 0.

Complexity

O((N + P) log P) — sort posts by offset, binary-search each cow's interval endpoints.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, P;
    cin >> N >> P;
    vector<long long> px(P), py(P);
    for (int i = 0; i < P; i++) cin >> px[i] >> py[i];

    // Walk perimeter to compute each post's arc offset.
    vector<long long> off(P, 0);
    for (int i = 1; i < P; i++)
        off[i] = off[i - 1] + abs(px[i] - px[i - 1]) + abs(py[i] - py[i - 1]);
    long long peri = off[P - 1] + abs(px[0] - px[P - 1]) + abs(py[0] - py[P - 1]);

    // Sorted post offsets with original index for output ordering.
    vector<pair<long long,int>> sorted_off(P);
    for (int i = 0; i < P; i++) sorted_off[i] = {off[i], i};
    sort(sorted_off.begin(), sorted_off.end());

    // Map an (x,y) on the fence -> offset. Pre-bucket edges by axis-aligned key.
    // For simplicity in this reference: O(P) per query, OK for N,P ≤ 2e5 if careful;
    // for full credit replace with binary search by edge bucket.
    auto offsetOf = [&](long long x, long long y) -> long long {
        for (int i = 0; i < P; i++) {
            int j = (i + 1) % P;
            long long x1 = px[i], y1 = py[i], x2 = px[j], y2 = py[j];
            if (x1 == x2 && x == x1 && min(y1,y2) <= y && y <= max(y1,y2))
                return (off[i] + llabs(y - y1)) % peri;
            if (y1 == y2 && y == y1 && min(x1,x2) <= x && x <= max(x1,x2))
                return (off[i] + llabs(x - x1)) % peri;
        }
        return -1;
    };

    // Difference array on sorted_off indices.
    vector<int> diff(P + 2, 0);

    auto addRange = [&](long long a, long long b) {
        // Add 1 to posts with offset in [a, b] (cyclic on [0, peri)).
        // Find first index >= a, last index <= b in sorted_off.
        auto lo = lower_bound(sorted_off.begin(), sorted_off.end(), make_pair(a, INT_MIN));
        auto hi = upper_bound(sorted_off.begin(), sorted_off.end(), make_pair(b, INT_MAX));
        int li = lo - sorted_off.begin(), ri = hi - sorted_off.begin();
        if (a <= b) { diff[li]++; diff[ri]--; }
        else { diff[li]++; diff[P]--; diff[0]++; diff[ri]--; } // wrap
    };

    while (N--) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        long long a = offsetOf(x1, y1), b = offsetOf(x2, y2);
        if (a > b) swap(a, b);
        long long d1 = b - a, d2 = peri - d1;
        if (d1 <= d2) addRange(a, b);
        else addRange(b, a + peri); // wraps
    }

    vector<int> ans(P, 0);
    int run = 0;
    for (int k = 0; k < P; k++) {
        run += diff[k];
        ans[sorted_off[k].second] = run;
    }
    for (int i = 0; i < P; i++) cout << ans[i] << "\n";
}

Pitfalls

S3 · The "Winning" Gene

Official statement (cpid=1424)

Statement (paraphrase)

Given a string S of length N over A..Z. For each pair (K, L) with 1 ≤ L ≤ K ≤ N: in every K-length window of S, find the lex-smallest L-length substring and record its starting position. Let P be the set of recorded positions across all windows for this (K, L). Output, for v = 1..N, the number of (K, L) pairs with |P| = v.

Constraints & subtasks

Key idea

O(N²) pairs (K, L) — we must process each pair in amortized O(1) or O(log N). Fix L. Compute, for each starting position i in 0..N−L, the L-length substring. Use suffix-array / Z-algorithm or pairwise longest common prefix via DP to sort the substrings of length L (or precompute an order over starting positions for each L using O(N²) total work). Then for each K, slide a window of K−L+1 candidate positions and find the lex-smallest; use a monotonic deque keyed on the sorted rank. Counting unique starting positions across all windows = counting how many distinct "argmin" indices appear.

Complexity

O(N²) memory and time with a careful suffix-array-style ordering. ~9·10⁶ ops fits easily.

Reference C++

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

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

    // rank[L][i] = lex rank of S.substr(i, L) among all length-L substrings.
    // Compute via doubling: rank for L=1 is just the character; then rank[2L] from rank[L].
    // For O(N^2) memory we instead build rank[L] one at a time and process all K for it.

    vector<long long> freq(N + 2, 0); // freq[v] = # (K,L) pairs with |P|=v

    // Precompute base rank for L=1.
    vector<int> rnk(N), tmp(N);
    for (int i = 0; i < N; i++) rnk[i] = S[i];

    auto processL = [&](int L) {
        // For this L, valid starting positions: 0..N-L. There are M = N-L+1 of them.
        // For each K in L..N, window is K-L+1 consecutive starting positions.
        // We need |{argmin starting position in each window}| across all M-K+L windows.
        int M = N - L + 1;
        // Monotonic deque on rnk[] over the first L-length substrings.
        for (int K = L; K <= N; K++) {
            int W = K - L + 1; // window size in starting positions
            int numWindows = M - W + 1;
            if (numWindows <= 0) break;
            deque<int> dq;
            set<int> argmins;
            for (int i = 0; i < M; i++) {
                while (!dq.empty() && rnk[dq.back()] > rnk[i]) dq.pop_back();
                dq.push_back(i);
                while (dq.front() <= i - W) dq.pop_front();
                if (i >= W - 1) argmins.insert(dq.front());
            }
            freq[(int)argmins.size()]++;
        }
    };

    // L=1
    processL(1);
    // Build rank for L=2, 3, ..., by extension (O(N) per L using bucket sort on (rnk[i], rnk[i+L/2])
    // — simplified here as direct lex compare for clarity).
    for (int L = 2; L <= N; L++) {
        // tmp[i] = rank of S.substr(i, L), comparing pairs (rnk_prev[i], S[i+L-1]).
        vector<tuple<int,int,int>> keys;
        for (int i = 0; i + L <= N; i++) keys.push_back({rnk[i], S[i + L - 1], i});
        sort(keys.begin(), keys.end());
        int r = 0;
        for (size_t k = 0; k < keys.size(); k++) {
            if (k && (get<0>(keys[k]) != get<0>(keys[k-1]) ||
                       get<1>(keys[k]) != get<1>(keys[k-1]))) r++;
            tmp[get<2>(keys[k])] = r;
        }
        rnk = tmp;
        processL(L);
    }

    for (int v = 1; v <= N; v++) cout << freq[v] << "\n";
}

Pitfalls