U USACO Prep

2022 US Open · Silver

← Back to 2022 US Open · Official results page

Three Silver problems. S1 is a functional-graph greedy where you pick which cows get their visit, S2 is a clever observation that a Q-subset query depends only on each pair of letters separately, and S3 is a beautiful parity / XOR invariant disguised as a string-rewriting puzzle.

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

Official statement (cpid=1230)

Statement (paraphrase)

Each of N cows has a target a_i ≠ i it wants to visit, and a "moo value" v_i it produces only if it visits before its target has left. You choose the order in which cows leave. Maximize the sum of v_i over cows whose target hadn't yet departed when they themselves departed.

Constraints

Key idea

Build the functional graph with edge i → a_i. In any ordering you can collect every cow's value except in each cycle of the graph at least one cow must depart last and therefore loses its value. (Tree-tails can always be processed leaves-first and collect everything.) So the answer is sum(v_i) − Σ over cycles of min(v_i in cycle). Detect cycles by following the functional graph; each node has out-degree 1, so cycles are easy to extract with the standard "two-color" walk.

Complexity

O(N) — one linear scan finds all cycles in a functional graph.

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 + 1);
    vector<long long> v(N + 1);
    long long total = 0;
    for (int i = 1; i <= N; i++) { cin >> a[i] >> v[i]; total += v[i]; }

    // Find all cycles of i -> a[i].
    vector<int> state(N + 1, 0); // 0 unseen, 1 on current path, 2 finished
    vector<int> order; // current DFS stack as list
    long long penalty = 0;
    for (int s = 1; s <= N; s++) {
        if (state[s]) continue;
        int u = s; vector<int> path;
        while (state[u] == 0) { state[u] = 1; path.push_back(u); u = a[u]; }
        if (state[u] == 1) {
            // Cycle starts at u within path.
            long long mn = LLONG_MAX;
            int k = (int)path.size() - 1;
            while (k >= 0 && path[k] != u) { mn = min(mn, v[path[k]]); k--; }
            mn = min(mn, v[u]);
            penalty += mn;
        }
        for (int x : path) state[x] = 2;
    }
    cout << (total - penalty) << "\n";
}

Pitfalls

S2 · Subset Equality

Official statement (cpid=1231)

Statement (paraphrase)

Given two strings s, t over the alphabet {a..r} (18 letters). For each query, a subset Q of letters is given. Output 'Y' if s and t become identical after deleting every character not in Q (preserving order), else 'N'.

Constraints

Key idea

Two filtered strings are equal iff for every pair of letters (x, y) in the query, the order pattern of those two letters in s matches that in t. Concretely: precompute, for each unordered pair {x, y}, the boolean "s and t agree when restricted to just letters x and y" — only 18·19/2 = 171 pairs, each O(N) to test. Also store the 18 single-letter counts. A query Q passes iff every singleton in Q has matching count AND every pair {x, y} ⊆ Q has the precomputed agree flag set. Each query is O(|Q|²) ≤ 18² = 324.

Complexity

Preprocess O(18² · N) ≈ 3.2·10⁷. Each query O(18²). Total comfortably under 1 s.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t; cin >> s >> t;
    const int A = 18;

    // Counts of each letter must agree.
    array<int, A> cs{}, ct{};
    for (char c : s) cs[c - 'a']++;
    for (char c : t) ct[c - 'a']++;

    // For each pair (x, y), check whether filtering to {x,y} yields equal strings.
    auto filterTo = [&](const string& z, int x, int y) {
        string r; r.reserve(z.size());
        for (char c : z) if (c - 'a' == x || c - 'a' == y) r.push_back(c);
        return r;
    };
    vector<vector<char>> ok(A, vector<char>(A, 0));
    for (int x = 0; x < A; x++)
        for (int y = x; y < A; y++)
            ok[x][y] = ok[y][x] = (filterTo(s, x, y) == filterTo(t, x, y));

    int Q; cin >> Q;
    string out; out.reserve(Q);
    while (Q--) {
        string q; cin >> q;
        bool good = true;
        for (char c : q) if (cs[c - 'a'] != ct[c - 'a']) { good = false; break; }
        if (good) {
            for (int i = 0; i < (int)q.size() && good; i++)
                for (int j = i + 1; j < (int)q.size() && good; j++)
                    if (!ok[q[i] - 'a'][q[j] - 'a']) good = false;
        }
        out.push_back(good ? 'Y' : 'N');
        out.push_back('\n');
    }
    cout << out;
}

Pitfalls

S3 · COW Operations

Official statement (cpid=1232)

Statement (paraphrase)

A string over {C, O, W} supports two operations: (a) delete two adjacent equal letters or (b) replace a single letter by the two others (in either order). For each query (l, r), output 'Y' if the substring s[l..r] can be reduced to a single 'C', else 'N'.

Constraints

Key idea

Both operations preserve the parities (count C mod 2, count O mod 2, count W mod 2) up to a flip: deletion drops two equal letters (parities unchanged), and the replacement of one letter by the other two flips all three parities together. So the multiset parity vector (cnt_C, cnt_O, cnt_W) mod 2 is invariant up to simultaneously flipping all three bits. Equivalently the differences (cnt_C − cnt_O) mod 2 and (cnt_C − cnt_W) mod 2 are exact invariants. The single 'C' target has (1, 0, 0): differences (1, 1). So query (l, r) is 'Y' iff (cnt_C − cnt_O) mod 2 = 1 AND (cnt_C − cnt_W) mod 2 = 1 over s[l..r]. Prefix-sum the three counts and answer each query in O(1).

Sufficiency (any string with the right invariant reduces to C) follows by an induction that uses the replace operation to merge two non-equal adjacent letters into a single new letter and the delete operation to peel matched pairs.

Complexity

O(|s| + Q) after prefix sums.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; int Q; cin >> s >> Q;
    int N = s.size();
    vector<array<int, 3>> pre(N + 1, {0, 0, 0});
    auto idx = [](char c) { return c == 'C' ? 0 : c == 'O' ? 1 : 2; };
    for (int i = 0; i < N; i++) {
        pre[i + 1] = pre[i];
        pre[i + 1][idx(s[i])]++;
    }
    string out; out.reserve(Q * 2);
    while (Q--) {
        int l, r; cin >> l >> r;          // 1-indexed inclusive
        int c = pre[r][0] - pre[l - 1][0];
        int o = pre[r][1] - pre[l - 1][1];
        int w = pre[r][2] - pre[l - 1][2];
        bool ok = (((c - o) % 2 + 2) % 2 == 1) && (((c - w) % 2 + 2) % 2 == 1);
        out.push_back(ok ? 'Y' : 'N');
        out.push_back('\n');
    }
    cout << out;
}

Pitfalls