U USACO Prep

2022 February Bronze · All three problems

← Back to Feb 2022 hub · Official results

Canonical statements live at usaco.org. Statements below are my paraphrase — open the official problem PDFs before submitting your own solution. Each problem links to the official viewer.

Problem 1 · Sleeping in Class

Official problem (cpid=1203)

Statement (paraphrased)

Elsie keeps a log a1,…,aN of how many times Bessie nods off in each class period. The only allowed modification is to merge two adjacent entries into their sum. Across at most T = 10 independent test cases, find the minimum number of merges needed so every remaining entry is the same value.

Constraints

Key idea

The final array consists of k equal values summing to S = Σa, so the only candidate target values are divisors of S. For each divisor d of S, scan left to right accumulating a prefix sum; whenever the prefix hits a multiple of d that block is closeable. If the prefix ever exceeds the next multiple, d fails. The minimum merge count for a working d is N − (S/d). Maximise S/d (i.e. minimise d) over working divisors. Edge: if every ai=0 the answer is 0.

Complexity target

O(N · σ(S)) per case. σ(106) ≤ 240, comfortable.

C++ reference solution

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

int main(){
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<ll> a(N);
        ll S = 0;
        for (auto& x : a) { cin >> x; S += x; }
        if (S == 0) { cout << 0 << '\n'; continue; }

        auto works = [&](ll d) -> bool {
            ll run = 0;
            for (ll x : a) {
                run += x;
                if (run == d) run = 0;
                else if (run > d) return false;
            }
            return true;
        };

        ll best = 0; // best S/d (== number of blocks)
        for (ll d = 1; d * d <= S; ++d) if (S % d == 0) {
            if (works(d)) best = max(best, S / d);
            if (works(S / d)) best = max(best, d);
        }
        cout << (N - best) << '\n';
    }
    return 0;
}

Pitfalls

Problem 2 · Photoshoot 2

Official problem (cpid=1204)

Statement (paraphrased)

Two permutations a, b of {1..N}. In one operation you may pick any cow and shift it to the left by any positive number of positions. Find the minimum number of operations to transform a into b.

Constraints

Key idea

Cows that don't move form a contiguous subsequence of b appearing as a subsequence of a in the same order — every other cow has to be slid left into place. So the answer is N − L, where L is the longest prefix of b matchable as a subsequence of a. Walk a left-to-right with a pointer j into b; advance j whenever a[i] == b[j]. Then L = j.

Complexity target

O(N). Single pass with two pointers.

C++ reference solution

#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), b(N);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    int j = 0;
    for (int i = 0; i < N; ++i)
        if (a[i] == b[j]) ++j;
    // j cows already aligned; the remaining N - j must each be moved left once.
    cout << (N - j) << '\n';
    return 0;
}

Pitfalls

Problem 3 · Blocks

Official problem (cpid=1205)

Statement (paraphrased)

Bessie has 4 cubes, each labelled with 6 letters. For each of N query words (length 1–4) decide whether the word can be spelled by assigning each letter to a distinct cube that contains that letter.

Constraints

Key idea

Length ≤ 4, so try all 4! = 24 cube permutations and check each. Alternatively a 4-cube bitmask: for each letter precompute the set of cubes containing it, then DFS/permute through the word picking an unused cube per letter. Either way it's effectively O(24·|word|) per query — instant.

Complexity target

O(N · 24 · 4) per test. Brute force is the intended solution.

C++ reference solution

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

int main(){
    int N; cin >> N;
    vector<string> block(4);
    for (auto& s : block) cin >> s;
    while (N--) {
        string w; cin >> w;
        int perm[4] = {0,1,2,3};
        bool ok = false;
        do {
            bool good = true;
            for (int i = 0; i < (int)w.size(); ++i) {
                if (block[perm[i]].find(w[i]) == string::npos) { good = false; break; }
            }
            if (good) { ok = true; break; }
        } while (next_permutation(perm, perm + 4));
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

Pitfalls