U USACO Prep

2023 US Open · Silver

← Back to 2023 US Open · Official results page

Silver here is a clean trio: a sort-and-prefix-sum query problem, a bitmask superset-DP problem on strings of length up to 18, and the Silver flavor of the recurring "Pareidolia" theme (counting bessie subsequences in every substring).

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.

S1 · Milk Sum

Official statement (cpid=1326)

Statement (paraphrase)

Given N cows with milk values a_i, Farmer John unhooks them one at a time; the k-th cow unhooked contributes k · a_{σ(k)} to the total. He picks the order σ to maximize the total (so: sort ascending and multiply by 1,2,…,N). For each query (i, x), answer "if we temporarily set a_i := x, what's the maximum total?"

Constraints

Key idea

Sort a[] ascending; base answer = Σ (k+1) · a_sorted[k] (1-indexed multiplier). For a query that changes a_i to x, conceptually remove old value a_i (which sits at rank r_old) and insert x at rank r_new (lower_bound in the remaining sorted array). Use prefix sums of the sorted array: when x > a_i, all values strictly between a_i and x shift down one rank (their multiplier decreases by 1); when x < a_i, those between shift up one. The delta is a difference of prefix sums plus the placement of x.

Complexity

O((N + Q) log N) — sort once, then O(log N) per query via binary search + prefix sums.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<long long> a(N);
    for (auto &x : a) cin >> x;
    vector<long long> original = a;

    vector<long long> s = a;
    sort(s.begin(), s.end());
    // prefix sum of sorted
    vector<long long> pre(N + 1, 0);
    for (int i = 0; i < N; i++) pre[i + 1] = pre[i] + s[i];
    long long base = 0;
    for (int i = 0; i < N; i++) base += (long long)(i + 1) * s[i];

    int Q; cin >> Q;
    while (Q--) {
        int i; long long x;
        cin >> i >> x;
        --i;
        long long old = original[i];
        // Position of "old" in sorted: first occurrence found via lower_bound.
        int rOld = (int)(lower_bound(s.begin(), s.end(), old) - s.begin());
        // After removing old, where does x go? Compute in the "removed" array.
        // Position of x in sorted assuming old still present:
        int rXraw = (int)(lower_bound(s.begin(), s.end(), x) - s.begin());
        // If x <= old, removing old (at rOld) doesn't shift x's position when x < old
        // (rOld > rX). If x > old, x's true rank in the removed array is rXraw - 1.
        int rNew = (x > old) ? rXraw - 1 : rXraw;

        long long ans;
        if (rNew == rOld) {
            // x replaces old at the same rank: delta = (rOld+1) * (x - old)
            ans = base + (long long)(rOld + 1) * (x - old);
        } else if (rNew > rOld) {
            // Values originally at ranks rOld+1..rNew shift down by 1 multiplier (lose 1*v each).
            long long shifted = pre[rNew + 1] - pre[rOld + 1];
            ans = base - (long long)(rOld + 1) * old - shifted + (long long)(rNew + 1) * x;
        } else {
            // rNew < rOld: values at rNew..rOld-1 shift up by 1.
            long long shifted = pre[rOld] - pre[rNew];
            ans = base - (long long)(rOld + 1) * old + shifted + (long long)(rNew + 1) * x;
        }
        cout << ans << "\n";
    }
}

Pitfalls

S2 · Field Day

Official statement (cpid=1327)

Statement (paraphrase)

N teams, each a length-C string over {G, H} (C ≤ 18). For each team T_i, output the maximum Hamming distance between T_i and any other team T_j.

Constraints

Key idea

Map each string to a bitmask in [0, 2^C). Hamming(T_i, T_j) = popcount(T_i XOR T_j). Maximizing popcount(T_i XOR T_j) is equivalent to finding any T_j whose mask agrees with the complement ~T_i on the maximum number of bits — i.e., we want the smallest "distance" between ~T_i and the set of present masks. Do a multi-source BFS from all present masks over the hypercube graph (edges = flip one bit): dist[m] = min Hamming distance from m to any present mask. Then answer for T_i is C − dist[ ~T_i & ((1<<C)−1) ].

Complexity

O(C · 2^C + N) — BFS over the hypercube visits 2^C nodes each with C neighbors.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, N; cin >> C >> N;
    int M = 1 << C;
    vector<int> mask(N);
    vector<char> present(M, 0);
    for (int i = 0; i < N; i++) {
        string s; cin >> s;
        int m = 0;
        for (int b = 0; b < C; b++) if (s[b] == 'H') m |= (1 << b);
        mask[i] = m;
        present[m] = 1;
    }

    // BFS: dist[m] = min Hamming distance from m to any present mask.
    vector<int> dist(M, INT_MAX);
    queue<int> q;
    for (int m = 0; m < M; m++) if (present[m]) { dist[m] = 0; q.push(m); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int b = 0; b < C; b++) {
            int v = u ^ (1 << b);
            if (dist[v] > dist[u] + 1) { dist[v] = dist[u] + 1; q.push(v); }
        }
    }

    // For team i, max Hamming = C - dist[~mask[i] & (M-1)],
    // but we must also exclude the case where the closest mask IS itself when N=1
    // for that team — handled by the multi-source containing all teams.
    int full = M - 1;
    for (int i = 0; i < N; i++) {
        int target = mask[i] ^ full;
        cout << (C - dist[target]) << "\n";
    }
}

Pitfalls

S3 · Pareidolia

Official statement (cpid=1328)

Statement (paraphrase)

For a string s, define B(s) as the maximum number of non-overlapping occurrences of the word "bessie" that can be carved out of s by deleting characters (the carved copies must appear in order, each spelling b-e-s-s-i-e). Compute the sum of B(s) over every contiguous substring s of the given string.

Constraints

Key idea

Walk the string with a 6-state automaton (state s = how many letters of "bessie" we've matched modulo 6). At each position i, for every starting position L ≤ i, track the state we'd be in at position i+1 if we started a fresh "bessie" search at L. Equivalently, scan left to right and maintain, for each starting position L, the automaton state — but that's O(N²). Smart trick: when we see character c at position i, all starting positions whose current state expects c advance by 1 (and complete a bessie when state would become 6 → wrap to 0 and credit +1). Use a counter per state. On reading c, the count of "starts currently in state expecting c" all transition; add the number that completed (state 5 → 0) into a running sum, and also account for the "every substring that starts ≤ i contributes its final B value at its right endpoint."

Complexity

O(N) per character with constant-size state counter (6 states).

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();
    const string B = "bessie";

    // count[s] = number of starting positions L <= i whose current automaton state is s.
    // sum_complete = total bessies completed so far summed across all starts (this is sum
    // over starts L of B(t[L..i])), accumulated so we can add to global answer per i.
    long long count_[6] = {0,0,0,0,0,0};
    long long ans = 0;
    long long bessies_so_far = 0; // sum over L of B(t[L..i]) up to current i

    for (int i = 0; i < N; i++) {
        // A new substring starts at L = i: it begins in state 0.
        count_[0]++;
        // Now process character t[i]: for every state s where B[s] == t[i], transition s -> (s+1) mod 6.
        // States 0..5 expect B[s].
        // Build new counts.
        long long newc[6] = {0,0,0,0,0,0};
        for (int s = 0; s < 6; s++) {
            if (count_[s] == 0) continue;
            if (B[s] == t[i]) {
                int ns = (s + 1) % 6;
                newc[ns] += count_[s];
                if (s == 5) bessies_so_far += count_[s]; // each of these starts just completed +1 bessie
            } else {
                newc[s] += count_[s];
            }
        }
        for (int s = 0; s < 6; s++) count_[s] = newc[s];
        // After processing position i, every substring ending at i contributes its current B value.
        ans += bessies_so_far;
    }
    cout << ans << "\n";
}

Pitfalls