USACO 2019 US Open · Silver · all three problems

← Full 2019 US Open set · Official results

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

Subtask structure

Single full-credit test set; brute force passes when N is small but the intended O(N²) sweep handles N = 1000.

Statement

An N×N grid of cows each facing left ('L') or right ('R'). Farmer John may shout at any row or column to flip every cow in it. He can perform any sequence of row/column flips. Determine whether he can make all but at most one cow face the same direction. If yes, output the 1-indexed (row, col) of the lone cow that ends up facing differently (smallest row, then col). If all can be aligned, print "1 1". If impossible (more than one inevitably wrong), print "-1".

Constraints

2 ≤ N ≤ 1000.
Each cell is 'L' or 'R'.
Time limit: 2s.

Key idea

Flipping rows + columns is XOR by (r_i ⊕ c_j) on cell (i,j). After fixing r₀ = 0 (WLOG), the desired pattern (all same) forces row/col flip parities. Compare the implied pattern with the actual grid: count mismatches. If 0, alignment is perfect; if 1, the single mismatch is the lone cow; if ≥ 2, check whether all mismatches lie in a single row (and one extra column flip would fix all but one) or a single column — otherwise −1.

Complexity target

O(N²) read + O(N²) mismatch scan.

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<string> g(N);
    for (auto& r : g) cin >> r;

    // Convert to 0/1, where 1 means 'R'.
    vector<vector<int>> a(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) a[i][j] = (g[i][j] == 'R');

    // Normalize row 0 to all zeros by flipping the columns where a[0][j] == 1.
    vector<int> cflip(N);
    for (int j = 0; j < N; ++j) cflip[j] = a[0][j];
    // Now a[i][j] XOR cflip[j] is the "post column-flip" value; if row i is uniform
    // we can flip the row to make it all 0. Otherwise row i has mixed bits.
    int badRow = -1, badCol = -1, badCount = 0;
    for (int i = 0; i < N; ++i) {
        int b0 = a[i][0] ^ cflip[0];
        int diffCnt = 0, diffCol = -1;
        for (int j = 0; j < N; ++j) {
            int v = a[i][j] ^ cflip[j];
            if (v != b0) { ++diffCnt; diffCol = j; }
        }
        if (diffCnt == 0) continue;
        // diffCnt > 0 means row i can't be uniformly flipped.
        // If exactly one column differs, this row has exactly one "outlier" cow.
        if (diffCnt == 1) {
            if (badRow != -1) { cout << -1 << "\n"; return 0; }
            badRow = i; badCol = diffCol;
        } else {
            // More than one mismatch in a single row => impossible to leave just one.
            cout << -1 << "\n"; return 0;
        }
    }
    if (badRow == -1) cout << "1 1\n";
    else              cout << (badRow + 1) << " " << (badCol + 1) << "\n";
}

Pitfalls

Output convention. Different sources disagree on the all-aligned output; USACO statement says print "1 1" in that case.
Symmetric pivot. Fixing row 0 (or column 0) as the anchor is a WLOG — the resulting decision is unique regardless of choice.
"Lone cow" is unique. If two rows each have a mismatch, the answer is −1 — you cannot fix both with row/column flips.
Read as char grid then convert. Doing XOR directly on 'L'/'R' is error-prone.

Problem 2 — Cow Steeplechase II

Subtask structure

Single test set up to N ≤ 10⁵. A Bentley–Ottmann–style sweep is the intended solution.

Statement

Given N axis-aligned line segments (each either horizontal or vertical), exactly one segment can be removed so the remaining N−1 segments are pairwise disjoint (no shared interior or endpoint). Output the smallest 1-indexed segment id that can be removed.

Constraints

2 ≤ N ≤ 10⁵.
0 ≤ coordinates ≤ 10⁹.
All endpoints are distinct; each segment is horizontal or vertical.
Exactly one removable segment exists.
Time limit: 2s.

Key idea

Standard "find intersections among axis-aligned segments" sweep. Sweep events along x: a horizontal segment is "alive" between its left and right endpoints; verticals are point events at their x. Maintain a std::multiset of active horizontals keyed by y. At a vertical at x=v with y-range [y1,y2], every horizontal currently active whose y is in [y1,y2] intersects this vertical. Collect all intersecting pairs. If they all share a single segment, output that segment's id (smallest if there are ties because the problem says exactly one valid answer).

Complexity target

O((N + K) log N) where K = number of intersecting pairs reported. K is small in this problem because exactly one bad segment exists.

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;
    struct Seg { int x1, y1, x2, y2, id; bool horiz; };
    vector<Seg> s(N);
    for (int i = 0; i < N; ++i) {
        auto& e = s[i]; cin >> e.x1 >> e.y1 >> e.x2 >> e.y2;
        if (e.x1 > e.x2 || e.y1 > e.y2) { swap(e.x1, e.x2); swap(e.y1, e.y2); }
        e.id = i; e.horiz = (e.y1 == e.y2);
    }
    // Events: for each horizontal, add at x1 and remove at x2.
    // Verticals are point events at x1.
    struct Ev { int x, type, idx; };  // type: 0 add, 1 vertical, 2 remove
    vector<Ev> ev;
    for (int i = 0; i < N; ++i) {
        if (s[i].horiz) {
            ev.push_back({s[i].x1, 0, i});
            ev.push_back({s[i].x2, 2, i});
        } else {
            ev.push_back({s[i].x1, 1, i});
        }
    }
    sort(ev.begin(), ev.end(), [](const Ev& a, const Ev& b){
        if (a.x != b.x) return a.x < b.x;
        return a.type < b.type;  // add (0) before vertical (1) before remove (2)
    });
    multiset<pair<int,int>> alive;   // (y, segment id) of active horizontals
    map<int,int> hitCount;            // count of intersections involving each segment

    for (auto& e : ev) {
        if (e.type == 0) alive.insert({s[e.idx].y1, e.idx});
        else if (e.type == 2) alive.erase({s[e.idx].y1, e.idx});
        else {
            int y1 = s[e.idx].y1, y2 = s[e.idx].y2;
            auto lo = alive.lower_bound({y1, INT_MIN});
            auto hi = alive.upper_bound({y2, INT_MAX});
            for (auto it = lo; it != hi; ++it) {
                ++hitCount[it->second];
                ++hitCount[e.idx];
            }
        }
    }
    // The "bad" segment touches every intersection: it appears (total / 2) times.
    int total = 0;
    for (auto& [k, v] : hitCount) total += v;
    int pairs = total / 2;
    int ans = -1;
    for (auto& [k, v] : hitCount) if (v == pairs) { ans = k; break; }
    cout << ans + 1 << "\n";
}

Pitfalls

Endpoints count as intersection. The problem says segments must not touch "even at endpoints" — but since all endpoints are distinct, only crossings happen; still, careful with closed-interval comparisons in the multiset range query.
Event tie-breaking. Process adds before verticals before removes at the same x, so a vertical "sees" horizontals that touch at that x.
Pick the smallest valid id. Iterate ids in increasing order when scanning hitCount — use map or sort keys.
Coordinates up to 10⁹. int is fine for storage but be careful with any product (none needed here).

Problem 3 — Fence Planning

Subtask structure

Single full-credit test set. Direct DSU + per-component bounding box is the intended O((N+M)·α(N)) solution.

Statement

N cows live at given 2D coordinates and form a graph via M undirected "moo" edges. A connected component is a "moo network". Build an axis-aligned rectangle that contains every cow of at least one network (cows on the border count as enclosed). Minimize the rectangle's perimeter.

Constraints

2 ≤ N ≤ 10⁵.
1 ≤ M < 10⁵.
0 ≤ x_i, y_i ≤ 10⁸.
Every cow has at least one edge; no duplicate edges.
Time limit: 2s.

Key idea

Use DSU to find connected components. For each cow, union it with the per-component running bounding box (xmin, xmax, ymin, ymax). The perimeter of a component is 2·((xmax − xmin) + (ymax − ymin)). Return the minimum across components.

Complexity target

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

Reference solution (C++)

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

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(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<int> x(N), y(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    DSU d(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a; --b;
        d.unite(a, b);
    }
    // Per-root bounding box.
    const int INF = INT_MAX;
    vector<int> xmin(N, INF), xmax(N, INT_MIN), ymin(N, INF), ymax(N, INT_MIN);
    for (int i = 0; i < N; ++i) {
        int r = d.find(i);
        xmin[r] = min(xmin[r], x[i]); xmax[r] = max(xmax[r], x[i]);
        ymin[r] = min(ymin[r], y[i]); ymax[r] = max(ymax[r], y[i]);
    }
    ll ans = LLONG_MAX;
    for (int i = 0; i < N; ++i) if (d.find(i) == i) {
        ll per = 2LL * ((ll)(xmax[i] - xmin[i]) + (ll)(ymax[i] - ymin[i]));
        ans = min(ans, per);
    }
    cout << ans << "\n";
}

Pitfalls

Coordinates up to 10⁸. Perimeter fits in int but use long long defensively (doubled differences could be ~4·10⁸).
1-indexed input. Subtract 1 when reading edge endpoints.
Single-cow components are excluded by the constraint. Every cow has at least one edge, so every component has size ≥ 2.
Don't iterate "every component" via a map. Walk i = 0..N−1 and check find(i) == i — that's the canonical "iterate components" idiom for DSU.

What Silver 2019 US Open was actually testing

P1 — invariants under row/column flips. Reduce to XOR of row/column bits and check consistency.
P2 — sweepline on axis-aligned segments. Multiset of active horizontals + range query at each vertical.
P3 — DSU + per-component aggregation. Bog-standard combo every Silver climber must own.