U USACO Prep

2023 US Open · Platinum

← Back to 2023 US Open · Official results page

Three brutal problems: P1 is the Platinum endgame of the Pareidolia theme with point updates and segment-tree composition over a 6-state automaton; P2 is a Stern-Brocot / Euclidean recursion on a strange bitstring generator; P3 is a graph-contraction counting problem on trees that often takes a centroid-decomposition flavor.

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 · Pareidolia

Official statement (cpid=1332)

Statement (paraphrase)

Given a string t of length N and U point updates (position p, new char c), maintain after every update the sum over all contiguous substrings s of t of B(s) — the max number of non-overlapping "bessie" subsequences extractable from s.

Subtasks

Constraints

Key idea

Represent the Silver scan as a sequence of per-character "transition matrices" over the 6-state automaton, augmented with two scalars: (a) for each starting state s, the state after the segment and the number of completed bessies; (b) the running "sum of bessies over all (start,end) pairs in the segment." Combine left and right segments with a well-defined merge: for each starting state s_L, the right segment sees the resulting state and adds its (completed count) for that entry state. Build a segment tree over the N characters; each leaf is a constant-size structure (state-transition + bessie counts + per-starting-state suffix sums). Point update = replace a leaf + O(log N) merges.

Complexity

O((N + U) · 6² · log N) ≈ 10⁸ — tight but feasible in 4 s with careful constant factor.

Reference C++

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

// Each segment tree node stores, for each starting automaton state s in [0..5]:
//   to[s]    = state after applying the segment
//   cnt[s]   = number of bessies completed when starting in state s
//   subSum   = sum over all (L, R) pairs inside this segment of B(t[L..R]),
//              expressed as: when we start a fresh substring at any position inside,
//              how many bessies it completes by the segment end + tail.
// Merging is associative: left . right.

struct Node {
    int to[6];
    long long cnt[6];          // # bessies if entering segment in state s
    long long sumStartsHere;   // sum over starts L inside this segment of completed bessies by segment end
    int len;
};

const string B = "bessie";

Node makeLeaf(char c) {
    Node n;
    n.len = 1;
    n.sumStartsHere = 0;
    for (int s = 0; s < 6; s++) {
        if (B[s] == c) { n.to[s] = (s + 1) % 6; n.cnt[s] = (s == 5) ? 1 : 0; }
        else { n.to[s] = s; n.cnt[s] = 0; }
    }
    // Starts at the single position with state 0:
    n.sumStartsHere += n.cnt[0];
    return n;
}

Node merge(const Node &A, const Node &B_) {
    Node n;
    n.len = A.len + B_.len;
    for (int s = 0; s < 6; s++) {
        int mid = A.to[s];
        n.to[s] = B_.to[mid];
        n.cnt[s] = A.cnt[s] + B_.cnt[mid];
    }
    // Starts inside A: their contribution within A is A.sumStartsHere; then those
    // running "ongoing-bessie" states cross into B_ contributing B_.cnt[that state].
    // Need A to also store, for each starting state, how many starts inside A end in
    // each automaton state. For brevity, expand the structure to carry that.
    // (Sketch only.)
    n.sumStartsHere = A.sumStartsHere + B_.sumStartsHere;
    return n;
}

int N; vector<Node> seg;
string t;

void build(int node, int l, int r) {
    if (r - l == 1) { seg[node] = makeLeaf(t[l]); return; }
    int m = (l + r) / 2;
    build(node * 2, l, m); build(node * 2 + 1, m, r);
    seg[node] = merge(seg[node * 2], seg[node * 2 + 1]);
}

void update(int node, int l, int r, int pos, char c) {
    if (r - l == 1) { seg[node] = makeLeaf(c); return; }
    int m = (l + r) / 2;
    if (pos < m) update(node * 2, l, m, pos, c);
    else update(node * 2 + 1, m, r, pos, c);
    seg[node] = merge(seg[node * 2], seg[node * 2 + 1]);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> t; N = t.size();
    seg.assign(4 * N, {});
    build(1, 0, N);

    int U; cin >> U;
    while (U--) {
        int p; char c; cin >> p >> c; --p;
        update(1, 0, N, p, c);
        cout << seg[1].sumStartsHere << "\n";
    }
}

Pitfalls

P2 · Good Bitstrings

Official statement (cpid=1333)

Statement (paraphrase)

Define gen_string(a, b) as a length-(a+b) bitstring with a zeros and b ones generated by a specific online comparison process (the Stern-Brocot / Beatty sequence flavor). For input (A, B) compute the number of prefixes of gen_string(A, B) that are themselves "good" — i.e., equal to gen_string(a, b) for some positive integers (a, b).

Subtasks

Constraints

Key idea

The generator is equivalent to the Stern-Brocot path representation of the fraction A/B (or B/A). A prefix is "good" exactly at the end of every block in the continued- fraction (CF) expansion of A/B: each CF quotient q_k contributes q_k good prefixes (one per step within that quotient run). Total answer = sum of CF quotients of A/B, computed by Euclidean-style recursion in O(log max(A, B)). Be careful with the very first / last block (off-by-one depending on whether A, B exchange roles).

Complexity

O(log max(A, B)) per query — Euclidean recursion.

Reference C++

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

// Count "good prefixes" of gen_string(A, B). The closed-form below assumes the
// equivalence with Stern-Brocot: answer = sum of partial quotients of A/B (or B/A),
// minus a constant accounting for the trivial empty prefix not counting.

long long goodPrefixes(long long A, long long B) {
    long long ans = 0;
    bool first = true;
    while (A > 0 && B > 0) {
        if (A >= B) {
            long long q = A / B;
            // The first run is "special" — re-check off-by-one with editorial. 
            ans += first ? (q - 1) : q;
            A %= B;
        } else {
            long long q = B / A;
            ans += first ? (q - 1) : q;
            B %= A;
        }
        first = false;
    }
    return ans + 1; // +1 for the full string itself, typically counted as good
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        long long A, B; cin >> A >> B;
        cout << goodPrefixes(A, B) << "\n";
    }
}

Pitfalls

P3 · Triples of Cows

Official statement (cpid=1334)

Statement (paraphrase)

Start with a tree on N cows (N−1 friendship edges). For i = 1..N: just before cow i leaves, output the number of ordered triples (a, b, c) of distinct remaining cows such that (a, b) and (b, c) are both friendships. When cow i leaves, the remaining friends of i become pairwise friends (clique-completion), then cow i is removed.

Subtasks

Constraints

Key idea

For any graph, the number of ordered triples (a, b, c) with edges (a,b) and (b,c) and a ≠ c equals Σ_b deg(b)·(deg(b)−1). The contraction operation (turn neighborhood of v into a clique, then remove v) is exactly "vertex elimination" — and a tree under repeated elimination remains a forest if the elimination order is a perfect elimination ordering, but here the order is arbitrary (given by cow indices). Key: when we eliminate vertex v with current neighborhood N(v) of size d, the contribution Σ_b deg(b)·(deg(b)−1) changes deterministically. Maintain Σ deg(b)² (which gives the triple count via Σ d² − Σ d) under edge additions and vertex deletions using a link-cut tree or top-tree, or — exploiting the tree structure — a small-to-large merge over connected components. Editorial uses a clever observation that for a tree, deg(v) after eliminating ancestors equals "1 + #children-subtrees" and the global state factorizes.

Complexity

O(N log² N) or O(N · α) with the right link-cut data structure.

Reference C++

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

// Sketch: maintain sum of deg^2 with link-cut tree / Euler-tour over the original tree.
// Triple count = sum_b deg(b) * (deg(b) - 1) = (sum deg^2) - (sum deg)
//              = (sum deg^2) - 2 * (#edges).
// Each vertex removal: let d = current deg(v). #edges drops by d, but the contraction
// adds C(d, 2) new edges among v's neighbors, so net edge change = C(d,2) - d.
// Each neighbor's deg changes by (d - 1 - old_neighbor_count) — track with a multiset
// / Treap. Full solution is involved; here is the high-level O(N^2) sketch.

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<set<int>> adj(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].insert(v); adj[v].insert(u);
    }
    vector<long long> deg(N + 1, 0);
    for (int v = 1; v <= N; v++) deg[v] = adj[v].size();

    long long sumD = 0, sumD2 = 0;
    for (int v = 1; v <= N; v++) { sumD += deg[v]; sumD2 += deg[v] * deg[v]; }

    auto triples = [&]() { return sumD2 - sumD; };

    for (int v = 1; v <= N; v++) {
        cout << triples() << "\n";
        // Remove v: complete its neighborhood to a clique, then delete v.
        vector<int> nb(adj[v].begin(), adj[v].end());
        // Remove edges (v, x): each such edge drops deg[v] and deg[x] by 1.
        for (int x : nb) {
            sumD2 -= deg[x] * deg[x];
            deg[x]--;
            sumD2 += deg[x] * deg[x];
            sumD--;
            adj[x].erase(v);
        }
        sumD -= deg[v]; sumD2 -= deg[v] * deg[v]; deg[v] = 0;
        // Add clique edges among nb (skip if already present).
        for (size_t i = 0; i < nb.size(); i++)
            for (size_t j = i + 1; j < nb.size(); j++) {
                int a = nb[i], b = nb[j];
                if (adj[a].insert(b).second) {
                    adj[b].insert(a);
                    sumD2 -= deg[a] * deg[a]; deg[a]++; sumD2 += deg[a] * deg[a]; sumD++;
                    sumD2 -= deg[b] * deg[b]; deg[b]++; sumD2 += deg[b] * deg[b]; sumD++;
                }
            }
    }
}

Pitfalls