U USACO Prep

USACO 2018 US Open · Silver · all three problems

← Full US Open 2018 set · Official results

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

Statement

Bessie implements bubble sort. Each outer iteration of her loop prints "moo", then performs a single left-to-right pass that swaps adjacent out-of-order pairs; the loop exits when a pass makes no swaps. Given the initial array A, output how many times "moo" is printed.

Constraints

Key idea

The classic identity: a single left-to-right bubble pass moves the largest unsorted element fully to its correct position, and moves every other element at most one slot left. So the number of passes needed equals 1 + max over i of (i − possorted(A[i])) — i.e. one plus the largest leftward displacement any element has to travel. The final "check" pass with no swaps adds one more "moo". With ties, break the sorted ordering by original index so equal elements keep their relative order.

Complexity target

O(N log N): sort pairs (value, index), take max(i − sortedRank[i]).

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<pair<long long,int>> a(N);
    for (int i = 0; i < N; ++i) { cin >> a[i].first; a[i].second = i; }

    // Stable sort by value; ties broken by original index.
    sort(a.begin(), a.end());

    // For each original element now at sorted rank j, its old index was a[j].second.
    // Bubble passes >= max over j of (a[j].second - j), then +1 for the silent final pass.
    int maxShift = 0;
    for (int j = 0; j < N; ++j) maxShift = max(maxShift, a[j].second - j);
    cout << maxShift + 1 << "\n";
}

Pitfalls

Problem 2 — Lemonade Line

Statement

N cows want lemonade. Cow i has a "patience" wi: it will only join the line if at the moment of its arrival the line already contains at most wi cows; otherwise it leaves forever. FJ chooses the order in which cows arrive. What is the minimum number of cows that will end up in the line?

Constraints

Key idea

Sort patience values in descending order. Greedily admit the patient cows first: the k-th admitted cow sees k − 1 cows already in line. So admit cow k iff wk ≥ k − 1. Stop the first time the condition fails; the answer is the count admitted up to that point.

Why "minimum"? FJ chooses the arrival order adversarially against admission count. Sending the most patient cows first packs the most "stayers" early; the moment the line has more cows than the next cow's patience, that cow and every less-patient cow leaves.

Complexity target

O(N log N) sort + O(N) 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<long long> w(N);
    for (auto& x : w) cin >> x;
    sort(w.begin(), w.end(), greater<long long>());

    int joined = 0;
    for (int i = 0; i < N; ++i) {
        if (w[i] >= (long long)joined) ++joined;
        else break;
    }
    cout << joined << "\n";
}

Pitfalls

Problem 3 — Multiplayer Moo

Statement

An N×N grid is filled with cow IDs (each cell holds an integer 0..106). A "region" is a 4-connected (up/down/left/right) maximal set of cells all sharing some ID. Output:

  1. Single-cow: the size of the largest region of identical IDs.
  2. Two-cow team: the size of the largest 4-connected component using cells of exactly two distinct IDs (you choose which pair to maximize).

Constraints

Key idea

Step 1 — flood fill to label each maximal single-ID region with a component id. Track size of each component and the ID it represents. The largest single-cow region is just max(size).

Step 2 — build the "component graph": two components are adjacent if any pair of their cells is orthogonally adjacent in the grid. For each pair of distinct IDs (A, B) that share at least one component-graph edge, BFS over the union of components labelled A or B that are connected through other A/B components. Answer is the max BFS size.

Practical implementation: for each component C with ID A, look at its neighbours in the component graph; for each neighbour ID B ≠ A, start a BFS over the union "components with ID ∈ {A, B}" reachable from C using only A/B edges, summing their cell counts. Cache (C, B) so each pair is processed once.

Complexity target

Up to N² = 62,500 cells. The component graph has at most O(N²) nodes and O(N²) edges. Pair-BFS in the worst case touches every edge for every pair, but the number of distinct (A, B) seed pairs is bounded by the edge count of the component graph, giving overall O(N² · avgDeg) — fast enough.

Reference solution (C++)

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

int N;
vector<vector<int>> g;          // grid IDs
vector<vector<int>> comp;       // comp id per cell, -1 unset
vector<int> compSize, compID;   // per component
vector<set<int>> adj;           // adj[c] = component-ids touching c
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};

void floodComp(int sr, int sc, int cid) {
    queue<pair<int,int>> q; q.push({sr, sc}); comp[sr][sc] = cid;
    int v = g[sr][sc], sz = 0;
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop(); ++sz;
        for (int d = 0; d < 4; ++d) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
            if (g[nr][nc] == v && comp[nr][nc] == -1) { comp[nr][nc] = cid; q.push({nr, nc}); }
        }
    }
    compSize.push_back(sz); compID.push_back(v);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    g.assign(N, vector<int>(N));
    comp.assign(N, vector<int>(N, -1));
    for (auto& row : g) for (auto& x : row) cin >> x;
    for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c)
        if (comp[r][c] == -1) floodComp(r, c, compSize.size());

    int C = compSize.size();
    adj.assign(C, {});
    for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c)
        for (int d = 0; d < 4; ++d) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
            if (comp[nr][nc] != comp[r][c]) adj[comp[r][c]].insert(comp[nr][nc]);
        }

    int best1 = *max_element(compSize.begin(), compSize.end());
    int best2 = best1; // a single component is a valid degenerate "two-cow" region only if it shares
                       // an edge with another ID; we'll improve it below.
    // BFS in component graph restricted to ID pair {A, B}.
    auto pairBfs = [&](int start, int A, int B) {
        vector<char> vis(C, 0); queue<int> q; q.push(start); vis[start] = 1;
        int tot = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop(); tot += compSize[u];
            for (int v : adj[u]) if (!vis[v] && (compID[v] == A || compID[v] == B)) { vis[v] = 1; q.push(v); }
        }
        return tot;
    };
    for (int u = 0; u < C; ++u) for (int v : adj[u]) if (v > u) {
        int A = compID[u], B = compID[v];
        if (A == B) continue;
        best2 = max(best2, pairBfs(u, A, B));
    }
    cout << best1 << "\n" << best2 << "\n";
}

Pitfalls

What Silver US Open 2018 was actually testing