U USACO Prep

USACO 2021 December · Silver · all three problems

← Full December 2021 set · Official results

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

Statement

A number line has N cows at positions pi, each with a tastiness ti. Farmer Nhoj already planted M patches at positions fj. Bessie now plants K patches at integer positions of her choice. A cow goes to the patch closest to it; ties go to Nhoj. Maximize the total tastiness of cows that go to a Bessie patch.

Constraints

Key idea

Sort Nhoj's patches; they cut the line into M+1 "gaps". Within one gap [L, R] between two Nhoj patches, placing one Bessie patch in the middle captures all cows in [L+1, midpoint−1] ∪ [midpoint+1, R−1] — i.e. all cows strictly inside the half-gap on each side. With more Bessie patches in the same gap, additional patches each capture another sub-segment. The marginal gain of the first patch in a gap is large; later ones are smaller. Precompute prefix tastiness sums; for every gap compute the score of placing 1 Bessie patch and the score of placing 2 patches (which is the whole gap minus boundary cows). Put all "first patch" gains and "second patch extra gain" values in a max-heap and pick the top K.

Complexity target

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

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 K, M, N;
    cin >> K >> M >> N;     // [verify input order] cpid=1158
    vector<pair<ll, ll>> cows(N);
    for (auto& [x, t] : cows) cin >> x >> t;
    vector<ll> f(M);
    for (auto& x : f) cin >> x;
    sort(f.begin(), f.end());
    sort(cows.begin(), cows.end());

    // For a half-open range of cow indices [lo, hi), tastiness sum via prefix.
    vector<ll> pref(N + 1, 0);
    for (int i = 0; i < N; ++i) pref[i + 1] = pref[i] + cows[i].second;
    auto sumIn = [&](ll a, ll b) -> ll {
        // tastiness of cows with position in [a, b]
        int lo = lower_bound(cows.begin(), cows.end(), make_pair(a, 0LL)) - cows.begin();
        int hi = upper_bound(cows.begin(), cows.end(), make_pair(b, LLONG_MAX)) - cows.begin();
        return pref[hi] - pref[lo];
    };

    priority_queue<ll> pq;
    // Process M+1 gaps. Outside boundaries: cows left of f[0] and right of f[M-1].
    for (int i = 0; i <= M; ++i) {
        ll L = (i == 0) ? LLONG_MIN/2 : f[i - 1];
        ll R = (i == M) ? LLONG_MAX/2 : f[i];
        if (i == 0)            { pq.push(sumIn(L, R - 1)); continue; }
        if (i == M)            { pq.push(sumIn(L + 1, R)); continue; }
        ll mid = (L + R) / 2;
        ll first  = sumIn(L + 1, mid - 1);     // capture half the gap
        ll whole  = sumIn(L + 1, R - 1);
        pq.push(first);
        pq.push(whole - first);                // second patch fills the rest
    }
    ll ans = 0;
    for (int i = 0; i < K && !pq.empty(); ++i) { ans += pq.top(); pq.pop(); }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Connecting Two Barns

Statement

A farm has N fields and M bidirectional paths. Bessie wants to go from field 1 to field N. You may add up to 2 new paths; the cost of a path between fields a and b is (a − b)². Find the minimum total cost of added paths so that field 1 and field N become connected.

Constraints

Key idea

Run DSU. Let A = component of node 1, B = component of node N. If A = B, answer 0. Otherwise we add one or two edges. With one edge: pick u ∈ A, v ∈ B minimizing (u − v)². With two edges: pick a third "bridge" component C, an edge from A to C and an edge from C to B, paying min over u ∈ A, c ∈ C of (u − c)² plus min over c' ∈ C, w ∈ B of (c' − w)². For each component C, the per-component cost to A is min over c ∈ C of squared distance to nearest node in A (use sorted A + binary search); likewise for B. Then iterate components.

Complexity target

O((N + M) α(N) + N log N) per test case.

Reference solution (C++)

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

struct DSU {
    vector<int> p;
    DSU(int n) : p(n, -1) {}
    int f(int x) { return p[x] < 0 ? x : p[x] = f(p[x]); }
    void u(int a, int b) { a = f(a); b = f(b); if (a != b) p[a] = b; }
};

void solve() {
    int N, M; cin >> N >> M;
    DSU d(N + 1);
    for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; d.u(a, b); }

    // Bucket nodes by their component root.
    map<int, vector<int>> comp;
    for (int i = 1; i <= N; ++i) comp[d.f(i)].push_back(i);
    int rA = d.f(1), rB = d.f(N);
    if (rA == rB) { cout << 0 << "\n"; return; }

    auto& A = comp[rA]; auto& B = comp[rB];
    // Min cost to attach a single node x to component S (sorted).
    auto bestTo = [](const vector<int>& S, int x) -> ll {
        auto it = lower_bound(S.begin(), S.end(), x);
        ll best = LLONG_MAX;
        if (it != S.end())     best = min(best, (ll)(*it - x) * (*it - x));
        if (it != S.begin())   { auto p = prev(it); best = min(best, (ll)(x - *p) * (x - *p)); }
        return best;
    };

    ll ans = LLONG_MAX;
    for (auto& [r, C] : comp) {
        ll cA = LLONG_MAX, cB = LLONG_MAX;
        for (int x : C) { cA = min(cA, bestTo(A, x)); cB = min(cB, bestTo(B, x)); }
        if (cA < LLONG_MAX && cB < LLONG_MAX) ans = min(ans, cA + cB);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}

Pitfalls

Problem 3 — Convoluted Intervals

Statement

N intervals [ai, bi] with integer endpoints in [0, M]. For every s ∈ [0, 2M], count the number of ordered pairs (i, j) (with i = j allowed) such that ai + aj ≤ s ≤ bi + bj. Output the N+1... actually 2M+1 counts.

Constraints

Key idea

Let cntA[x] = #{i : ai = x} and cntB[x] = #{i : bi = x}. The number of pairs with ai + aj = s is (cntA ⋆ cntA)[s] (convolution), computable in O(M²). Same for b. Let f(s) = #pairs with a-sum ≤ s = prefix sum of cntA ⋆ cntA; g(s) = #pairs with b-sum < s = prefix sum of cntB ⋆ cntB up to s−1. Then answer[s] = f(s) − g(s) = #pairs with a-sum ≤ s minus #pairs with b-sum < s, which by inclusion–exclusion equals #pairs with a-sum ≤ s ≤ b-sum.

Complexity target

O(M²) for the convolution (M ≤ 5000 ⇒ 2.5 · 107) plus O(M) prefix sums.

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, M; cin >> N >> M;
    vector<ll> cA(M + 1, 0), cB(M + 1, 0);
    for (int i = 0; i < N; ++i) { int a, b; cin >> a >> b; ++cA[a]; ++cB[b]; }

    // Convolutions: cA*cA and cB*cB. Both length 2M+1.
    int S = 2 * M;
    vector<ll> convA(S + 1, 0), convB(S + 1, 0);
    for (int x = 0; x <= M; ++x) if (cA[x])
        for (int y = 0; y <= M; ++y) if (cA[y]) convA[x + y] += cA[x] * cA[y];
    for (int x = 0; x <= M; ++x) if (cB[x])
        for (int y = 0; y <= M; ++y) if (cB[y]) convB[x + y] += cB[x] * cB[y];

    // f[s] = #pairs with a-sum <= s, g[s] = #pairs with b-sum <= s.
    // answer[s] = #pairs(a-sum <= s) - #pairs(b-sum <= s - 1)
    vector<ll> f(S + 1, 0), g(S + 1, 0);
    f[0] = convA[0]; g[0] = convB[0];
    for (int s = 1; s <= S; ++s) {
        f[s] = f[s - 1] + convA[s];
        g[s] = g[s - 1] + convB[s];
    }
    for (int s = 0; s <= S; ++s) {
        ll bLess = (s == 0 ? 0 : g[s - 1]);
        cout << (f[s] - bLess) << "\n";
    }
}

Pitfalls

What Silver December 2021 was actually testing