U USACO Prep

USACO 2020 US Open · Silver · all three problems

← Full 2020 US Open set · Official results

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

Statement

N cows must each occupy a distinct integer position on a number line. The allowed positions are the union of M mutually-disjoint intervals [aj, bj] (no two intervals overlap or touch). Maximize the minimum pairwise distance between any two cows.

Constraints

Key idea

Binary search on the answer D. For a given D, greedily place cows from left to right across sorted intervals: in each interval, the first feasible position is max(intervalStart, lastPlaced + D); from there step by D until you exit the interval. Total cows fittable is monotone-decreasing in D.

Complexity target

O((N + M) log(max coordinate)) — binary search over [1, 1018] with a linear feasibility check.

Reference solution (C++)

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

int N, M;
vector<pair<ll,ll>> iv;

bool ok(ll D) {
    ll placed = 0, last = LLONG_MIN / 4;
    for (auto& [a, b] : iv) {
        ll pos = max(a, last + D);
        if (pos > b) continue;
        // count placements in [pos, b] stepping by D
        ll cnt = (b - pos) / D + 1;
        placed += cnt;
        last = pos + (cnt - 1) * D;
        if (placed >= N) return true;
    }
    return placed >= N;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    iv.resize(M);
    for (auto& [a, b] : iv) cin >> a >> b;
    sort(iv.begin(), iv.end());

    ll lo = 1, hi = iv.back().second - iv.front().first;
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1) / 2;
        if (ok(mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
}

Pitfalls

Problem 2 — Cereal

Statement

Each of N cows has a 1st-choice cereal fi and 2nd-choice cereal si, out of M cereal boxes. Cows arrive in order; each takes its 1st choice if available, else its 2nd choice, else leaves empty. For each starting index k = 0..N−1, output the number of cows that get a cereal if only cows k, k+1, …, N−1 line up (in that order).

Constraints

Key idea

Process cows from last to first. Maintain owner[b] = the cow currently holding cereal b. When cow i tries to grab fi: if free, take it. Else "displace" the current owner, who then recursively tries its second choice s — that displacement chain is bounded amortized because each cow is "kicked" at most once per box, and each cow has only two choices total. So overall O(N+M) across all 1..N suffixes. After processing cow k, the number of cows holding a box is the answer for suffix k.

Complexity target

O((N + M) · α) total work; each cow occupies at most 2 boxes during its lifetime in the chain.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<int> f(N), s(N);
    for (int i = 0; i < N; ++i) cin >> f[i] >> s[i];

    vector<int> owner(M + 1, -1);     // owner[b] = cow index, or -1
    vector<int> ans(N);
    int served = 0;

    // Insert cow i: try its first choice; if taken, displace and the displaced
    // cow tries its second choice (and it has none beyond that, so it leaves).
    auto place = [&](int i) {
        int box = f[i];
        if (owner[box] == -1) { owner[box] = i; ++served; return; }
        int displaced = owner[box];
        owner[box] = i;                // newcomer gets first choice
        // displaced now tries its second choice
        int b2 = s[displaced];
        if (owner[b2] == -1) { owner[b2] = displaced; }
        else { --served; }             // displaced leaves
    };
    // Wait — that's only right if we insert in arrival order. We want suffix
    // answers, so insert cows from i = N-1 down to 0 and at each step record
    // ans[i] = served. But "arrival order" within the suffix is i, i+1, ...
    // so equivalently process forward but recompute. Simpler: insert in
    // reverse and use the same priority rule (newcomer wins first choice).
    for (int i = N - 1; i >= 0; --i) {
        place(i);
        ans[i] = served;
    }
    for (int v : ans) cout << v << "\n";
}

Pitfalls

Problem 3 — The Moo Particle

Statement

N "moo particles" each have spin (xi, yi). Two particles i, j can annihilate each other when xi ≤ xj and yi ≤ yj (or with i, j swapped). Find the minimum number of particles remaining after performing any sequence of pairwise annihilations.

Constraints

Key idea

Sort particles by x (break ties by y). Walk through and count "y-descents" — positions where the running max-y resets, i.e., the current y is strictly less than the maximum y seen so far. The answer is 1 + number of such descents. Intuition: particles that share a chain under the partial order (≤ in both coords) all collapse to one survivor; chains correspond to maximal increasing runs in y after sorting by x.

Complexity target

O(N log N) for the sort.

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; cin >> N;
    vector<pair<ll,ll>> p(N);
    for (auto& [x, y] : p) cin >> x >> y;
    sort(p.begin(), p.end());          // by x asc, then y asc

    int components = 1;
    ll runMaxY = p[0].second;
    for (int i = 1; i < N; ++i) {
        if (p[i].second < runMaxY) {
            // strict descent: current particle is incomparable with the
            // maximum-y so far in this x-block — new chain
            ++components;
        }
        runMaxY = max(runMaxY, p[i].second);
    }
    cout << components << "\n";
}

Pitfalls

What Silver 2020 US Open was actually testing