U USACO Prep

USACO 2019 December · Silver · all three problems

← Full December 2019 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec19results. 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 — MooBuzz

Statement

In FizzBuzz, the cows say "Moo" on integers not divisible by 3 or 5 (skipping the ones that would have been Fizz, Buzz, or FizzBuzz). Given N, output the N-th integer the cows say "Moo" on.

Constraints

Key idea

In every block of 15 consecutive integers exactly 8 are coprime to {3, 5}: positions 1, 2, 4, 7, 8, 11, 13, 14. So the N-th moo is 15 · ((N − 1) / 8) + base[(N − 1) % 8], where base lists those 8 offsets. Constant-time arithmetic.

Complexity target

O(1).

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);
    ll N; cin >> N;
    int base[8] = {1, 2, 4, 7, 8, 11, 13, 14};
    ll q = (N - 1) / 8, r = (N - 1) % 8;
    cout << 15 * q + base[r] << "\n";
}

Pitfalls

Problem 2 — Meetings

Statement

N cows stand on a number line of length L. Each cow i has weight wi, position xi, and initial direction di ∈ {−1, +1}, walking at speed 1. When two cows meet they swap directions (equivalently the labels pass through). When a cow reaches an endpoint it falls off. The contest ends at time T, the first instant when the total weight on the right end equals at least half the total weight. Output the number of unordered cow-pair meetings that occur in [0, T].

Constraints

Key idea

Two-step trick. (1) Since cows are indistinguishable physical points (swaps = ghost pass-throughs), the set of fall-off times equals the multiset of times {(L − x)/1 : d=+1} ∪ {x/1 : d=−1}, but the weight delivered to each end is not the same multiset — sort cows left-to-right by x and assign right-end fall-offs to the right-most "right-going-ghosts" (the K largest-positioned cows whose ghost goes right), where K = number of +1 cows. From this we get T by sorting fall-off times and prefix-summing weight on the right. (2) For the meeting count, a +1 cow at position a meets a −1 cow at position b > a within time T iff (b − a) ≤ 2T. Sort the two groups by position and two-pointer-count pairs with gap ≤ 2T.

Complexity target

O(N log N) overall — two sorts and two linear sweeps.

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; ll L; cin >> N >> L;
    vector<ll> W(N), X(N), D(N);
    for (int i = 0; i < N; ++i) cin >> W[i] >> X[i] >> D[i];
    vector<int> ord(N); iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b){ return X[a] < X[b]; });

    // Collect ghost fall times and where each ghost exits (left = 0, right = 1).
    // Ghost of cow i with d = +1 exits right at time L - x; d = -1 exits left at time x.
    vector<pair<ll,int>> ev; // (time, side) side 1 = right, 0 = left
    for (int i = 0; i < N; ++i)
        ev.push_back({D[i] == 1 ? L - X[i] : X[i], (int)(D[i] == 1)});
    // Assign weights to fall-events by matching sorted positions to sorted ghost arrivals on each side.
    // Standard trick: the weight that falls off the right end at the k-th right-event is the weight of the
    // k-th right-most cow.
    vector<ll> rightW, leftW;
    for (int idx : ord) {
        // gather in left-to-right cow order; we'll pair from the back for right side, front for left side.
        (void)idx;
    }
    // Count right-going ghosts.
    int R = 0; for (int i = 0; i < N; ++i) if (D[i] == 1) ++R;
    // The R rightmost cows by position keep weights for right-end fall-offs.
    vector<ll> sortedRightTimes, sortedLeftTimes;
    for (auto& e : ev) (e.second ? sortedRightTimes : sortedLeftTimes).push_back(e.first);
    sort(sortedRightTimes.begin(), sortedRightTimes.end());
    sort(sortedLeftTimes.begin(), sortedLeftTimes.end());
    // Right-end weights, in time order, are the weights of the R rightmost cows in left-to-right order.
    vector<ll> rightWeights, leftWeights;
    for (int k = N - R; k < N; ++k) rightWeights.push_back(W[ord[k]]);
    for (int k = 0; k < N - R; ++k) leftWeights.push_back(W[ord[k]]);

    // Combine all fall events sorted by time; track cumulative right-end weight.
    vector<tuple<ll,int,ll>> evts; // (time, side, w)
    for (int k = 0; k < (int)sortedRightTimes.size(); ++k) evts.push_back({sortedRightTimes[k], 1, rightWeights[k]});
    for (int k = 0; k < (int)sortedLeftTimes.size();  ++k) evts.push_back({sortedLeftTimes[k],  0, leftWeights[k]});
    sort(evts.begin(), evts.end());
    ll total = 0; for (auto w : W) total += w;
    ll need = (total + 1) / 2;     // "at least half"
    ll cum = 0, T = 0;
    for (auto& [t, side, w] : evts) {
        if (side == 1) cum += w;
        if (cum >= need) { T = t; break; }
    }

    // Count meetings: +1 cow at a meets -1 cow at b > a iff b - a <= 2T.
    vector<ll> pos, neg;
    for (int i = 0; i < N; ++i) (D[i] == 1 ? pos : neg).push_back(X[i]);
    sort(pos.begin(), pos.end()); sort(neg.begin(), neg.end());
    ll ans = 0; int j = 0;
    // For each +1 cow at position a, count -1 cows at b in (a, a + 2T].
    int lo = 0;
    for (ll a : pos) {
        while (lo < (int)neg.size() && neg[lo] <= a) ++lo;
        while (j  < (int)neg.size() && neg[j]  <= a + 2 * T) ++j;
        if (j > lo) ans += j - lo;
        // j is non-decreasing across a's because we iterate a in sorted order.
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Milk Visits

Statement

A tree of N nodes; each node has a milk type 'H' or 'G'. M queries, each (a, b, c) asking whether the unique path from a to b contains at least one node of type c. Output a binary string of length M.

Constraints

Key idea

Because there are only 2 types, build a DSU over edges connecting same-type nodes. Each connected component is monochromatic. The path from a to b passes through a node of type c iff (a's type is c) or (b's type is c) or (a and b lie in different same-type components). Simplest: a's path contains type c iff not all nodes on the path are the opposite type, which is equivalent to a and b not being in the same opposite-type component (with the further check that the component's type isn't c).

Complexity target

O((N + M) α(N)) with DSU.

Reference solution (C++)

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) {
        a = find(a); b = find(b); if (a == b) return;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a; if (r[a] == r[b]) ++r[a];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    string t; cin >> t;            // length N, characters 'H'/'G'
    DSU d(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        if (t[u] == t[v]) d.unite(u, v);
    }
    string ans;
    while (M--) {
        int a, b; char c; cin >> a >> b >> c; --a; --b;
        // Path a..b contains type c iff some node on it is c.
        // If a or b is already c, yes.
        // Else both are the opposite type 'o'. Path contains a c iff a and b are
        // NOT in the same monochromatic 'o' component.
        bool ok;
        if (t[a] == c || t[b] == c) ok = true;
        else                         ok = d.find(a) != d.find(b);
        ans += ok ? '1' : '0';
    }
    cout << ans << "\n";
}

Pitfalls

What Silver December 2019 was actually testing