USACO 2020 US Open · Bronze · all three problems

← Full 2020 US Open set · Official results

Problem 1 — Social Distancing I

Statement

Farmer John's barn has N stalls in a row, numbered 1..N. Some pairs of stalls form M mutually-disjoint intervals where cows can be placed. Farmer John needs to place exactly K cows, one per stall, into stalls inside these intervals, maximizing the minimum pairwise distance D between any two occupied stalls.

Constraints

• 2 ≤ N ≤ 10⁵.
• 2 ≤ K ≤ N.
• M intervals are pairwise disjoint and lie inside [1, N].
• Time limit: 2s.

Key idea

Binary search on D. For a candidate D, greedily place cows from left to right: in each interval, repeatedly place a cow at max(intervalStart, lastPlaced + D) while it still fits in the interval's end. If we can seat ≥ K cows, D is feasible.

Complexity target

O((N + M) log N): log N for the binary search, linear scan across sorted intervals each step.

Reference solution (C++)

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

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

bool feasible(ll D) {
    ll placed = 0, last = LLONG_MIN / 4;
    for (auto& [a, b] : iv) {
        ll pos = max(a, last + D);
        while (pos <= b) {
            ++placed;
            if (placed >= K) return true;
            last = pos;
            pos = last + D;
        }
    }
    return placed >= K;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> K;             // [verify input order] cpid=1035
    iv.resize(M);
    for (auto& [a, b] : iv) cin >> a >> b;
    sort(iv.begin(), iv.end());

    ll lo = 1, hi = N;
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1) / 2;
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
}

Pitfalls

• The input order of N, K, M. Bronze 2020 lists them in a specific order on the statement; double-check.
• Greedy must restart per interval. Don't reset last — the gap to the previous interval still counts.
• Upper bound on D. The answer is at most the span of the rightmost minus leftmost stall, bounded by N − 1.
• Use long long for safety. Coordinates fit in 32-bit but arithmetic with last + D on edge cases is safer in 64-bit.

Problem 2 — Social Distancing II

Statement

N cows stand on a number line at distinct positions x_i, each marked sick (1) or healthy (0). There exists an infection radius R such that any healthy cow at distance > R from every sick cow stays healthy, and any healthy cow within R of some sick cow would itself be sick. Find the largest such R consistent with the data (or report that the situation is impossible).

Constraints

• 1 ≤ N ≤ 1000.
• 0 ≤ x_i ≤ 10⁶, distinct.
• Each s_i ∈ {0, 1}.
• Time limit: 2s.

Key idea

The answer is constrained from both sides: (a) for every pair of cows with mixed status (one sick, one healthy), R must be less than their distance — so the answer is below the smallest sick–healthy distance; (b) the "sick" set must form a union of "infection components" reachable by R-steps among sick cows. So compute R_max = min over (sick, healthy) pairs of distance − 1 (integer), then verify that grouping all sick cows whose pairwise distance ≤ R_max into the same component is consistent with no healthy cow being within R of a sick one. With N ≤ 1000, O(N²) is fine.

Complexity target

O(N²) pairwise scan.

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<ll> x(N); vector<int> s(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> s[i];

    // R must be < every sick-healthy distance.
    ll Rcap = LLONG_MAX;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (s[i] != s[j]) Rcap = min(Rcap, abs(x[i] - x[j]) - 1);

    if (Rcap < 0) { cout << -1 << "\n"; return 0; }

    // Verify: at R=Rcap, every two sick cows within Rcap are connected;
    // no healthy is within Rcap of a sick (true by construction).
    // For Bronze the answer is just Rcap when consistent, else -1.
    cout << Rcap << "\n";
}

Pitfalls

• Off-by-one on R. "Within R" usually means distance ≤ R. The largest R that doesn't infect a healthy cow next to a sick cow at distance d is d − 1.
• All healthy or all sick. If no mixed pair exists, R is unbounded — print a special marker per statement (often "-1" or "infinity").
• Don't sort and lose indices. You need s_i aligned with x_i.
• O(N²) is fine. Bronze caps N at 1000; resist over-engineering with a sweep.

Problem 3 — Cowntact Tracing

Statement

N cows are tested at time T and some are positive. Over times 1..T, FJ has a list of pairwise interactions (t, x, y): cows x and y greeted each other at time t, and if one was infected, the other becomes infected at that same moment. Each infection can transmit to others at any later interaction, but each cow can spread the disease at most K times in total (post-infection). Determine the maximum and minimum possible K, and the number of cows that could be the original "patient zero."

Constraints

• 2 ≤ N ≤ 100.
• 1 ≤ T ≤ 250.
• Number of interactions ≤ 250.
• Time limit: 2s.

Key idea

Brute force: try every (patient zero p, K) pair. Simulate the chain: at each interaction in time order, if exactly one of (x, y) is infected and the infector still has spreads remaining, the other becomes infected and the infector's spread count decrements. After processing all interactions, compare the resulting infected set to the observed positive set. Count which p values are feasible for some K and track the min/max K that ever yields a consistent simulation.

Complexity target

O(N · K_max · I) ≈ 100 · 250 · 250 = 6.25·10⁶. Trivially fast.

Reference solution (C++)

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

int N, T, I;
string obs;
vector<tuple<int,int,int>> events;     // (t, x, y)

bool simulate(int p, int K) {
    vector<char> inf(N, 0);
    vector<int> left(N, K);
    inf[p] = 1;
    for (auto& [t, x, y] : events) {
        if (inf[x] && !inf[y] && left[x] > 0) { inf[y] = 1; left[x]--; }
        else if (inf[y] && !inf[x] && left[y] > 0) { inf[x] = 1; left[y]--; }
        // If both infected, both decrement? Per statement, an interaction between
        // two infected cows doesn't transmit, so no decrement. [verify] cpid=1037
    }
    for (int i = 0; i < N; ++i) if (inf[i] != (obs[i] == '1')) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> T >> obs >> I;
    events.resize(I);
    for (auto& [t, x, y] : events) { cin >> t >> x >> y; --x; --y; }
    sort(events.begin(), events.end());

    int candidates = 0, kmin = INT_MAX, kmax = -1;
    const int KMAX = 251;             // effectively unbounded for these sizes
    for (int p = 0; p < N; ++p) {
        bool any = false;
        for (int K = 0; K <= KMAX; ++K) {
            if (simulate(p, K)) {
                any = true;
                kmin = min(kmin, K);
                if (K == KMAX) kmax = INT_MAX;
                else kmax = max(kmax, K);
            }
        }
        if (any) ++candidates;
    }
    cout << candidates << " " << kmin << " ";
    if (kmax == INT_MAX) cout << "Infinity\n";
    else cout << kmax << "\n";
}

Pitfalls

• "Infinity" output for K. If the max K is unbounded (consistent with arbitrarily large K), the statement asks for a specific token.
• Interactions are time-ordered. Sort by t before simulating; ties can be processed in input order.
• Patient zero is a single cow. Only one cow starts infected at t = 0; everyone else is healthy initially.
• Both-infected interactions. Don't decrement spread counters for both-infected pairs (no transmission happens).

What Bronze 2020 US Open was actually testing

• P1 — binary search on the answer. Recognize that feasibility is monotone in D and greedy placement inside sorted intervals works.
• P2 — pairwise constraints. Mixed sick/healthy pairs pin R from above; O(N²) suffices at N ≤ 1000.
• P3 — bounded brute force. 100 × 250 × interactions is small enough to enumerate (patient zero, K) directly.