U USACO Prep

2022 US Open · Bronze

← Back to 2022 US Open · Official results page

Three Bronze problems. B1 is a slick observation problem about reversing even-length prefixes of a G/H string, B2 asks for the minimum number of statements you must disregard to leave a consistent picture, and B3 is the chewiest of the three — a DAG-of-recipes feasibility check that rewards careful memoised recursion.

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.

B1 · Photoshoot

Official statement (cpid=1227)

Statement (paraphrase)

Farmer John has N cows (N even) in a line, each Guernsey ('G') or Holstein ('H'). The one allowed move is "reverse an even-length prefix" (positions 1..2k for some k). Find the minimum number of such reversals needed to maximize the number of Guernseys at even-indexed (1-indexed) positions. Output that minimum count.

Constraints

Key idea

Pair up positions (1,2), (3,4), …, (N−1,N). The optimum has a Guernsey in every pair that contains at least one G; an HH pair stays HH. So the max Guernseys-on-even-indices is just the count of pairs containing a G. The interesting question is the minimum number of even-prefix reversals to achieve that. Walk the string left to right in pairs: each time the current pair is HG (G is on the odd slot inside the pair), you must perform exactly one reversal that ends at or past this pair to swap it into GH; consecutive HG pairs can sometimes be flipped together by a single longer reversal. Count maximal runs of pairs whose orientation needs flipping.

Complexity

O(N) — one pass over the string after pairing.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; string s;
    cin >> N >> s;

    // For each pair (s[2i], s[2i+1]) classify:
    //   - "OK": already has G on the even (1-indexed) slot, i.e. s[2i+1]=='G', or pair is HH (skip).
    //   - "NEEDS_FLIP": pair has a G but it's on the odd slot (s[2i]=='G', s[2i+1]=='H').
    // A single even-prefix reversal flips the orientation of an even-length prefix of pairs,
    // so a run of consecutive NEEDS_FLIP pairs (possibly separated by HH no-ops which we can
    // treat as "either") can be fixed by one reversal if it ends at the rightmost flip-needed pair.
    // Min reversals = number of maximal NEEDS_FLIP runs after collapsing HH gaps.
    int ans = 0;
    bool inRun = false;
    for (int i = 0; i + 1 < N; i += 2) {
        char a = s[i], b = s[i + 1];
        if (a == 'G' && b == 'H') {       // needs flipping
            if (!inRun) { ans++; inRun = true; }
        } else if (a == 'H' && b == 'G') { // already good
            inRun = false;
        } else {
            // HH or GG: don't change run state (skippable)
        }
    }
    cout << ans << "\n";
}

Pitfalls

B2 · Counting Liars

Official statement (cpid=1228)

Statement (paraphrase)

Bessie hides at some integer position on a number line. N cows make statements: cow i says either "Bessie is at position ≤ p_i" (type L) or "Bessie is at position ≥ p_i" (type G). Find the minimum number of cows that must be lying so that the remaining statements are simultaneously satisfiable by some single position.

Constraints

Key idea

Equivalent: maximize the number of statements simultaneously satisfiable at some position x. The answer is N − maxSatisfiable. Because all critical x values lie at one of the p_i (or just to either side), try each p_i as the candidate hiding position and count how many statements it satisfies in O(N). The overall solution is O(N²), well under the limit at N ≤ 1000.

Complexity

O(N²) — N candidate positions × O(N) check. An O(N log N) sweep is also possible but unnecessary at this size.

Reference C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<char> type(N);
    vector<long long> pos(N);
    for (int i = 0; i < N; i++) cin >> type[i] >> pos[i];

    int bestSatisfied = 0;
    // Candidate hiding spots: each p_i is sufficient since the satisfaction function is piecewise constant.
    for (int j = 0; j < N; j++) {
        long long x = pos[j];
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (type[i] == 'L' && x <= pos[i]) cnt++;
            else if (type[i] == 'G' && x >= pos[i]) cnt++;
        }
        bestSatisfied = max(bestSatisfied, cnt);
    }
    cout << (N - bestSatisfied) << "\n";
}

Pitfalls

B3 · Alchemy

Official statement (cpid=1229)

Statement (paraphrase)

Bessie has a_i units of metal i for i=1..N. There are K ≤ N recipes; each recipe says "to make 1 unit of metal L, consume 1 unit each of M specific lower-numbered metals." At most one recipe per metal. Can Bessie produce at least 1 unit of metal N? Output "YES" or "NO".

Constraints

Key idea

Because each metal has at most one recipe, the "ways to make metal i" form a DAG (in fact a tree of dependencies). Process metals in increasing index. Let avail[i] = a_i initially. For each metal i (in order 1..N), greedily produce as many extra units as possible using metal i's recipe: the limit is the minimum availability across the recipe's ingredients. Subtract that minimum from each ingredient and add it to avail[i]. Finally, check avail[N] ≥ 1.

Greedy works because ingredient metals are strictly smaller than the produced metal, so a metal is finalized (no future demand) once its index is passed.

Complexity

O(N + total recipe size). With N ≤ 100 and a_i ≤ 10⁴, integer arithmetic is comfortable in 32-bit.

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> have(N + 1);
    for (int i = 1; i <= N; i++) cin >> have[i];

    int K; cin >> K;
    vector<vector<int>> recipe(N + 1); // recipe[L] = ingredient list (each contributes 1 unit)
    for (int k = 0; k < K; k++) {
        int L, M; cin >> L >> M;
        recipe[L].resize(M);
        for (int j = 0; j < M; j++) cin >> recipe[L][j];
    }

    // Process in increasing order of metal index. Each metal's ingredients are strictly smaller,
    // so they are already at their final available amount when we craft metal L.
    for (int L = 1; L <= N; L++) {
        if (recipe[L].empty()) continue;
        long long canMake = LLONG_MAX;
        for (int ing : recipe[L]) canMake = min(canMake, have[ing]);
        for (int ing : recipe[L]) have[ing] -= canMake;
        have[L] += canMake;
    }

    cout << (have[N] >= 1 ? "YES" : "NO") << "\n";
}

Pitfalls