U USACO Prep

2024 January Bronze — three problems

← 2024 January contest index · Official results page

Bronze is ad-hoc and simulation: the algorithmic content lives in one observation each, and the rest is clean code.

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 straight to usaco.org.

Problem 1 · Majority Opinion

Official statement (cpid=1371)

Statement (paraphrased)

There are N cows in a row, each preferring one of K hay types. Farmer John can call a contiguous focus group [l, r]; if some hay type is preferred by strictly more than half the cows in that group, every cow in [l, r] switches to that hay type. Output every hay type that can end up as the unanimous preference of all N cows after some sequence of focus groups, in sorted order, or "-1" if none exists.

Constraints

Key idea

A hay type h is achievable iff some contiguous run contains at least two adjacent positions of h inside a window where h is already a strict majority. The cleanest characterisation: h can win iff there exist three positions i < j < k of hay h with j ≤ i + 2, i.e. two of the three closest occurrences of h are within distance 2. Then that triple seeds a small majority window, which you can grow outward repeatedly.

Implementation: for each hay type, scan its occurrence list and check whether any three consecutive occurrences fit in a window of length ≤ 5. Equivalently, two consecutive occurrences within distance 2 are enough to seed it.

Complexity

O(N) per test case after bucketing by hay type.

C++ reference

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        vector<int> a(N);
        for (auto& x : a) scanf("%d", &x);

        // group indices by hay type
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < N; i++) pos[a[i]].push_back(i);

        vector<int> good;
        for (auto& [h, v] : pos) {
            bool ok = false;
            for (int i = 0; i + 2 < (int)v.size(); i++)
                if (v[i + 2] - v[i] <= 4) { ok = true; break; }   // 3 occurrences in 5 cells
            for (int i = 0; i + 1 < (int)v.size() && !ok; i++)
                if (v[i + 1] - v[i] <= 2) ok = true;               // 2 adjacent within 2
            if (ok) good.push_back(h);
        }
        if (good.empty()) { puts("-1"); continue; }
        sort(good.begin(), good.end());
        for (int x : good) printf("%d\n", x);
    }
}

Pitfalls

Problem 2 · Cannonball

Official statement (cpid=1372)

Statement (paraphrased)

Bessie starts at position S on a number line with power P = 1, moving right. Some cells are jump pads with a value v: when Bessie lands on one, her power is set to max(P, v) and her direction reverses. Other cells are targets with a strength s: if Bessie lands on one with P ≥ s, the target breaks (becomes empty) and she keeps moving in her current direction; otherwise the target stops her. Each step she moves P cells in her current direction. Count the total number of targets broken before she exits the number line or stops on an unbreakable target.

Constraints

Key idea

Pure simulation. The only subtlety: Bessie's power is monotonically non-decreasing (jump pads only raise it), and each landing either ends the process or strictly progresses simulation, so total steps are bounded by O(N) hop-events when implemented as "jump in direction d until you hit a non-empty cell." A naive cell-by-cell loop is O(N · P) and TLEs at the upper bound.

Maintain two ordered sets (e.g. std::set<int>) of "occupied" positions: one indexed left-to-right, one right-to-left. At each step, find the next occupied cell in the current direction; if its position has the same parity-step alignment Bessie would land on (i.e. distance divisible by P), interact with it, else she flies past and exits.

Complexity

O(N log N) using std::set lookups; each occupied cell is visited O(1) times.

C++ reference

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

int main() {
    int N, S; scanf("%d %d", &N, &S);
    // cell[i] = 0 empty, >0 jump pad value, <0 -strength target
    vector<long long> cell(N + 2, 0);
    for (int i = 1; i <= N; i++) scanf("%lld", &cell[i]);   // [verify] input format cpid=1372

    set<int> occ;
    for (int i = 1; i <= N; i++) if (cell[i] != 0) occ.insert(i);

    long long P = 1;
    int dir = +1, pos = S, broken = 0;
    while (true) {
        auto it = (dir > 0) ? occ.lower_bound(pos + 1) : occ.upper_bound(pos - 1);
        if (dir > 0 ? it == occ.end() : it == occ.begin()) break;
        if (dir < 0) --it;
        int np = *it;
        if (abs(np - pos) % P != 0) break;     // she steps over it, off the line
        pos = np;
        long long v = cell[np];
        if (v > 0) { P = max(P, v); dir = -dir; }      // jump pad
        else if (-v <= P) { broken++; occ.erase(it); cell[np] = 0; }  // target breaks
        else break;                                     // unbreakable
    }
    printf("%d\n", broken);
}

Pitfalls

Problem 3 · Balancing Bacteria

Official statement (cpid=1373)

Statement (paraphrased)

Patches 1..N have bacteria levels a[1..N]. A single spray applied at the rightmost patch with power L changes a[N] by ±L, a[N−1] by ±(L−1), ..., a[N−L+1] by ±1. (Sign chosen per spray.) Find the minimum total number of sprays so every a[i] becomes 0. The answer is guaranteed ≤ 109.

Constraints

Key idea

Take two differences. The first difference di = ai − ai−1 is incremented by ±1 per spray for every position covered. The second difference ei = di − di−1 changes by ±1 only at the left boundary of the spray's range. So sweeping left-to-right while tracking the cumulative effect of past sprays, the required net number of sprays at each boundary is forced. Sum the absolute values of those forced counts.

Complexity

O(N), one linear pass over second differences.

C++ reference

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

int main() {
    int N; scanf("%d", &N);
    vector<long long> a(N + 1, 0);
    for (int i = 1; i <= N; i++) scanf("%lld", &a[i]);

    // We want every a[i] = 0. A spray with power L at the right end adds an
    // arithmetic progression ending at +/-L on position N, slope 1 going left.
    // Equivalently, after two prefix-difference transforms each spray becomes a
    // single point change at position N-L+1. Process from right to left.
    long long ans = 0, slope = 0, val = 0;
    for (int i = N; i >= 1; i--) {
        val += a[i] + slope;       // current bacteria after past sprays' tails
        // [verify] sign/index convention against editorial cpid=1373
        long long k = -val;        // sprays starting at this left boundary
        ans += llabs(k);
        slope += k;                // each such spray adds slope 1 to cells further left
        val = 0;
    }
    printf("%lld\n", ans);
}

Pitfalls