USACO 2016 US Open · Gold · 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 — Splitting the Field

Statement

FJ has N cows at integer positions (x_i, y_i). The single bounding-box area covers all of them. FJ wants to split the cows into two non-empty groups and build two axis-aligned bounding fences, one per group. Find the maximum amount of area saved versus the single combined fence (i.e. single area minus the minimum sum of two areas), over all ways to partition cows into two non-empty groups using a single axis-aligned cut (cows in one group lie strictly on one side of a vertical or horizontal line).

Constraints

2 ≤ N ≤ 50 000.
1 ≤ x_i, y_i ≤ 10⁹.
Time limit: 2s.

Key idea

It is enough to consider splits where one group is "all cows with x ≤ some threshold" or "all cows with y ≤ some threshold." Sort by x; with a left-to-right sweep maintain (min y, max y, min x, max x) of the prefix and the symmetric quantities of the suffix (precomputed in a right-to-left pass). For every split index i, compute the prefix bounding box and suffix bounding box areas; track the minimum sum. Repeat with y as the splitting axis. Answer = total area − min(prefix+suffix).

Complexity target

O(N log N) for sorts; O(N) for the sweeps. About 10⁶ operations.

Reference solution (C++)

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

int N;
vector<pair<int,int>> P; // (x,y)

ll bestSplit(int axis) {
    // axis=0: sort by x; axis=1: sort by y.
    vector<pair<int,int>> A = P;
    sort(A.begin(), A.end(), [&](auto& p, auto& q){
        return axis==0 ? p.first<q.first : p.second<q.second;
    });
    vector<ll> preA(N), sufA(N);
    int xl=INT_MAX, xh=INT_MIN, yl=INT_MAX, yh=INT_MIN;
    for (int i = 0; i < N; ++i) {
        xl=min(xl,A[i].first); xh=max(xh,A[i].first);
        yl=min(yl,A[i].second); yh=max(yh,A[i].second);
        preA[i] = (ll)(xh-xl)*(yh-yl);
    }
    xl=INT_MAX; xh=INT_MIN; yl=INT_MAX; yh=INT_MIN;
    for (int i = N - 1; i >= 0; --i) {
        xl=min(xl,A[i].first); xh=max(xh,A[i].first);
        yl=min(yl,A[i].second); yh=max(yh,A[i].second);
        sufA[i] = (ll)(xh-xl)*(yh-yl);
    }
    ll best = LLONG_MAX;
    for (int i = 0; i < N - 1; ++i)
        best = min(best, preA[i] + sufA[i+1]);
    return best;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    P.resize(N);
    int xl=INT_MAX, xh=INT_MIN, yl=INT_MAX, yh=INT_MIN;
    for (auto& p : P) {
        cin >> p.first >> p.second;
        xl=min(xl,p.first); xh=max(xh,p.first);
        yl=min(yl,p.second); yh=max(yh,p.second);
    }
    ll total = (ll)(xh-xl)*(yh-yl);
    ll best = min(bestSplit(0), bestSplit(1));
    cout << total - best << "\n";
}

Pitfalls

Use 64-bit areas. Coordinates up to 10⁹; area products up to 4·10¹⁸. long long everywhere.
Ties at the cut. Sort stably; the split is by sorted position, not by coordinate value. Two cows with the same x can fall into either prefix or suffix — both are valid splits and the sweep considers them.
Don't forget the y-axis split. The optimal cut might be horizontal; run the sweep with both orderings.
Output: savings, not area. The problem asks for area saved versus the combined fence, not the sum of two areas.

Problem 2 — Closing the Farm

Statement

Same problem as the Silver version: barns close one by one in a given order; after each closure print whether the remaining open barns form a connected subgraph. Gold scales N and M up so a naive O(N·(N+M)) BFS-after-each-closure cannot pass.

Constraints

1 ≤ N ≤ 200 000.
1 ≤ M ≤ 200 000.
Time limit: 2s.

Key idea

Identical algorithm to Silver: reverse the closing sequence into an opening sequence, process with DSU, and maintain the number of open components. The only differences are the larger N/M and the need for fast I/O and a path-compressed DSU.

Complexity target

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

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){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return 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

Fast I/O is mandatory. Without sync_with_stdio(false) + cin.tie(nullptr), 200k edges read by cin alone will eat much of the 2-second budget.
Iterative path compression. Recursive find on a 200k chain can blow the default stack on some judges. The iterative two-step path-halving above is safer.
Don't forget to flip the output. Closure i's answer is stored at out[i], printed in forward order at the end.

Problem 3 — 248

Statement

Given a sequence of N positive integers a₁, …, a_N, you may repeatedly pick two adjacent equal values v and v and merge them into a single tile of value v+1 (think 2048 on a 1D row). Each merge shrinks the sequence by one. Find the maximum tile value that can appear in the sequence at any point during such merges.

Constraints

1 ≤ N ≤ 248.
1 ≤ a_i ≤ 40.
Time limit: 2s.

Key idea

Classic interval DP. Let f[l][r] = the value that the subarray a[l..r] collapses to if and only if it can collapse to a single tile (0 otherwise). Recurrence: f[l][r] = f[l][m]+1 for any split m where f[l][m] = f[m+1][r] and both are nonzero. Track the global maximum value seen across all (l, r). Subarray that can't collapse to a single tile simply contributes 0.

Complexity target

O(N³) = ~1.5·10⁷. Comfortable.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (auto& x : a) cin >> x;

    vector<vector<int>> f(N, vector<int>(N, 0));
    int ans = 0;
    for (int i = 0; i < N; ++i) { f[i][i] = a[i]; ans = max(ans, a[i]); }

    for (int len = 2; len <= N; ++len) {
        for (int l = 0; l + len - 1 < N; ++l) {
            int r = l + len - 1;
            for (int m = l; m < r; ++m) {
                if (f[l][m] && f[l][m] == f[m+1][r]) {
                    int v = f[l][m] + 1;
                    if (v > f[l][r]) f[l][r] = v;
                }
            }
            ans = max(ans, f[l][r]);
        }
    }
    cout << ans << "\n";
}

Pitfalls

Intervals that don't collapse are 0, not −infinity. 0 is a sentinel: original tile values are ≥ 1, so 0 always means "cannot collapse to one tile."
Track the global max, not just f[0][N-1]. The biggest tile might appear mid-game in a strict sub-interval; the full array might not even be mergeable.
O(N³) is the intended bound. Don't reach for monotonic-stack tricks at N = 248 — the DP is the clean solution.

What Gold 2016 US Open was actually testing

P1 — prefix/suffix bounding-box sweep. Classic "split an array into two halves" pattern, with 2D geometry on top.
P2 — offline reverse-time DSU at scale. The same algorithm as Silver, but proves you can implement DSU+I/O cleanly at 200k.
P3 — interval DP with mergeability. A staple Gold pattern; recognize that "collapses to one tile" is the right per-interval state.