U USACO Prep

2023 January Bronze — three problems

← 2023 January contest index · Official results page

Bronze 2023-Jan is two ad-hoc / counting problems and one greedy. The dominant skill is reading carefully and indexing without off-by-ones.

Read the official PDF first. Paraphrases below are my own; if my wording and the PDF disagree, the PDF wins. All three problem links go to usaco.org.

Problem 1 · Leaders

Official statement (cpid=1281)

Statement (paraphrased)

There are N cows in a row, each cow has a breed (G for Guernsey, H for Holstein) and points to another cow of the same breed (or to itself). A cow x is a leader of its breed if every cow of the same breed lies in the range [x, p(x)] where p(x) is the cow x points to, and x is the leftmost cow of its breed in that range. Count ordered pairs (a, b) of leaders of different breeds such that the intervals [a, p(a)] and [b, p(b)] touch — i.e. one is the leftmost cow of its breed and the other lies in the first's interval.

Constraints

Key idea

There are at most one G-leader and one H-leader, because a leader's interval must cover every cow of its breed and start at the leftmost such cow. So compute (a) the leftmost G and the leftmost H, (b) check whether the leftmost-of-breed-X is a valid leader (its pointer reaches the last cow of breed X and that cow points back inside its interval). Then test the two pairing cases.

Concretely: find leftmost G index gL and rightmost G index gR; G has a leader iff cow[gL].p ≥ gR and cow at position cow[gL].p has breed G. Same for H. Count the at-most-two valid leader pairs by the touching rule.

Complexity

O(N) per test case.

C++ reference

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

int main() {
    int N; scanf("%d", &N);
    string s; s.resize(N);
    for (int i = 0; i < N; i++) { char c; scanf(" %c", &c); s[i] = c; }
    vector<int> p(N);
    for (int i = 0; i < N; i++) { scanf("%d", &p[i]); --p[i]; }

    auto findLeader = [&](char breed) -> int {
        int lo = -1, hi = -1;
        for (int i = 0; i < N; i++) if (s[i] == breed) { if (lo < 0) lo = i; hi = i; }
        if (lo < 0) return -1;
        // leader candidate is lo; needs p[lo] >= hi and s[p[lo]] == breed
        if (p[lo] >= hi && s[p[lo]] == breed) return lo;
        return -1;
    };

    int lg = findLeader('G'), lh = findLeader('H');
    int ans = 0;
    // pair (G-leader, H-leader): H must be the leftmost H AND lie in G's interval, or vice versa
    auto check = [&](int a, int b) {
        if (a < 0 || b < 0) return false;
        return (a <= b && b <= p[a]) || (b <= a && a <= p[b]);
    };
    if (check(lg, lh)) ans++;
    printf("%d\n", ans);   // [verify] exact "pair" definition against editorial cpid=1281
}

Pitfalls

Problem 2 · Air Cownditioning II

Official statement (cpid=1282)

Statement (paraphrased)

N stalls each have a required cooling demand di. M air conditioners are available; the i-th AC covers stalls [si, ti] adding pi cooling to each stall in its range, and costs mi dollars to buy. Choose a subset of ACs so every stall's total cooling is at least di, minimising total cost. Bronze: M ≤ 10, so 2M subset enumeration is fine.

Constraints

Key idea

Enumerate all 2M ≤ 1024 subsets. For each subset, sum cooling per stall (cheap: 100·10 work) and check every stall is satisfied. Track the minimum cost.

Complexity

O(2M · N · M) ≈ 106.

C++ reference

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

int main() {
    int N, M; scanf("%d %d", &N, &M);
    vector<int> d(N + 2, 0);
    for (int i = 1; i <= N; i++) scanf("%d", &d[i]);
    vector<int> s(M), t(M), p(M), m(M);
    for (int i = 0; i < M; i++) scanf("%d %d %d %d", &s[i], &t[i], &p[i], &m[i]);

    int best = INT_MAX;
    for (int mask = 0; mask < (1 << M); mask++) {
        vector<long long> cool(N + 2, 0);
        long long cost = 0;
        for (int i = 0; i < M; i++) if (mask >> i & 1) {
            cost += m[i];
            for (int j = s[i]; j <= t[i]; j++) cool[j] += p[i];
        }
        bool ok = true;
        for (int j = 1; j <= N; j++) if (cool[j] < d[j]) { ok = false; break; }
        if (ok && cost < best) best = (int)cost;
    }
    printf("%d\n", best);
}

Pitfalls

Problem 3 · Moo Operations

Official statement (cpid=1283)

Statement (paraphrased)

Given a string S over {M, O, F} (or similar small alphabet), the allowed operations are: change one character (cost 1), or delete a character from either end (cost 1). Find the minimum number of operations to turn S into a string of the form MOOMOO...MOO (some number of MOO repetitions, possibly zero). Multiple test cases per input.

Constraints

Key idea

The target length must be a multiple of 3 and at most |S| (since we can only delete, never insert). For each candidate target length 3k from 0 to ⌊|S|/3⌋·3, and each starting position i in S of length 3k, count mismatches with the pattern "MOOMOO..."; the cost is (|S| − 3k) deletions + mismatch count. Take the minimum.

Complexity

O(|S|2) per test case — fine for |S| ≤ 100.

C++ reference

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char buf[256]; scanf("%s", buf);
        string s = buf;
        int n = (int)s.size();
        const string pat = "MOO";
        int best = n;   // worst case: delete everything (target = empty string)
        for (int k = 3; k <= n; k += 3) {
            for (int i = 0; i + k <= n; i++) {
                int mismatch = 0;
                for (int j = 0; j < k; j++)
                    if (s[i + j] != pat[j % 3]) mismatch++;
                int cost = (n - k) + mismatch;
                best = min(best, cost);
            }
        }
        printf("%d\n", best);
    }
}

Pitfalls