U USACO Prep

USACO 2015 December · Silver · all three problems

← Full December 2015 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec15results. 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 — Switching on the Lights

Statement

Bessie starts in room (1,1) of an N×N grid. All rooms are initially dark except (1,1). Each room may contain switches that, when entered, turn lights on in specific other rooms (each switch toggles a specific room on; once on it stays on). Bessie can only walk between adjacent rooms (up/down/left/right) that are currently lit. How many rooms can eventually be illuminated?

Constraints

Key idea

Iterate to a fixed point. Maintain (a) lit[r][c] and (b) the set of rooms Bessie can reach (lit rooms connected to (1,1) by lit rooms). On each pass, BFS from (1,1) through lit rooms; for every reachable room, fire all its switches (turning new rooms lit). A newly lit room becomes reachable if it's adjacent (4-neighbor) to a reachable room — so re-BFS. Loop until no new room is lit in a full pass. With N ≤ 100 and M ≤ 20,000 the total work is bounded.

Complexity target

O((N² + M) · N²) worst case; well under a second.

Reference solution (C++)

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<pair<int,int>> sw[105][105]; // switches in (r,c)
bool lit[105][105], reach[105][105];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int x, y, a, b; cin >> x >> y >> a >> b;
        sw[x][y].push_back({a, b});
    }
    lit[1][1] = true;
    int dr[] = {1,-1,0,0}, dc[] = {0,0,1,-1};
    bool changed = true;
    while (changed) {
        changed = false;
        memset(reach, 0, sizeof reach);
        queue<pair<int,int>> q; q.push({1,1}); reach[1][1] = true;
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto [a, b] : sw[r][c]) if (!lit[a][b]) { lit[a][b] = true; changed = true; }
            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr<1||nc<1||nr>N||nc>N) continue;
                if (lit[nr][nc] && !reach[nr][nc]) { reach[nr][nc] = true; q.push({nr,nc}); }
            }
        }
    }
    int ans = 0;
    for (int r = 1; r <= N; ++r) for (int c = 1; c <= N; ++c) if (lit[r][c]) ++ans;
    cout << ans << "\n";
}

Pitfalls

Problem 2 — High Card Wins

Statement

A deck has 2N cards numbered 1…2N. Elsie holds some N of them; Bessie has the rest. They play N rounds: each round Elsie reveals her next card (Elsie's order is known in advance), and Bessie simultaneously plays a card from her hand. The higher card wins the round. Bessie may permute her hand as she likes. Output the maximum number of rounds Bessie can win.

Constraints

Key idea

Classic two-pointer greedy. Sort Bessie's hand ascending. Walk through Elsie's plays in the given order; but it's easier to also sort Elsie's plays ascending and pair greedily: for each Elsie card (smallest first), assign Bessie's smallest unused card that still beats it; if none, this Elsie card is unwinnable and Bessie throws her smallest remaining card at a later round. Equivalent to the standard "horse race" problem.

Complexity target

O(N log N) sort + O(N) two-pointer.

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;
    vector<int> elsie(N);
    vector<bool> taken(2*N + 1, false);
    for (auto& e : elsie) { cin >> e; taken[e] = true; }

    vector<int> bessie;
    bessie.reserve(N);
    for (int v = 1; v <= 2*N; ++v) if (!taken[v]) bessie.push_back(v);

    sort(elsie.begin(), elsie.end());
    sort(bessie.begin(), bessie.end());

    // For each Elsie card (ascending), use Bessie's smallest card > it.
    int wins = 0, j = 0;
    for (int i = 0; i < N; ++i) {
        while (j < N && bessie[j] < elsie[i]) ++j;
        if (j < N && bessie[j] > elsie[i]) { ++wins; ++j; }
    }
    cout << wins << "\n";
}

Pitfalls

Problem 3 — Breed Counting

Statement

N cows stand in a line, each tagged with breed 1 (Holstein), 2 (Guernsey), or 3 (Jersey). Q queries of the form (a, b) ask how many cows of each breed are in positions a..b inclusive. Output three counts per query.

Constraints

Key idea

Three prefix-sum arrays, one per breed. prek[i] = number of cows of breed k in positions 1..i. Each query (a, b) returns prek[b] − prek[a−1] for k = 1,2,3 in O(1).

Complexity target

O(N + Q).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vector<array<int,4>> pre(N + 1, {0,0,0,0}); // index 0 unused for breeds

    for (int i = 1; i <= N; ++i) {
        int b; cin >> b;
        pre[i] = pre[i-1];
        pre[i][b]++;
    }
    while (Q--) {
        int a, b; cin >> a >> b;
        cout << (pre[b][1] - pre[a-1][1]) << ' '
             << (pre[b][2] - pre[a-1][2]) << ' '
             << (pre[b][3] - pre[a-1][3]) << "\n";
    }
}

Pitfalls

What Silver December 2015 was actually testing