U USACO Prep

2023 February Bronze · All three problems

← Back to Feb 2023 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 · Hungry Cow

Official problem (cpid=1299)

Statement (paraphrased)

Bessie eats exactly one haybale every day on which she has at least one in storage; otherwise she eats nothing that day. Farmer John makes N deliveries: on day di he drops off bi haybales in the morning before dinner. Output the total number of haybales Bessie consumes during days 1..T.

Constraints

Key idea

Walk the deliveries left-to-right tracking cur, the day Bessie will eat next, plus a running stockpile. Between delivery i and i+1 Bessie eats min(stock, d_{i+1} − cur) haybales — the rest carries forward. After the last delivery cap the run by T. T is huge but the simulation is O(N) because we collapse each "eating run" in one arithmetic step instead of iterating day-by-day.

Complexity target

O(N). Day count is virtual — never loop over T.

C++ reference solution

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; ll T;
    cin >> N >> T;
    vector<ll> d(N), b(N);
    for (int i = 0; i < N; ++i) cin >> d[i] >> b[i];

    ll eaten = 0;     // total haybales consumed
    ll stock = 0;     // current stockpile
    ll cur   = 1;     // next day Bessie will try to eat
    for (int i = 0; i < N; ++i) {
        // eat from cur up to min(d[i]-1, T)
        ll until = min(d[i] - 1, T);
        if (until >= cur) {
            ll take = min(stock, until - cur + 1);
            eaten += take;
            stock -= take;
            cur    = until + 1;
        }
        if (d[i] > T) break;
        stock += b[i];
        cur = max(cur, d[i]);
    }
    // tail from cur..T
    if (cur <= T) {
        ll take = min(stock, T - cur + 1);
        eaten += take;
    }
    cout << eaten << '\n';
    return 0;
}

Pitfalls

Problem 2 · Stamp Grid

Official problem (cpid=1300)

Statement (paraphrased)

Given a target N×N grid of black/white cells and a K×K stamp also coloured B/W, decide whether you can reproduce the target by repeatedly placing the stamp (in any of its four rotations) onto a blank N×N canvas. Each placement paints all black-cells of the stamp onto the canvas; cells once painted stay painted. White stamp cells leave the canvas unchanged.

Constraints

Key idea

Try every rotation of the stamp and every top-left placement (N−K+1)2. A placement is "legal" if no black stamp-cell sits on a target-white cell — otherwise it would over-paint a cell that must stay white. Greedily apply every legal placement; you can apply each one at most once because cells only flip W→B. Then check whether the resulting canvas equals the target.

Complexity target

O(4 · N2 · K2) per test case — comfortable with N, K ≤ 20.

C++ reference solution

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

int N, K;
vector<string> target, canvas;

vector<string> rot(const vector<string>& s){
    int n = s.size();
    vector<string> r(n, string(n, '.'));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            r[j][n-1-i] = s[i][j];
    return r;
}

bool legal(const vector<string>& st, int r, int c){
    for (int i = 0; i < K; ++i)
        for (int j = 0; j < K; ++j)
            if (st[i][j] == '*' && target[r+i][c+j] != '*') return false;
    return true;
}
void apply(const vector<string>& st, int r, int c){
    for (int i = 0; i < K; ++i)
        for (int j = 0; j < K; ++j)
            if (st[i][j] == '*') canvas[r+i][c+j] = '*';
}

int main(){
    int T; cin >> T;
    while (T--){
        cin >> N >> K;
        target.assign(N, "");
        for (auto& s : target) cin >> s;
        vector<string> st(K, ""); for (auto& s : st) cin >> s;
        canvas.assign(N, string(N, '.'));
        for (int rot_i = 0; rot_i < 4; ++rot_i){
            for (int r = 0; r + K <= N; ++r)
                for (int c = 0; c + K <= N; ++c)
                    if (legal(st, r, c)) apply(st, r, c);
            st = rot(st);
        }
        cout << (canvas == target ? "YES" : "NO") << '\n';
    }
}

Pitfalls

Problem 3 · Watching Mooloo

Official problem (cpid=1301)

Statement (paraphrased)

Bessie wants to watch on N specific days d1 < … < dN. A subscription covering d consecutive days costs d + K moonies; she may buy as many disjoint blocks as she likes. Minimise total cost so every viewing day is covered.

Constraints

Key idea

Sort the days (already sorted in input) and consider the gap g = di+1 − di. Extending the current subscription across the gap costs g additional days. Starting a fresh subscription costs 1 + K (1 for the new day, K for the new subscription overhead). So merge while g ≤ K, else split. Final cost = N + K·(blocks) + Σ (kept gaps).

Complexity target

O(N) after the implicit sort. One linear pass.

C++ reference solution

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; ll K;
    cin >> N >> K;
    vector<ll> d(N);
    for (auto& x : d) cin >> x;
    ll cost = 1 + K;            // first block: 1 day + K
    for (int i = 1; i < N; ++i){
        ll g = d[i] - d[i-1];
        if (g <= K) cost += g;  // extend
        else        cost += 1 + K; // new block
    }
    cout << cost << '\n';
    return 0;
}

Pitfalls