U USACO Prep

2024 February Gold · All three problems

← Back to Feb 2024 hub · Official results

Gold is above the level I compete in. These are exposure write-ups — I read the editorial, then re-implement. Statements paraphrased; canonical source is usaco.org.

Problem 1 · Bessla Motors

Official problem (cpid=1401)

Statement (paraphrased)

An undirected weighted graph has N nodes and M edges; nodes 1..C are charging stations, the rest are destinations. A tractor starts at any station with a full charge and can travel up to 2R miles per leg, meaning each station can directly reach any node within R miles (you must save half the charge for the return). A destination is "well-connected" if it is reachable within R miles from at least K distinct stations. List all well-connected destinations in increasing order.

Constraints

Key idea

Multi-source Dijkstra where every charging station is a source at distance 0. But that only counts the closest station, not all of them. Trick: run a modified Dijkstra that maintains, per node, the set of up to K closest distinct station-sources that can reach it within R. Equivalently, push at most K state entries per node (one per source) and drop any that exceed distance R. Because K ≤ 10, the total state is bounded by 10N.

Complexity target

O(K · (N + M) log N).

C++ reference solution

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, C, K; ll R;
    cin >> N >> M >> C >> R >> K;
    vector<vector<pair<int,ll>>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v; ll w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    // Dijkstra with multi-source labels; cap per-node to K distinct sources.
    vector<vector<int>> sources(N + 1);
    priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<>> pq;
    for (int s = 1; s <= C; ++s) {
        pq.push({0, s, s});
    }
    while (!pq.empty()) {
        auto [d, u, src] = pq.top(); pq.pop();
        if (d > R) continue;
        auto& sv = sources[u];
        if ((int)sv.size() >= K) continue;
        if (find(sv.begin(), sv.end(), src) != sv.end()) continue;
        sv.push_back(src);
        for (auto [v, w] : g[u]) {
            if (d + w <= R) pq.push({d + w, v, src});
        }
    }

    vector<int> ans;
    for (int v = C + 1; v <= N; ++v)
        if ((int)sources[v].size() >= K) ans.push_back(v);
    cout << ans.size() << '\n';
    for (int v : ans) cout << v << '\n';
    return 0;
}

Pitfalls

Problem 2 · Milk Exchange (Gold)

Official problem (cpid=1402)

Statement (paraphrased)

N cows around a circle, each with a bucket of capacity ai. Every minute each cow passes her full bucket clockwise; if her downstream neighbour's capacity is smaller, the excess is lost. For each minute t = 1..N, output the total remaining milk.

Constraints

Key idea

After t minutes, the milk at position i is min(ai−t, ai−t+1, …, ai) — a sliding window minimum on the circular sequence of length N. Sum across all i gives the total. Compute, for each pair (i, t), how much each "valley" aj contributes. Standard trick: for each j, find the maximal contiguous interval of i in which aj is the min of the window of length t. Using monotonic stacks, compute for every j the number of length-t windows it dominates, summed over t = 1..N. That gives all N answers in O(N) or O(N log N).

Complexity target

O(N log N) with offline sweep; O(N) is possible with careful monotonic-stack accounting.

C++ reference solution

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> a(2*N);
    for (int i = 0; i < N; ++i) { cin >> a[i]; a[i + N] = a[i]; }

    // For each j in [0, 2N), find L[j], R[j] = nearest strictly smaller on each side.
    int L = 2 * N;
    vector<int> left_smaller(L, -1), right_smaller(L, L);
    {
        stack<int> st;
        for (int i = 0; i < L; ++i) {
            while (!st.empty() && a[st.top()] >= a[i]) st.pop();
            left_smaller[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
    }
    {
        stack<int> st;
        for (int i = L - 1; i >= 0; --i) {
            while (!st.empty() && a[st.top()] > a[i]) st.pop();
            right_smaller[i] = st.empty() ? L : st.top();
            st.push(i);
        }
    }
    // For each minute t in [1, N], the total = sum over j of a[j] * (#windows of length t
    // ending in [j .. j + (range where j is the min)] capped by N positions).
    // Implementation: contribute a[j] to a difference array indexed by t.
    vector<ll> diff(N + 2, 0);
    for (int j = 0; j < L; ++j) {
        ll left  = j - left_smaller[j];        // window can start as far left as left_smaller[j]+1
        ll right = right_smaller[j] - j;       // window can end as far right as right_smaller[j]-1
        ll span  = left * right;               // # of (start, end) windows where j is the min
        // ... distribute span across window-lengths t in [1..N] uniformly; details elided.
        (void)span;
    }
    // After distributing, prefix-sum diff to get answer[t] for t = 1..N.
    for (int t = 1; t <= N; ++t) cout << diff[t] << '\n'; // placeholder
    return 0;
}

The full distribution step is the heart of the problem — left as a placeholder while I work the editorial. The structure above (monotonic stack + per-element contribution) is the intended frame.

Pitfalls

Problem 3 · Quantum Moochanics

Official problem (cpid=1403)

Statement (paraphrased)

N particles on a line, indices in increasing position. Particles at odd indices move right at speed si, even indices move left. Bessie observes the system at times 1, 2, 3, … with gaps growing; each observation reverses every particle's direction. Two particles that meet annihilate. For each particle, report the observation index after which it disappears.

Constraints

Key idea

Each adjacent pair (1,2), (3,4), … faces inward at start and outward after one observation, etc. Between observation k and k+1 the gap is k seconds. Compute, for each adjacent inward-facing pair, the absolute time at which they would collide if unobstructed. Use a stack/priority-queue sweep (similar to "crash sequence" problems): when a pair annihilates, the neighbours on either side become a new pair, and we recompute their collision time. Keep a sorted heap of "next collision"; pop the earliest, mark both, splice. The tricky part is computing the right collision time given the alternating observation pattern; that's a piecewise-linear function of the schedule that you evaluate analytically per pair (not by simulation).

Complexity target

O(N log N).

C++ reference solution

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

// Each adjacent inward pair (left moving right at s_L, right moving left at s_R) closes
// the gap (p_R - p_L) at rate (s_L + s_R) while facing inward. Observations flip directions.
// Compute collision "schedule-time" T*(L,R) by integrating the alternating velocity over k.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<ll> p(N), s(N);
        for (auto& x : p) cin >> x;
        for (auto& x : s) cin >> x;

        // Doubly-linked list of indices to support splicing on annihilation.
        vector<int> L(N), R(N);
        for (int i = 0; i < N; ++i) { L[i] = i - 1; R[i] = i + 1; }
        R[N-1] = -1;

        // Priority queue of (collision-observation-index, left-index, version) tuples.
        // Version-stamp lazy deletion. Implementation of collision time omitted.
        vector<int> ans(N, -1);
        // ... sweep loop ...
        for (int i = 0; i < N; ++i) cout << ans[i] << " \n"[i == N-1];
    }
    return 0;
}

Skeleton only — the closed-form collision-observation calculation is the hard step and is best understood from the official editorial.

Pitfalls