U USACO Prep

USACO 2016 US Open · Silver · all three problems

← Full 2016 US Open set · Official results

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

Statement

Same setup as Bronze P3: N cows at integer positions, remove exactly 3 cows to minimize the area of the axis-aligned bounding box of the remaining N−3 cows. Silver bumps N up so a brute O(N3) is no longer free; you must reduce to a small candidate set.

Constraints

Key idea

Same observation as Bronze: only cows that hold one of the four extremes (min x, max x, min y, max y) are candidates for removal, and because you remove three, the next-rank extremes matter too. Keep the 3 smallest-x cows, 3 largest-x cows, 3 smallest-y cows, 3 largest-y cows — at most 12 distinct indices. Enumerate all C(≤12, 3) triples and for each recompute the bounding box of the remaining N−3 cows.

Complexity target

O(N) candidate extraction + O(220 · N) evaluation ≈ 107.

Reference solution (C++)

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

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

    auto top3 = [&](function<bool(int,int)> cmp) {
        vector<int> idx(N); iota(idx.begin(), idx.end(), 0);
        partial_sort(idx.begin(), idx.begin()+3, idx.end(), cmp);
        return vector<int>{idx[0], idx[1], idx[2]};
    };
    set<int> S;
    for (int i : top3([&](int a, int b){return X[a]<X[b];})) S.insert(i);
    for (int i : top3([&](int a, int b){return X[a]>X[b];})) S.insert(i);
    for (int i : top3([&](int a, int b){return Y[a]<Y[b];})) S.insert(i);
    for (int i : top3([&](int a, int b){return Y[a]>Y[b];})) S.insert(i);

    vector<int> C(S.begin(), S.end());
    int M = C.size();
    long long ans = LLONG_MAX;
    for (int a = 0; a < M; ++a)
      for (int b = a+1; b < M; ++b)
        for (int d = b+1; d < M; ++d) {
            int s0=C[a], s1=C[b], s2=C[d];
            int xl=INT_MAX, xh=INT_MIN, yl=INT_MAX, yh=INT_MIN;
            for (int i = 0; i < N; ++i) {
                if (i==s0||i==s1||i==s2) continue;
                xl=min(xl,X[i]); xh=max(xh,X[i]);
                yl=min(yl,Y[i]); yh=max(yh,Y[i]);
            }
            ans = min(ans, (long long)(xh-xl)*(yh-yl));
        }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Diamond Collector

Statement

Same N diamonds with sizes si. Bessie now has two display cases. She fills each case with a subset of diamonds whose max−min ≤ K, and the two cases must share no diamond. Maximize the total number of diamonds displayed across both cases.

Constraints

Key idea

Sort sizes. After sorting, each case is a contiguous range, and the two ranges are disjoint — so one lies entirely to the left of the other. For each index i, compute:

Answer = max over i of bestL[i-1] + R[i]. Linear after sorting.

Complexity target

O(N log N) sort + O(N) sweep.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N; long long K;
    cin >> N >> K;
    vector<long long> s(N);
    for (auto& x : s) cin >> x;
    sort(s.begin(), s.end());

    // R[i] = length of longest valid range starting at i.
    vector<int> R(N+1, 0);
    int j = 0;
    for (int i = 0; i < N; ++i) {
        if (j < i) j = i;
        while (j < N && s[j] - s[i] <= K) ++j;
        R[i] = j - i;
    }

    // bestL[i] = max over l ≤ i of length(longest valid range ending at l).
    vector<int> bestL(N+1, 0);
    int lp = 0;
    for (int r = 0; r < N; ++r) {
        while (s[r] - s[lp] > K) ++lp;
        int len = r - lp + 1;
        bestL[r+1] = max(bestL[r], len);
    }

    int ans = 0;
    for (int i = 0; i < N; ++i)
        ans = max(ans, bestL[i] + R[i]);   // left case uses [0..i-1], right uses [i..]
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Closing the Farm

Statement

The farm has N barns connected by M bidirectional paths. FJ will close barns one at a time in a given order; when a barn is closed, it and all incident paths are removed. After each closure, report whether the remaining open barns still form a connected graph (output "YES" or "NO"). The initial graph (zero closures) is considered first.

Constraints

Key idea

Process closures in reverse — the time-reversed sequence is a series of barn openings, where each opening adds a node and the edges connecting it to already-open barns. This is the classic offline "deletions become unions" trick, and a Union-Find handles it in near-linear time. After the reverse sequence, flip the YES/NO answers back to original order.

Complexity target

O((N + M) · α(N)) total.

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 f(int x){ return p[x]==x?x:p[x]=f(p[x]); }
    bool u(int a, int b){
        a=f(a); b=f(b); if(a==b) return false;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a; if(r[a]==r[b]) ++r[a]; return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    vector<int> order(N);
    for (auto& x : order) { cin >> x; --x; }

    DSU dsu(N);
    vector<bool> open(N, false);
    vector<string> out(N);
    int comps = 0;
    for (int i = N - 1; i >= 0; --i) {
        int v = order[i];
        open[v] = true; ++comps;
        for (int u : adj[v]) if (open[u]) if (dsu.u(u, v)) --comps;
        out[i] = (comps == 1 ? "YES" : "NO");
    }
    for (auto& s : out) cout << s << "\n";
}

Pitfalls

What Silver 2016 US Open was actually testing