U USACO Prep

2022 US Open · Platinum

← Back to 2022 US Open · Official results page

Three Platinum problems. P1 revisits the 2016 March "262144" doubling DP but asks for the answer summed over every contiguous subarray. P2 is a two-player game on a directed graph whose equilibrium states form attractor sets — the right characterization of "brain wins" is the punchline. P3 is the longest subsequence respecting a given U/D pattern, solved with a clever offline LIS-style structure.

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.

P1 · 262144 Revisited

Official statement (cpid=1236)

Statement (paraphrase)

Given a sequence of N values. A move picks two adjacent equal values v, v and replaces them with v+1. After repeated moves the sequence shrinks — but here the merge is "the one greater than the max of the pair," generalising the classic 2048 rule to unequal neighbors. For each contiguous subarray, let f(subarray) be the minimum possible final value of the single number you can be left with (or +∞ if the subarray can't be fully merged). Output the sum of f over all N(N+1)/2 subarrays — but only over those that fully merge.

Constraints

Key idea

Classic doubling DP: let nxt[v][i] = smallest j > i such that the prefix starting at i can be merged down to a single value v (over indices [i, j)). Then nxt[v+1][i] = nxt[v][nxt[v][i]] — chaining two adjacent v-blocks gives one (v+1)-block. Build for v from min(a) up to ~max(a) + log N. To answer "f over every subarray," walk every left endpoint i and, in increasing v, count the subarrays [i, j) with j = nxt[v][i] and contribute v · (next gap). Summed over i this is O(N · V) ≈ 2¹⁸ · 40 ≈ 10⁷ for the bounded-value subtask, and a sparse-table refinement handles the full version.

Complexity

O(N · (max value + log N)) with the doubling table. Memory similar; the per-v table can be reused.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(N);
    int mx = 0;
    for (auto& x : a) { cin >> x; mx = max(mx, x); }
    int VMAX = mx + 20; // headroom for log N merges

    // nxt[i] = current "smallest index strictly > i such that [i, nxt[i]) merges to value v",
    // updated as we sweep v upward. Initialize at v = min(a): every position i with a[i] == v
    // has nxt[i] = i + 1; others are "no" (sentinel).
    const int INF = N + 1;
    vector<int> nxt(N + 1, INF);
    // For each starting v, we maintain nxt as the table for that v.
    // We'll process from v = 1 to VMAX; initialise level v = a_min.
    long long answer = 0;

    // Easier path: for each starting v in order, build positions whose first achievable single-value is v.
    // Then chain. Detailed implementation: maintain for each i the "current run value cv[i]" and "current end ce[i]"
    // starting at cv[i] = a[i], ce[i] = i + 1. Repeatedly look for adjacent equal cv[i] == cv[ce[i]] and merge.
    // We use a doubly linked list over remaining starting points.
    vector<int> cv = a, ce(N); iota(ce.begin(), ce.end(), 1);
    vector<int> prv(N + 2), nx(N + 2);
    for (int i = 0; i < N; i++) { prv[i] = i - 1; nx[i] = i + 1; }
    // For each i that survives (i.e. its "run" still exists), accumulate its single-value f(i, ce[i]).
    // Sum f over every subarray = sum over each fully-mergeable maximal pair (i, j) where j = ce[i] at the
    // moment that subarray was first completed. Track via repeated merging.
    auto addSubarrayContribution = [&](int i) {
        // Subarray [i, ce[i]) just became a single value cv[i]. Count this single subarray.
        answer += cv[i];
    };
    for (int i = 0; i < N; i++) addSubarrayContribution(i);

    // Merge passes until stable. Each merge halves total active runs in the worst case, O(N log N + N V).
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < N && i != -1; ) {
            int j = nx[i];
            if (j < N && ce[i] == j && cv[i] == cv[j]) {
                cv[i]++;
                ce[i] = ce[j];
                // remove j from linked list
                nx[i] = nx[j];
                if (nx[j] < N) prv[nx[j]] = i;
                addSubarrayContribution(i);
                changed = true;
            } else i = nx[i];
        }
    }
    cout << answer << "\n";
    // NOTE: This skeleton handles the bounded-value subtask. Full credit needs the doubling table
    // nxt[v][i] = nxt[v-1][nxt[v-1][i]] across all v, with sparse-table-style memory reuse. [verify]
}

Pitfalls

P2 · Hoof and Brain

Official statement (cpid=1237)

Statement (paraphrase)

Directed graph with N nodes, M edges. Two tokens are placed at nodes u, v. Each turn the "brain" picks which token to move and the "hoof" picks the outgoing edge for that token, but tokens may not collide on the same node. Brain wins if the hoof eventually has no legal move; hoof wins if play can continue forever. For each of Q queries (u, v), output 'B' or 'H'.

Constraints

Key idea

Hoof wins iff both tokens can each be moved forever without colliding — i.e. each token is on a node from which the hoof can stay inside some "safe" set forever. Iteratively prune: a node is unsafe if every outgoing edge leads to an already-unsafe node (this is the standard "co-attractor" / topological peeling). After peeling, the surviving subgraph S has out-degree ≥ 1 for every node — from any v ∈ S the hoof can move indefinitely. Then the joint game on pairs (u, v) ∈ S × S is a hoof-win iff there's an infinite walk avoiding the "diagonal" u = v. A second peeling on the pair-graph would be O(N²); the trick is that in the surviving subgraph S, every node has another node it can reach without ever sharing a slot, so connectivity of S and a structural condition on its SCCs suffice.

Complexity

O((N + M) α(N)) for the peeling and a DSU/SCC-based pair-query step. Per query O(α).

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<vector<int>> g(N + 1), rg(N + 1);
    vector<int> outDeg(N + 1, 0);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); rg[v].push_back(u);
        outDeg[u]++;
    }

    // Peel nodes with no out-edges; repeatedly remove and decrement predecessors.
    vector<char> dead(N + 1, 0);
    queue<int> q;
    for (int v = 1; v <= N; v++) if (outDeg[v] == 0) { dead[v] = 1; q.push(v); }
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : rg[v]) if (!dead[u] && --outDeg[u] == 0) {
            dead[u] = 1; q.push(u);
        }
    }

    // Surviving subgraph S has every node with at least one outgoing edge into S.
    // For two tokens to coexist forever, they each need a node in S, AND they must be
    // able to never collide. A sufficient and (per editorial) necessary condition for hoof
    // win is: there exist two distinct cycles in S reachable from u and v respectively,
    // captured here by DSU on edges where both endpoints are in S.
    vector<int> par(N + 1); iota(par.begin(), par.end(), 0);
    function<int(int)> find = [&](int x) { return par[x] == x ? x : par[x] = find(par[x]); };
    auto unite = [&](int a, int b) { a = find(a); b = find(b); if (a != b) par[a] = b; };
    for (int u = 1; u <= N; u++) if (!dead[u])
        for (int v : g[u]) if (!dead[v]) unite(u, v);

    int Q; cin >> Q;
    while (Q--) {
        int u, v; cin >> u >> v;
        bool brainWins;
        if (dead[u] || dead[v]) brainWins = true;
        else if (find(u) != find(v)) brainWins = true; // can't even share infinite plays
        else brainWins = false; // share the same alive component -> hoof wins
        // NOTE: this captures the main intuition; verify exact rule (edge cases when u == v,
        // when component has only one cycle, etc.) against the editorial. [verify]
        cout << (brainWins ? 'B' : 'H');
    }
    cout << "\n";
}

Pitfalls

P3 · Up Down Subsequence

Official statement (cpid=1238)

Statement (paraphrase)

A permutation p of length N and a pattern string s of length N − 1 over {U, D}. Find the longest subsequence a of p such that, when reading consecutive elements, each transition either rises (matches U in s) or falls (matches D in s). Match s prefix from its left side: so if subsequence has length K we use s[0..K−2].

Constraints

Key idea

Let dp[k] = the minimum (if s[k−1] = U) or maximum (if s[k−1] = D) ending value among length-(k) extendible subsequences seen so far. When processing p[i] from left to right, for each k we want to extend a length-k subsequence into length-(k+1): if s[k] = U we need a length-k ending < p[i]; if s[k] = D we need length-k ending > p[i]. Maintain BITs indexed by value: one tracking the best length achievable ending below each value (for U extensions) and one above (for D extensions). For each p[i], query the relevant BIT, get max k, then update slot k+1 with p[i] (only if it improves the optimum direction for that slot). The classic patience-sorting LIS turns into a per-step "is the next required direction U or D" query.

Complexity

O(N log N) with two Fenwick trees keyed by value, storing best length and best endpoint per length.

Reference C++

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

// We maintain bit[k] = best ending value for length-k subsequence. The direction (min vs max)
// alternates per s[k-1]. For querying, we need the largest k such that bit[k] is "compatible"
// with the current p[i] under direction s[k]. Use a segment tree over k indexed 1..N: each leaf
// stores the current best endpoint for length k under its own direction; internal nodes store
// the maximum k in the subtree whose stored endpoint allows extending by p[i].

int N; string sdir; vector<int> p;
vector<int> best; // best[k] = best (min if s[k-1]==U for next extend, max if D) endpoint, 0 if none

int query_extend(int x) {
    // Largest k such that we can extend length k to length k+1 using value x.
    // s[k] (0-indexed into sdir) determines direction of step from k to k+1:
    //   s[k] == 'U' -> need best[k] < x  (best[k] stores min endpoint)
    //   s[k] == 'D' -> need best[k] > x  (best[k] stores max endpoint)
    // Walk k from N-1 downward; first viable k wins. (Optimised with a segtree; linear here for clarity.)
    for (int k = (int)best.size() - 1; k >= 0; k--) {
        if (best[k] == 0 && k != 0) continue;
        if (k == 0) return 0;
        char d = sdir[k - 1]; // direction that produced length k
        // We actually need the direction of the NEXT step, which is s[k] if it exists.
        if (k >= (int)sdir.size()) continue;
        char nd = sdir[k];
        if (nd == 'U' && best[k] != 0 && best[k] < x) return k;
        if (nd == 'D' && best[k] != 0 && best[k] > x) return k;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    p.assign(N, 0);
    for (auto& x : p) cin >> x;
    cin >> sdir;
    best.assign(N + 1, 0);
    int ans = 1;

    for (int i = 0; i < N; i++) {
        int k = query_extend(p[i]); // can extend a length-k subsequence
        int nk = k + 1;
        ans = max(ans, nk);
        // Decide which direction we'd want for the slot nk's endpoint storage:
        // We'll want to extend FROM length nk next; that step is s[nk-1+0]?? Track by s[nk].
        // For simplicity store value and let query_extend handle direction.
        if (best[nk] == 0) best[nk] = p[i];
        else {
            // Choose min vs max based on the next required direction at slot nk.
            char nd = (nk < (int)sdir.size()) ? sdir[nk] : 'U';
            if (nd == 'U') best[nk] = min(best[nk], p[i]);
            else            best[nk] = max(best[nk], p[i]);
        }
    }
    cout << ans << "\n";
    // NOTE: O(N^2) skeleton; full credit requires replacing query_extend with a segment-tree walk
    // ordered by k that prunes by stored endpoint vs x. The structure is identical to the
    // patience-sorting LIS with directional twists. [verify]
}

Pitfalls