U USACO Prep

2023 February Silver · All three problems

← Back to Feb 2023 hub · Official results

Canonical statements live at usaco.org. Statements below are my paraphrase — open the official problem PDFs before submitting your own solution. Each problem links to the official viewer.

Problem 1 · Bakery

Official problem (cpid=1302)

Statement (paraphrased)

Bessie's bakery produces a cookie in tC time and a muffin in tM. She can spend moonies to permanently reduce either time by 1 per moonie (but never below 1). Each of N friends orders ai cookies and bi muffins and will wait at most ci total time — meaning ai·tC + bi·tM ≤ ci. Find the minimum moonies so every friend's inequality holds simultaneously.

Constraints

Key idea

Total cost = (initial tC − new tC) + (initial tM − new tM). Enumerate the new cookie-time x ∈ [1, tC] — but only O(N+1) values of x matter, namely those that become "active" constraints (each friend gives at most one bend point). For each candidate x, the minimum legal new muffin time is y(x) = max over i of ceil((ci − ai·x) / bi), then clamp to [1, tM]. Cost = (tC−x) + (tM−y). Sweep x downward; update y incrementally.

Complexity target

O(N · tC) naive; O(N log N) with the candidate-x sweep. With N ≤ 100, even O(N²) per test case is fine.

C++ reference solution

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

ll need_y(const vector<ll>& a, const vector<ll>& b, const vector<ll>& c, ll x){
    ll y = 1;
    for (size_t i = 0; i < a.size(); ++i){
        lll rem = (lll)c[i] - (lll)a[i]*x;
        if (rem < b[i]) return -1;             // even y=1 fails
        ll need = (ll)((rem) / b[i]);           // floor since rem ≥ b[i] > 0
        if (need < y) y = y;                    // keep max
        else y = need;                          // tighter
    }
    return y;
}

int main(){
    int T; cin >> T;
    while (T--){
        int N; ll tC, tM; cin >> N >> tC >> tM;
        vector<ll> a(N), b(N), c(N);
        for (int i = 0; i < N; ++i) cin >> a[i] >> b[i] >> c[i];
        // candidate xs: t_C, and each c_i/a_i breakpoint, clamped to [1, t_C]
        set<ll> xs{1, tC};
        for (int i = 0; i < N; ++i){
            ll x = c[i] / a[i];
            if (x >= 1 && x <= tC) { xs.insert(x); if (x+1 <= tC) xs.insert(x+1); }
        }
        ll best = LLONG_MAX;
        for (ll x : xs){
            ll y = 1;
            bool ok = true;
            for (int i = 0; i < N; ++i){
                lll rem = (lll)c[i] - (lll)a[i]*x;
                if (rem < (lll)b[i]) { ok = false; break; }
                ll need_y = (ll)(rem / b[i]); if (need_y > y) y = need_y;
            }
            if (!ok) continue;
            if (y > tM) y = tM;
            ll cost = (tC - x) + (tM - y);
            if (cost < best) best = cost;
        }
        cout << best << '\n';
    }
}

Pitfalls

Problem 2 · Cow-libi

Official problem (cpid=1303)

Statement (paraphrased)

G grazings happened at points (xg, yg) at times tg. Each of N suspect cows claims to have been at (xc, yc) at time tc. Cows move at speed 1. A cow is guilty if her alibi is consistent with her having committed all G grazings (i.e. she could have visited every grazing site within the time budget). Output the count of innocent cows — those whose alibi is impossible.

Constraints

Key idea

For a cow with alibi (x, y, t) to be guilty she must (a) reach the grazing immediately before t in time, AND (b) reach the grazing immediately after t in time. Sort grazings by t. For each suspect, binary-search the two adjacent grazings and check Euclidean distance ≤ |Δt|. If either check fails, the cow is innocent. (Special cases: t before all grazings → only the "next" check; t after all → only the "previous" check.)

Complexity target

O((G + N) log G).

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 G, N; cin >> G >> N;
    vector<ll> gx(G), gy(G), gt(G);
    vector<int> idx(G);
    for (int i = 0; i < G; ++i){ cin >> gx[i] >> gy[i] >> gt[i]; idx[i] = i; }
    sort(idx.begin(), idx.end(), [&](int a, int b){ return gt[a] < gt[b]; });
    vector<ll> sx(G), sy(G), st(G);
    for (int i = 0; i < G; ++i){ sx[i]=gx[idx[i]]; sy[i]=gy[idx[i]]; st[i]=gt[idx[i]]; }

    auto reach = [&](ll x1, ll y1, ll t1, ll x2, ll y2, ll t2){
        ll dx = x1 - x2, dy = y1 - y2, dt = t1 - t2; if (dt < 0) dt = -dt;
        return (long double)(dx*dx + dy*dy) <= (long double)dt*dt;
    };

    int innocent = 0;
    while (N--){
        ll x, y, t; cin >> x >> y >> t;
        int p = (int)(lower_bound(st.begin(), st.end(), t) - st.begin());
        bool ok = true;
        if (p > 0   && !reach(x, y, t, sx[p-1], sy[p-1], st[p-1])) ok = false;
        if (p < G   && !reach(x, y, t, sx[p],   sy[p],   st[p]  )) ok = false;
        if (!ok) ++innocent;
    }
    cout << innocent << '\n';
    return 0;
}

Pitfalls

Problem 3 · Moo Route II

Official problem (cpid=1304)

Statement (paraphrased)

Bessie starts at airport 1 at time 0. There are M time-travel flights, each from airport u at departure r to airport v with arrival s (s may be < r). To take a flight from airport v she must arrive there at time ≤ r − av, where av is the layover time. Output the earliest arrival time at each of the N airports (−1 if unreachable).

Constraints

Key idea

Dijkstra fails because edge weights can be negative. The crucial observation: sort each airport's outgoing flights by departure time descending. When you visit airport u with current best earliest-arrival tu, process flights in that order and stop at the first flight whose departure r < tu + au. Crucially, once you've used a flight, never re-use it — each flight is processed exactly once across the whole algorithm. Re-relaxing v? Push v back into the queue but skip already-used outgoing flights. This gives O((N+M) log) or O(N+M) total.

Complexity target

O((N+M) log N).

C++ reference solution

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<tuple<ll,int,ll>> raw(M); // (r, v, s) per flight from u
    vector<vector<int>> out(N+1);
    vector<ll> r(M), s(M); vector<int> to(M), from(M);
    for (int i = 0; i < M; ++i){
        int u, v; cin >> u >> r[i] >> v >> s[i];
        from[i]=u; to[i]=v;
        out[u].push_back(i);
    }
    vector<ll> a(N+1, 0); for (int i = 1; i <= N; ++i) cin >> a[i];
    for (int u = 1; u <= N; ++u){
        sort(out[u].begin(), out[u].end(), [&](int x, int y){ return r[x] > r[y]; });
    }

    vector<ll> dist(N+1, INF); dist[1] = 0;
    vector<int> ptr(N+1, 0);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.push({0, 1});
    while (!pq.empty()){
        auto [t, u] = pq.top(); pq.pop();
        if (t != dist[u]) continue;
        ll readyT = t + (u == 1 ? 0 : a[u]);
        while (ptr[u] < (int)out[u].size()){
            int e = out[u][ptr[u]];
            if (r[e] < readyT) break;       // remaining flights depart earlier, can't catch
            int v = to[e];
            if (s[e] < dist[v]){ dist[v] = s[e]; pq.push({s[e], v}); }
            ptr[u]++;
        }
    }
    for (int i = 1; i <= N; ++i) cout << (dist[i] == INF ? -1 : dist[i]) << '\n';
    return 0;
}

Pitfalls