U USACO Prep

2023 US Open · Gold

← Back to 2023 US Open · Official results page

Gold this year leans on graph reasoning and constructive DP. G1 is a key-on-the-graph reachability puzzle with a constructive output, G2 is a weighted variant of the Pareidolia subsequence DP from Silver, and G3 is a tree-isomorphism / sibling-merge constructive problem.

Paraphrase warning. Statements here are summarized for my notes. Read the official problem on usaco.org before coding. Each problem links to the canonical statement.

G1 · Custodial Cleanup

Official statement (cpid=1329)

Statement (paraphrase)

A mootel has N stalls connected by M corridors. Stall i has color C_i. Initially key of color S_i is in stall i; FJ wants key F_i in stall i at the end. He starts in stall 1, can carry any number of keys, and may enter stall v ≠ 1 only while holding a key matching color C_v. He may pick up / drop keys at stalls he visits. Decide whether the target configuration is reachable and FJ can return to stall 1.

Subtasks

Constraints

Key idea

Two-phase analysis. Phase A (reach): compute the set R of stalls reachable from stall 1 with the multiset of keys present in their initial positions — BFS where you "unlock" a stall v when you've reached some stall holding a key of color C_v. This collects all keys reachable starting from {S_1}. Phase B (place): work backwards. Consider the target configuration with keys {F_i}; the same BFS from stall 1 must also collect every key. If both BFSes touch the same set of stalls and the multisets of collectable keys match the multisets of keys to be placed there, output YES. Constructive output is BFS-order pickups followed by reverse-BFS drop-offs.

Complexity

O((N + M) · α) per test — BFS with a queue keyed on "newly available colors."

Reference C++

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

// Multi-source BFS variant: a stall v is reachable when (a) some neighbor of v is reached
// and (b) we hold a key of color C[v]. Initially we hold {S[1]}; reaching a stall picks up
// its key (in the "initial" pass) or its "needed" key (in the "final" pass for placement).
struct Reach {
    int N;
    vector<vector<int>> adj;
    vector<int> C; // color
    vector<int> key; // key at stall i in this snapshot

    bool run(vector<char> &visited) {
        visited.assign(N + 1, 0);
        vector<int> haveCount(N + 2, 0); // how many copies of each color we hold
        // Pending: stalls we can reach but haven't unlocked yet, grouped by color needed.
        vector<vector<int>> pending(N + 2);
        queue<int> q;

        auto enter = [&](int v) {
            if (visited[v]) return;
            visited[v] = 1;
            // pick up its key
            haveCount[key[v]]++;
            // any pending stalls waiting on color key[v] can now be entered
            for (int u : pending[key[v]]) q.push(u);
            pending[key[v]].clear();
            q.push(v);
        };

        enter(1);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (visited[v]) continue;
                if (v == 1 || haveCount[C[v]] > 0) enter(v);
                else pending[C[v]].push_back(v);
            }
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        Reach R; R.N = N; R.adj.assign(N + 1, {}); R.C.assign(N + 1, 0);
        vector<int> S(N + 1), F(N + 1);
        for (int i = 1; i <= N; i++) cin >> R.C[i];
        for (int i = 1; i <= N; i++) cin >> S[i];
        for (int i = 1; i <= N; i++) cin >> F[i];
        for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; R.adj[a].push_back(b); R.adj[b].push_back(a); }

        vector<char> visA, visB;
        R.key = S; R.run(visA);
        R.key = F; R.run(visB);

        bool ok = true;
        // Both passes must reach the same set, AND the multiset of S-keys on visited stalls
        // must equal the multiset of F-keys on visited stalls (since we conserve keys).
        map<int,int> cntS, cntF;
        for (int i = 1; i <= N; i++) {
            if (visA[i] != visB[i]) ok = false;
            if (visA[i]) cntS[S[i]]++;
            if (visB[i]) cntF[F[i]]++;
        }
        if (cntS != cntF) ok = false;
        cout << (ok ? "YES" : "NO") << "\n";
    }
}

Pitfalls

G2 · Pareidolia

Official statement (cpid=1330)

Statement (paraphrase)

Given a string of length N and an integer cost c_i per character (deletion cost), return two numbers: the maximum count k* of non-overlapping "bessie" occurrences achievable by deleting any subset of characters, and the minimum total deletion cost to achieve that k*.

Subtasks

Constraints

Key idea

Greedy max-count is easy: scan left to right, match b-e-s-s-i-e in order, count completed copies. To minimize cost: among all greedy-optimal extractions, we have freedom in which instance of each letter we select. DP with 7 states (0..5 = progress within current bessie, 6 = "just completed, count incremented"): f[i][s] = (max copies, min cost) considering prefix t[..i] with current automaton state s. Transitions: skip character (pay c_i, stay) or use it (advance state if it matches expected letter). Within "must achieve max copies," cost-minimizing means at every position we either advance (free) or delete (cost c_i) — but the count constraint says we must end each bessie with as few skipped characters in-between as possible. Track (count, cost) as a lexicographic pair maximizing count then minimizing cost.

Complexity

O(N · 6) time and space — 6-state DP scanned once.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t; cin >> t;
    int N = t.size();
    vector<int> c(N);
    for (auto &x : c) cin >> x;
    const string B = "bessie";

    // dp[s] = (maxCount, minCostToAchieve) for current prefix in state s.
    // We want lexicographic: max count first, then min cost.
    const long long NEG = LLONG_MIN / 4;
    array<pair<long long,long long>, 6> dp;
    for (int s = 0; s < 6; s++) dp[s] = {NEG, 0};
    dp[0] = {0, 0};

    auto better = [&](pair<long long,long long> a, pair<long long,long long> b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    };

    for (int i = 0; i < N; i++) {
        array<pair<long long,long long>, 6> nd;
        for (int s = 0; s < 6; s++) nd[s] = {NEG, 0};
        for (int s = 0; s < 6; s++) {
            if (dp[s].first == NEG) continue;
            // Option 1: delete t[i]; stay in state s; cost += c[i].
            pair<long long,long long> opt1 = {dp[s].first, dp[s].second + c[i]};
            if (better(opt1, nd[s])) nd[s] = opt1;
            // Option 2: keep t[i]. If t[i] == B[s], advance state; if state was 5, increment count and wrap to 0.
            if (t[i] == B[s]) {
                int ns = (s + 1) % 6;
                long long addCount = (s == 5) ? 1 : 0;
                pair<long long,long long> opt2 = {dp[s].first + addCount, dp[s].second};
                if (better(opt2, nd[ns])) nd[ns] = opt2;
            } else {
                // Keeping a non-matching character "breaks" — but only if we were mid-bessie?
                // Actually keeping doesn't break: a non-matching kept char is fine — it just
                // doesn't advance. So keep stays in state s, cost 0.
                pair<long long,long long> opt3 = {dp[s].first, dp[s].second};
                if (better(opt3, nd[s])) nd[s] = opt3;
            }
        }
        dp = nd;
    }

    pair<long long,long long> best = {NEG, 0};
    for (int s = 0; s < 6; s++) if (better(dp[s], best)) best = dp[s];
    cout << best.first << " " << best.second << "\n";
}

Pitfalls

G3 · Tree Merging

Official statement (cpid=1331)

Statement (paraphrase)

Given an initial rooted tree on N nodes and a target rooted tree on M ≤ N nodes, output a sequence of "merge two distinct siblings into one node" operations that transforms the initial tree into the target. After merging siblings u and v, the resulting node takes the max label and the union of their children. The problem guarantees a valid sequence exists.

Subtasks

Constraints

Key idea

Process the trees top-down, level by level from the root. At each node v of the target tree, you have a corresponding subset of nodes in the initial tree that must merge into v. Recurse on the children: target's child set must be matchable to a partition of the initial tree's grand-children-equivalence-classes. Because labels take the max, you can identify each target child by its label = max label in its descendants in the initial tree. Greedy: sort children by required max-label and emit merges of the initial siblings whose subtree-max-labels group together.

Complexity

O(N · M) or O((N + M) · log) per test, well under 1000² = 10⁶ ops.

Reference C++

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

// Sketch — full constructive solution is involved. This skeleton verifies feasibility
// (assumed by problem) and emits merges by recursively matching target children to
// initial subtree-groups by max-label.

int N, M;
vector<vector<int>> initCh, finCh;
vector<int> subMax;

int dfsMax(int u, const vector<vector<int>> &ch) {
    int m = u;
    for (int v : ch[u]) m = max(m, dfsMax(v, ch));
    subMax[u] = m;
    return m;
}

void solve(int uI, int uF, vector<pair<int,int>> &merges) {
    // Group initCh[uI] by their subtree-max-label (computed in subMax).
    // Match each group to one child of uF (which has label == that max).
    map<int, vector<int>> group; // max-label -> list of initial children
    for (int c : initCh[uI]) group[subMax[c]].push_back(c);
    // Each target child uFc with label L expects group[L] to be its merged set.
    for (int uFc : finCh[uF]) {
        int L = uFc; // labels in final tree are 1..M; the matching label is L itself
        auto it = group.find(L);
        if (it == group.end() || it->second.empty()) continue; // problem guarantees solvable
        vector<int> &g = it->second;
        // Merge all in g into one node (pairwise; output (a, b) merges).
        while (g.size() > 1) {
            int a = g.back(); g.pop_back();
            int b = g.back(); // keep b as the survivor (with max label semantics handled)
            merges.push_back({a, b});
            // After merge, b's children = union of a's and b's children.
            for (int c : initCh[a]) initCh[b].push_back(c);
            initCh[a].clear();
        }
        // Recurse into the surviving node, which now represents uFc.
        solve(g.back(), uFc, merges);
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> N;
        initCh.assign(N + 1, {});
        for (int i = 0; i < N - 1; i++) { int c, p; cin >> c >> p; initCh[p].push_back(c); }
        cin >> M;
        finCh.assign(M + 1, {});
        for (int i = 0; i < M - 1; i++) { int c, p; cin >> c >> p; finCh[p].push_back(c); }

        subMax.assign(N + 1, 0);
        dfsMax(1, initCh);

        vector<pair<int,int>> merges;
        solve(1, 1, merges);
        cout << merges.size() << "\n";
        for (auto [a, b] : merges) cout << a << " " << b << "\n";
    }
}

Pitfalls