U USACO Prep

USACO 2021 US Open · Gold · all three problems

← Full US Open 2021 set · Official results

Source. Statements and constraints are paraphrased from usaco.org/index.php?page=open21results. 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 — United Cows of Farmer John

Subtasks

Statement

N cows stand in a line, each with a breed bi ∈ [1, N]. Count the number of contiguous intervals [l, r] of length ≥ 2 such that bl ≠ br and neither bl nor br appears anywhere in (l, r). The two endpoints are "leaders"; their breeds must be unique inside the interval and different from each other.

Constraints

Key idea

Sweep r from 1 to N. Maintain for each breed b the position prev[b] = previous occurrence (or 0). When r advances, the valid left endpoint l must satisfy: (1) prev[br] < l (so br doesn't appear inside), (2) bl ≠ br, (3) bl doesn't appear in (l, r). The third condition means bl last occurred at or before l. Use a Fenwick tree over positions: mark every position i with +1 iff i is the current "rightmost occurrence so far" of its breed; then valid l's are those marked positions in (prev[br], r). Subtract the l whose breed equals br (which is prev[br] itself when it's still in range — but it's not, since we required l > prev[br]).

Complexity target

O(N log N) — Fenwick of size N with two point-updates per step (clear old marker, set new) and one prefix-sum query.

Reference solution (C++)

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

struct BIT {
    int n; vector<int> t;
    BIT(int n) : n(n), t(n + 2, 0) {}
    void upd(int i, int v) { for (++i; i <= n; i += i & -i) t[i] += v; }
    int qry(int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += t[i]; return s; }
    int range(int l, int r) { return l > r ? 0 : qry(r) - (l ? qry(l-1) : 0); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> b(N);
    for (auto& x : b) cin >> x;
    vector<int> last(N + 1, -1);   // last occurrence index of each breed
    BIT bit(N);
    ll ans = 0;
    for (int r = 0; r < N; ++r) {
        int br = b[r];
        // Valid l in (last[br], r-1], with the additional constraint that l is the
        // current "rightmost so far" of b[l] AND b[l] != br.
        int lo = last[br] + 1, hi = r - 1;
        if (lo <= hi) ans += bit.range(lo, hi);
        // Now update markers: position r becomes the new rightmost for br;
        // clear the old marker if any.
        if (last[br] != -1) bit.upd(last[br], -1);
        bit.upd(r, +1);
        last[br] = r;
    }
    cout << ans << "\n";
}

Pitfalls

Problem 2 — Portals

Subtasks

Statement

There are N vertices, each with exactly 4 portal-ends, grouped initially into 2 unordered pairs of portal-ends per vertex. Each portal connects two portal-ends. A "location" is a (vertex, portal-pair) state; from a location you can switch to the other location at the same vertex or traverse a portal to the connected portal-end's location. Bessie can permute the pairing at vertex v at cost cv (rearranging which two pairs of portal-ends are grouped together — 3 possible pairings of 4 ends, but typically counted as a single "rearrangement" cost). Find the minimum total cost so that all 2N locations become mutually reachable.

Constraints

Key idea

Reformulate: build a graph G where each portal-pair at vertex v becomes a node (so 2N nodes total); each portal connects two such nodes. With the initial pairing, G has 2N nodes and 2N edges, so it splits into components each forming a single cycle (since every node has degree 2). Rearranging vertex v's pairing merges/splits its two local nodes. The cost-minimum spanning structure is found by, conceptually, picking one vertex from each component to "spend" — specifically, with k components we need k − 1 rearrangements (each merges two components), each at the minimum cv in the union. Implement with a DSU keyed on portal-pair nodes; sort vertices by cv; process in increasing order, and pay cv every time vertex v's two pair-nodes lie in different components (because rearranging v can stitch them).

Complexity target

O(N α(N)) for DSU + O(N log N) for sorting. Total: O(N log 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 f(int x) { return p[x] == x ? x : p[x] = f(p[x]); }
    bool unite(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; cin >> N;
    // Each vertex v has 4 portal-ends labeled v's "a b c d"; initially paired (a,b) and (c,d).
    // Each portal-pair becomes a node: 2v and 2v+1 (the two pairs at vertex v).
    // Read costs, then for each portal-end map (portal-id -> list of pair-nodes that contain it).
    vector<int> cost(N);
    // pair_of[portal_end] = pair-node id (2v or 2v+1).
    map<int, int> pair_of;
    for (int v = 0; v < N; ++v) {
        int a, b, c, d; cin >> cost[v] >> a >> b >> c >> d;
        pair_of[a] = pair_of[b] = 2*v;
        pair_of[c] = pair_of[d] = 2*v + 1;
    }

    // Portals: each portal-end id appears in exactly 2 vertices' pair_of (it's an endpoint).
    // Group endpoints by id; each id has exactly 2 occurrences -> an edge between two pair-nodes.
    map<int, vector<int>> ends;
    // (Re-read; the cleanest implementation reads input twice or stores the 4-tuples — kept brief here.)
    // For brevity assume we have collected edges (u, w) in 'edges'.
    vector<pair<int,int>> edges;   // populate from pair_of as described

    DSU dsu(2 * N);
    for (auto& [u, w] : edges) dsu.unite(u, w);

    // Now pay c[v] for every vertex v whose two pair-nodes (2v, 2v+1) are in different components,
    // in increasing cost order, uniting as we go.
    vector<int> idx(N); iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return cost[a] < cost[b]; });
    ll ans = 0;
    for (int v : idx) {
        if (dsu.unite(2*v, 2*v + 1)) ans += cost[v];
    }
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Permutation

Subtasks

Statement

Given N points in general position (no three collinear), Bessie picks a permutation π. She draws every pairwise segment incrementally: first the triangle on π1, π2, π3, then when adding πk (k ≥ 4) she draws segments from πk to all earlier πj (j < k) that don't cross any already-drawn segment. Count permutations where every step k ≥ 4 adds exactly 3 segments. Output mod 109+7.

Constraints

Key idea

"Adds exactly 3 segments" forces each new point to "see" exactly 3 previous points unobstructed — which geometrically means each new point is added inside a single existing triangular face, splitting it into 3 sub-triangles. So the configuration after k points is a triangulation of the convex hull of those k points using exactly the points-as-vertices (no Steiner points), and successive additions are triangle-subdivisions. The first 3 points form a triangle, the 4th must be strictly inside (otherwise it sees only 2 hull edges). Precompute, for each unordered triple (i, j, k) and each point p, whether p is strictly inside triangle ijk. DP over subsets is 240 — too large; instead use the structure: the answer counts ordered sequences, and a clean recursion is over which triple started times the number of valid orderings of the remaining N − 3 insertions, each of which must land in some current triangle. This is the editorial's setup; a clean implementation uses a 3D DP indexed by triangle (i, j, k) storing "number of ways to fill the interior point-set". Complexity O(N4) with precomputation of in-triangle relations.

Complexity target

O(N4) precompute + O(N4) DP. With N = 40 that's 2.5 million subproblems, easily under a second.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

int N;
vector<ll> X, Y;

ll cross(int o, int a, int b) {
    return (X[a]-X[o])*(Y[b]-Y[o]) - (Y[a]-Y[o])*(X[b]-X[o]);
}
// Is p strictly inside triangle (a,b,c)? No-three-collinear guarantees sign != 0.
bool inside(int a, int b, int c, int p) {
    ll s1 = cross(a, b, p), s2 = cross(b, c, p), s3 = cross(c, a, p);
    return (s1 > 0 && s2 > 0 && s3 > 0) || (s1 < 0 && s2 < 0 && s3 < 0);
}

// dp[a][b][c] = number of ordered sequences of insertions that triangulate the
// interior of triangle (a,b,c) given exactly the points strictly inside it.
// Recurrence: dp[a][b][c] = sum over chosen first interior point p of
//     C(k-1, k1, k2, k3) * dp[a][b][p] * dp[b][c][p] * dp[c][a][p],
// where k = #points strictly inside (a,b,c), k1/k2/k3 are interior counts of
// the three sub-triangles, and k1+k2+k3 = k-1. Base: dp = 1 if interior empty.
unordered_map<ll, ll> memo;
ll key(int a, int b, int c) {                    // canonical key: sorted triple
    int v[3] = {a,b,c}; sort(v, v+3);
    return ((ll)v[0] * 64 + v[1]) * 64 + v[2];
}

vector<vector<vector<vector<int>>>> ins;       // ins[a][b][c] = list of pts inside
ll fact[45], inv_fact[45];
ll mpow(ll b, ll e) { ll r=1; b%=MOD; while(e){ if(e&1) r=r*b%MOD; b=b*b%MOD; e>>=1;} return r; }
ll C(int n, int k) { if (k<0||k>n) return 0; return fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD; }

ll solve(int a, int b, int c) {
    ll k = key(a, b, c);
    auto it = memo.find(k);
    if (it != memo.end()) return it->second;
    auto& pts = ins[a][b][c];
    if (pts.empty()) return memo[k] = 1;
    ll res = 0;
    int sz = pts.size();
    for (int p : pts) {
        // counts in the three sub-triangles (a,b,p), (b,c,p), (c,a,p)
        int k1 = 0, k2 = 0, k3 = 0;
        for (int q : pts) if (q != p) {
            if (inside(a, b, p, q)) ++k1;
            else if (inside(b, c, p, q)) ++k2;
            else ++k3;
        }
        ll ways = C(sz - 1, k1) * C(sz - 1 - k1, k2) % MOD;
        ways = ways * solve(a, b, p) % MOD * solve(b, c, p) % MOD * solve(c, a, p) % MOD;
        res = (res + ways) % MOD;
    }
    return memo[k] = res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    X.assign(N, 0); Y.assign(N, 0);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];
    fact[0] = 1;
    for (int i = 1; i < 45; ++i) fact[i] = fact[i-1] * i % MOD;
    inv_fact[44] = mpow(fact[44], MOD - 2);
    for (int i = 43; i >= 0; --i) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;

    // Precompute interior point-sets for every triangle.
    ins.assign(N, vector(N, vector<vector<int>>(N)));
    for (int a = 0; a < N; ++a) for (int b = 0; b < N; ++b) for (int c = 0; c < N; ++c) {
        if (a == b || b == c || a == c) continue;
        for (int p = 0; p < N; ++p) if (p!=a&&p!=b&&p!=c && inside(a,b,c,p))
            ins[a][b][c].push_back(p);
    }

    // Sum over the initial triangle (a,b,c) — must be a CCW triple on the convex hull
    // and contain all other N-3 points. Order of the first 3 matters for the count:
    // any ordered triple of the same 3 hull points is one valid "start".
    ll ans = 0;
    for (int a = 0; a < N; ++a) for (int b = 0; b < N; ++b) for (int c = 0; c < N; ++c) {
        if (a==b||b==c||a==c) continue;
        if ((int)ins[a][b][c].size() != N - 3) continue;        // contains all others
        ans = (ans + solve(a, b, c)) % MOD;
    }
    cout << ans << "\n";
}

Pitfalls

What Gold US Open 2021 was actually testing