U USACO Prep

USACO 2016 January · Bronze · all three problems

← Full January 2016 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=jan16results. Each problem heading links to the canonical statement on usaco.org. Code is my own reference C++ — cross-check the official editorial before trusting it under contest pressure.

Problem 1 — Promotion Counting

Statement

USACO has four divisions (bronze, silver, gold, platinum). After a contest some bronze cows are promoted to silver, some silver to gold, and some gold to platinum (no demotions, no new entrants). You are given the head counts in each division before and after the contest. Output the number of promotions across each of the three boundaries (bronze→silver, silver→gold, gold→platinum).

Constraints

Key idea

Let bi, ai be the before/after sizes of division i (i = 1..4 for B/S/G/P). Let pi be the number promoted from division i to i+1. Conservation gives: a1 = b1 − p1, a2 = b2 + p1 − p2, a3 = b3 + p2 − p3, a4 = b4 + p3. Solve in order: p1 = b1 − a1, p3 = a4 − b4, p2 = (b3 − a3) + p3 = a4 − b4 + b3 − a3.

Complexity target

O(1). Six integers in, three out.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long b[4], a[4];
    for (int i = 0; i < 4; ++i) cin >> b[i] >> a[i];

    // p[i] = # promoted from level i to level i+1.
    // bronze loses p0, silver gains p0 loses p1, gold gains p1 loses p2,
    // platinum gains p2. Solve top-down and bottom-up:
    long long p0 = b[0] - a[0];          // bronze net loss
    long long p2 = a[3] - b[3];          // platinum net gain
    long long p1 = (a[3] - b[3]) + (b[2] - a[2]); // = p2 + (gold net loss)

    cout << p0 << "\n" << p1 << "\n" << p2 << "\n";
}

Pitfalls

Problem 2 — Angry Cows

Statement

N hay bales lie on a number line at integer positions xi. You launch one cow that lands on a chosen bale and detonates it at time t = 1 with blast radius 1, then radius 2 at t = 2, radius 3 at t = 3, etc. When any bale explodes it has the same growing-radius behaviour starting from time 1 (i.e. the chain reaction propagates). At each time step, every previously-detonated bale's radius grows by 1. Find the maximum number of bales that can be detonated by choosing the best landing bale.

Constraints

Key idea

With N ≤ 100, just simulate. For each starting bale s: run BFS in time steps. At time t, all bales already-exploded blast with radius t; newly engulfed bales begin at t+1 with radius 1, so they reach radius t+1 − (their start time) + 1 at the next tick. Easier: keep a set S of detonated bales and for each bale i in S, record its detonation time τi. At time t any undetonated j is added if some i ∈ S has |xj − xi| ≤ t − τi + 1. Stop when no new bale is added. Return |S|.

Complexity target

O(N³) per starting bale and O(N⁴) overall ≈ 10⁸ — fine within the limit.

Reference solution (C++)

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

int N;
vector<long long> X;

int simulate(int start) {
    // tau[i] = time at which bale i was detonated (0 if not yet).
    vector<int> tau(N, 0);
    tau[start] = 1;            // landing detonation = "time 1"
    int detonated = 1;
    for (int t = 2; ; ++t) {
        bool any = false;
        // A new bale j is hit at time t if some exploded i has |x_i - x_j| <= t - tau[i].
        vector<int> new_tau = tau;
        for (int j = 0; j < N; ++j) if (!tau[j]) {
            for (int i = 0; i < N; ++i) if (tau[i]) {
                if (llabs(X[i] - X[j]) <= (long long)(t - tau[i])) {
                    new_tau[j] = t; any = true; ++detonated; break;
                }
            }
        }
        if (!any) break;
        tau = new_tau;
    }
    return detonated;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N; X.resize(N);
    for (auto& x : X) cin >> x;
    int best = 0;
    for (int s = 0; s < N; ++s) best = max(best, simulate(s));
    cout << best << "\n";
}

Pitfalls

Problem 3 — Mowing the Field

Statement

Farmer John starts at (0,0) at time 0 and executes N movement statements. Each statement says "direction D, S steps" (D ∈ {N,E,S,W}, 1 ≤ S ≤ 10). He moves one cell per time unit, mowing each cell as he enters it. Grass cut at time t regrows at time t + x. FJ never re-cuts grass (he never enters a still-cut cell). Find the maximum integer x for which this is consistent, i.e. the largest x ≤ minimum gap between consecutive visits to the same cell. Output −1 if no cell is ever revisited.

Constraints

Key idea

Walk the path step-by-step. Maintain a hash map from cell (x,y) to the last time it was visited. On each new step, if (x,y) is in the map, compute gap = t − last; update the running min-gap; overwrite last. The answer is (min-gap − 1), because grass that regrows at time t+x is cut at exactly time t+x must still be cut, i.e. gap ≥ x+1 ⇒ x ≤ gap−1 (strictly fewer time units than the gap). If no revisit occurs, print −1.

Complexity target

O(total steps) ≈ 1000, trivially fast.

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    map<pair<int,int>, int> last;
    int x = 0, y = 0, t = 0;
    last[{0, 0}] = 0;          // mowed at time 0
    int best = INT_MAX;
    for (int k = 0; k < N; ++k) {
        char d; int s; cin >> d >> s;
        int dx = 0, dy = 0;
        if (d == 'N') dy = 1; else if (d == 'S') dy = -1;
        else if (d == 'E') dx = 1; else dx = -1;
        for (int i = 0; i < s; ++i) {
            x += dx; y += dy; ++t;
            auto it = last.find({x, y});
            if (it != last.end()) best = min(best, t - it->second);
            last[{x, y}] = t;
        }
    }
    if (best == INT_MAX) cout << -1 << "\n";
    else                 cout << best - 1 << "\n"; // grass regrows at t+x, gap > x => x <= gap-1
}

Pitfalls

What Bronze January 2016 was actually testing