U USACO Prep

USACO 2018 US Open · Gold · 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

Gold version: Bessie runs cocktail sort (bidirectional bubble sort). Each outer iteration prints "moo", then runs a left-to-right pass followed by a right-to-left pass. The loop exits when no swaps happen during a full cycle. Output the number of "moo"s.

Constraints

Key idea

Same trick as Silver, but now each cycle reduces an element's displacement in both directions. Sort indices by (value, original index). After k cycles, an element initially at original index i with sorted rank j is at position in [max(j, i − k), min(N − 1 − (N − 1 − j), i + k)] (roughly). The number of cycles needed equals ceil(maxShift / 2) where maxShift is the largest absolute distance |i − j| any element must travel. Then +1 for the final passive cycle.

Cleaner phrasing: after each cycle, every element moves at most 1 left and at most 1 right. So each cycle reduces |i − j| by up to 2. Total cycles needed = ⌈max|i − j| / 2⌉ + 1.

Complexity target

O(N log N).

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; }
    sort(a.begin(), a.end()); // stable on (value, idx)

    int maxAbs = 0;
    for (int j = 0; j < N; ++j) maxAbs = max(maxAbs, abs(a[j].second - j));

    cout << (maxAbs + 1) / 2 + 1 << "\n";
}

Pitfalls

Problem 2 — Milking Order

Statement

Gold version: N cows numbered 1..N; M observations, each a sequence of cow ids that must appear in the final milking order as a subsequence. Find a milking order that satisfies the longest possible prefix of the M observations (i.e. some k such that observations 1..k can all be simultaneously satisfied but 1..k+1 cannot); among all orders satisfying that prefix, output the lexicographically smallest one.

Constraints

Key idea

Binary search on k = number of observations to include. For a given k, build a DAG with edges from each consecutive pair within each of the first k observations (a → b means a must precede b). The set is satisfiable iff the DAG has no cycle. Largest feasible k → binary search.

Once we know k, output the topological order that is lexicographically smallest. Use Kahn's algorithm with a min-heap instead of a queue — at each step, pop the smallest available cow (in-degree 0).

Complexity target

O((N + total_edges) · log M · log N). Sum of observation lengths is 2·105, so each cycle check is linear; binary search adds log M factor. Comfortable for the 2-second limit.

Reference solution (C++)

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

int N, M;
vector<vector<int>> obs;

bool feasible(int k, vector<int>& order) {
    vector<vector<int>> adj(N + 1);
    vector<int> indeg(N + 1, 0);
    for (int i = 0; i < k; ++i)
        for (int j = 1; j < (int)obs[i].size(); ++j) {
            adj[obs[i][j - 1]].push_back(obs[i][j]);
            ++indeg[obs[i][j]];
        }
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int v = 1; v <= N; ++v) if (indeg[v] == 0) pq.push(v);
    order.clear();
    while (!pq.empty()) {
        int u = pq.top(); pq.pop(); order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) pq.push(v);
    }
    return (int)order.size() == N;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    obs.assign(M, {});
    for (int i = 0; i < M; ++i) {
        int m; cin >> m; obs[i].resize(m);
        for (auto& x : obs[i]) cin >> x;
    }

    int lo = 0, hi = M;
    vector<int> dummy;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (feasible(mid, dummy)) lo = mid; else hi = mid - 1;
    }
    vector<int> order;
    feasible(lo, order);
    for (int i = 0; i < (int)order.size(); ++i)
        cout << order[i] << " \n"[i + 1 == (int)order.size()];
}

Pitfalls

Problem 3 — Talent Show

Statement

N cows. Cow i has weight wi and talent ti. Choose a non-empty subset S whose total weight is at least W, maximizing the ratio Σi∈S ti / Σi∈S wi. Output ⌊1000 · max_ratio⌋.

Constraints

Key idea

Classic fractional programming reformulation. The ratio Σt/Σw ≥ λ iff Σ(t − λw) ≥ 0. So binary-search λ on [0, max ratio]. For a candidate λ, define vali(λ) = ti − λwi and ask: is there a subset with Σ w ≥ W and Σ vali(λ) ≥ 0?

Answer with a knapsack-style DP on weight. Let dp[j] = max Σ vali(λ) achievable using a subset whose Σw is min(W, actualSum) = j (cap at W since any extra weight beyond W doesn't tighten the constraint). Iterate items; update dp[min(W, j + wi)] = max(dp[min(W, j + wi)], dp[j] + vali(λ)). Feasible iff dp[W] ≥ 0 after processing all items.

To avoid floating-point pain, scale: store dp values as fixed-point integers (× 1000) and binary-search the answer as an integer in [0, 250 · 1000].

Complexity target

O(N · W · log(max_answer)) ≈ 250 · 1000 · 18 ≈ 4.5·106. Fast.

Reference solution (C++)

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

int N, W;
vector<long long> w, t;

// Can we achieve Sigma (1000*t - lam*w) >= 0 with Sigma w >= W?
// Here lam is the scaled candidate (so we multiply talents by 1000).
bool feasible(long long lam) {
    vector<long long> dp(W + 1, LLONG_MIN / 4);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        long long vi = 1000LL * t[i] - lam * w[i];
        // iterate j in reverse so each item used at most once
        for (int j = W; j >= 0; --j) if (dp[j] != LLONG_MIN / 4) {
            int nj = min((long long)W, j + w[i]);
            dp[nj] = max(dp[nj], dp[j] + vi);
        }
    }
    return dp[W] >= 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> W;
    w.assign(N, 0); t.assign(N, 0);
    for (int i = 0; i < N; ++i) cin >> w[i] >> t[i];

    // Answer is an integer in [0, max(t)*1000] since each t_i <= 1000 and ratio <= max(t/w)*scale.
    long long lo = 0, hi = 250LL * 1000; // safe upper bound: 250 cows * max ratio (t up to 1000, w >= 1)
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        if (feasible(mid)) lo = mid; else hi = mid - 1;
    }
    cout << lo << "\n";
}

Pitfalls

What Gold US Open 2018 was actually testing