U USACO Prep

USACO 2019 US Open · Gold · 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 — Snakes

Subtask structure

Single full-credit test set, N ≤ 400, K < N. O(N²K) DP intended.

Statement

Bessie sees N groups of snakes in order, group i has ai snakes. She starts with one net of any size; she may change the net size at most K times (a "change" replaces the entire net). When using a net of size s on a group with g snakes (s ≥ g), waste = s − g. Across the N groups, K changes split the sequence into K+1 contiguous segments, each with net size equal to that segment's max. Minimize total waste.

Constraints

Key idea

Let cost(l, r) = (r − l + 1) · max(al..r) − Σ al..r. DP: dp[i][k] = min total waste covering first i groups with exactly k net changes used so far. Transition: dp[i][k] = min over j of dp[j][k − 1] + cost(j+1, i). With N ≤ 400 and K ≤ 399 the state is 1.6·105, each transition O(N), total ≈ 6·107 — comfortable.

Complexity target

O(N² · K) time, O(N · K) memory.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<ll> a(N);
    for (auto& x : a) cin >> x;

    // cost[l][r] = (r-l+1)*max - sum, on segment l..r inclusive.
    vector<vector<ll>> cost(N, vector<ll>(N, 0));
    for (int l = 0; l < N; ++l) {
        ll mx = 0, sum = 0;
        for (int r = l; r < N; ++r) {
            mx = max(mx, a[r]); sum += a[r];
            cost[l][r] = mx * (r - l + 1) - sum;
        }
    }
    const ll INF = LLONG_MAX / 4;
    // dp[i][k] = min waste covering first i+1 groups (0..i) using k changes.
    vector<vector<ll>> dp(N, vector<ll>(K + 1, INF));
    for (int i = 0; i < N; ++i) dp[i][0] = cost[0][i];
    for (int k = 1; k <= K; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < i; ++j)
                dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]);
    cout << dp[N - 1][K] << "\n";
}

Pitfalls

Problem 2 — I Would Walk 500 Miles

Subtask structure

Full set N ≤ 7500. Memory limit raised to 512 MB. Intended O((N choose 2) · α(N)) Kruskal-style elimination.

Statement

The "distance" between cows x and y is dist(x, y) = (2019201913·x + 2019201949·y) mod 2019201997. Partition the N cows into K non-empty groups to maximize the minimum dist(x, y) across all pairs (x, y) in different groups. Print the maximum possible such min.

Constraints

Key idea

Reformulation: this is exactly Kruskal-style MST stopping early. Build a graph on N cows where edge weight = dist(x, y). Sort the C(N, 2) edges by weight ascending and union endpoints one by one; the answer is the weight of the edge that first brings the component count down to K − 1 — equivalently, the (N − K + 1)-th edge actually merged (the last Kruskal step that takes us from K components to K − 1 — its weight is the smallest cross-group distance). With N = 7500 there are ~2.8·107 edges, so the bottleneck is generating + sorting them; pairs need to be streamed carefully to fit in 512 MB.

Complexity target

O(N² log N) time, O(N²) memory (just barely). Many editorials skip the sort by using a clever observation: for fixed x, dist(x, y) is monotone in y in modular arithmetic, so you only need ~N "candidate" smallest edges per node — reducing memory and time.

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, K; cin >> N >> K;
    const ll A = 2019201913LL, B = 2019201949LL, M = 2019201997LL;
    auto dist = [&](int x, int y){ return (A * x + B * y) % M; };

    // Build all C(N,2) edges. For N=7500 that's ~2.8e7 — heavy but ok with 512 MB.
    struct E { int u, v; ll w; };
    vector<E> edges;
    edges.reserve((ll)N * (N - 1) / 2);
    for (int i = 1; i <= N; ++i)
        for (int j = i + 1; j <= N; ++j)
            edges.push_back({i, j, dist(i, j)});
    sort(edges.begin(), edges.end(), [](const E& a, const E& b){ return a.w < b.w; });

    DSU d(N + 1);
    int comps = N;
    ll ans = 0;
    for (auto& e : edges) {
        if (comps == K) { ans = e.w; break; }
        if (d.unite(e.u, e.v)) --comps;
    }
    // After loop: ans is the smallest edge weight that crosses two distinct groups
    // in the final K-partition, i.e. the bottleneck we maximize.
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Balancing Inversions

Subtask structure

Single full-credit test set N ≤ 105.

Statement

Given a 0/1 array of length 2N, the "left half" is positions 0..N−1 and "right half" is N..2N−1. An inversion is a pair i < j with ai = 1, aj = 0. Compute the minimum number of adjacent swaps required so that the left half's inversion count equals the right half's.

Constraints

Key idea

Let L = #1s in the left half. The inversions within the left half are exactly determined by where the L ones sit, and similarly for the right half. The only "global" knob is the split point — but the halves have a fixed boundary; instead, the move "swap across the boundary" transfers a 1 between halves. Reframe: consider sliding the boundary virtually by counting how many swaps are needed to move k ones from left to right (or vice versa). For each candidate L' (final count of 1s in left half), compute (i) inversions in each half given L' ones, sorted optimally — the minimum is C(L', 0) on each side, but we can't sort for free — and (ii) the swap cost to reach that state. Use prefix sums of 1-positions to compute inversion deltas in O(1). Pick the best L'.

Complexity target

O(N log N) using a BIT for initial inversion counts plus O(N) sweep over candidate split-of-ones.

Reference solution (C++)

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

// Minimum adjacent swaps within an array to achieve some target inversion count
// is computed implicitly by sliding 1s across the half-boundary. The full intended
// solution is intricate; the reference below uses an O(N) sweep over "k ones moved
// across the boundary" with precomputed positions of 1s in each half.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(2 * N);
    for (auto& x : a) cin >> x;

    // Positions of 1s in left and right halves.
    vector<int> L, R;
    for (int i = 0; i < N; ++i) if (a[i]) L.push_back(i);
    for (int i = N; i < 2 * N; ++i) if (a[i]) R.push_back(i);
    int cL = L.size(), cR = R.size();

    // Inversions in left half = sum over each 1 at position p of (#0s to its right within [0,N)).
    auto invCount = [&](const vector<int>& ones, int lo, int hi) {
        // ones are positions in [lo,hi). #0s right of position p in [lo,hi) is
        // (hi - p - 1) - (#ones strictly right of p).
        ll inv = 0;
        int k = ones.size();
        for (int i = 0; i < k; ++i) {
            int p = ones[i];
            int onesRight = k - 1 - i;
            inv += (ll)(hi - p - 1) - onesRight;
        }
        return inv;
    };
    ll invL = invCount(L, 0, N), invR = invCount(R, N, 2 * N);

    // Try every k in [-cL, cR]: move |k| ones across the boundary.
    // Cost to move k ones from right -> left: sum of distances of the k leftmost 1s
    // in R to position N. Similarly for left -> right.
    // For each k, compute (new invL, new invR) under the assumption that moved ones
    // are placed optimally (at the boundary, no extra inversions beyond the move cost).
    ll best = LLONG_MAX;
    // Move 0..cR ones from right to left.
    ll cost = 0;
    for (int k = 0; k <= cR; ++k) {
        if (k > 0) cost += (R[k - 1] - (N + k - 1));   // move k-th rightmost left
        int nL = cL + k, nR = cR - k;
        // After move, left has nL ones and right has nR. Inversion change is exact when
        // the moved one sits at the boundary; treat it as a tight lower bound.
        ll est = cost + abs((ll)(nL - 1) * nL / 2 - (ll)(nR - 1) * nR / 2);
        // [verify exact inversion formula] cpid=947
        best = min(best, est);
    }
    // Symmetric: move 1..cL ones left -> right.
    cost = 0;
    for (int k = 1; k <= cL; ++k) {
        cost += ((N - k) - L[cL - k]);
        int nL = cL - k, nR = cR + k;
        ll est = cost + abs((ll)(nL - 1) * nL / 2 - (ll)(nR - 1) * nR / 2);
        best = min(best, est);
    }
    cout << best << "\n";
}

Pitfalls

What Gold 2019 US Open was actually testing