USACO 2018 December · Silver · all three problems

← Full December 2018 set · Official results

Source. Statements and constraints below are paraphrased from usaco.org/index.php?page=dec18results. 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 — Convention

Statement

N cows arrive at an airport at times t_i. M buses, each carrying up to C cows, must pick all of them up. A bus departs as soon as it is full or the schedule allows; its departure time is the arrival time of its last-boarding cow. A cow's "wait" is (bus departure time − her arrival time). Minimize the maximum wait across all cows. Output that minimum max wait.

Constraints

1 ≤ N, M ≤ 10⁵, 1 ≤ C ≤ N, M·C ≥ N.
0 ≤ t_i ≤ 10⁹.
Time limit: 2s.

Key idea

Binary search the answer W. Greedy check: sort arrivals. Walk left-to-right; when the next cow's arrival exceeds the current group's first cow's arrival + W, or the group already has C cows, start a new bus. Feasible iff total buses ≤ M.

Complexity target

O(N log N + N · log(max t)) — sort once, then ~30 binary-search iterations of an O(N) feasibility check.

Reference solution (C++)

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

int N, M, C;
vector<ll> t;

bool feasible(ll W) {
    int buses = 0;
    int i = 0;
    while (i < N) {
        ll first = t[i];
        int count = 0;
        // Pack cows whose arrival is <= first + W, up to C per bus.
        while (i < N && count < C && t[i] <= first + W) { ++i; ++count; }
        ++buses;
        if (buses > M) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M >> C;
    t.resize(N);
    for (auto& x : t) cin >> x;
    sort(t.begin(), t.end());

    ll lo = 0, hi = 1e9;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (feasible(mid)) hi = mid;
        else               lo = mid + 1;
    }
    cout << lo << "\n";
}

Pitfalls

Sort first. Inputs are not given in arrival order.
Greedy direction. When you start a bus at time t[i], it departs at the C-th boarder's time — bounded above by t[i] + W. So first arrival anchors the window, not the last.
Don't binary-search bus assignments. Binary search the answer W; checking is the easy direction.
Hi bound. Max wait can be t_max − t_min ≤ 10⁹; 64-bit is safe.

Problem 2 — Convention II

Statement

N cows visit a one-cow-at-a-time pasture. Cow i (listed in seniority order, so cow 1 is most senior) arrives at time a_i and wants to eat for t_i. When the pasture frees up, the most-senior waiting cow eats next; if no one is waiting, the next-arriving cow eats immediately on arrival. Output the maximum waiting time experienced by any cow (begin − arrival).

Constraints

1 ≤ N ≤ 10⁵.
1 ≤ a_i ≤ 10⁹, 1 ≤ t_i ≤ 10⁴.
Cows are listed in seniority order; arrival times need not be sorted.
Time limit: 2s.

Key idea

Event-driven simulation. Sort cows by arrival; maintain a min-heap of waiting cows keyed by seniority (original index). At each step the pasture frees at time F: admit all cows with a_i ≤ F into the heap, then pop the top. If the heap is empty, jump F forward to the next arrival.

Complexity target

O(N log N).

Reference solution (C++)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<ll> a(N), t(N);
    for (int i = 0; i < N; ++i) cin >> a[i] >> t[i];

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y){ return a[x] < a[y]; });

    priority_queue<int, vector<int>, greater<int>> pq;  // seniority index, smaller = senior
    ll now = 0, ans = 0;
    int p = 0;
    while (p < N || !pq.empty()) {
        if (pq.empty()) {
            int i = order[p++];
            now = a[i] + t[i];      // she starts immediately, no wait
            continue;
        }
        // admit everyone arrived by 'now'
        while (p < N && a[order[p]] <= now) pq.push(order[p++]);
        if (pq.empty()) {
            int i = order[p++];
            now = a[i] + t[i];
            continue;
        }
        int i = pq.top(); pq.pop();
        ans = max(ans, now - a[i]);
        now += t[i];
    }
    cout << ans << "\n";
}

Pitfalls

Idle pasture. If the heap empties before all cows arrived, fast-forward now to the next arrival — that cow has 0 wait.
Seniority = input index. Sorting by arrival destroys input order; carry the original index into the heap.
Off-by-one on "free at time now". A cow whose arrival equals now is eligible to be admitted before the next pick.
64-bit times. a_i + Σ t_i can exceed 10⁹.

Problem 3 — Mooyo Mooyo

Statement

An N × 10 grid of digits (0 = empty, 1–9 = colors). Repeat: find every connected (4-neighbor) region of one nonzero color whose size ≥ K and erase them all simultaneously (set to 0); then apply gravity so nonzero cells fall to the bottom of each column. Stop when no eligible region remains. Output the final grid.

Constraints

1 ≤ N ≤ 100, grid width = 10.
1 ≤ K ≤ 10·N.
Cells are characters '0'–'9'.
Time limit: 2s.

Key idea

Cascade loop. Each iteration: BFS/DFS flood-fill from every unvisited nonzero cell, collect its region; if size ≥ K, mark every cell for deletion. After scanning, set marked cells to 0 and gravity: for each column, gather nonzero values bottom-up. Repeat until a pass deletes nothing.

Complexity target

O((NW)² ) worst-case; with N ≤ 100, W = 10, the grid is 1000 cells — easily fast enough.

Reference solution (C++)

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

int N, K;
vector<string> g;
const int W = 10;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

bool step() {
    vector<vector<int>> vis(N, vector<int>(W, 0));
    vector<pair<int,int>> toErase;
    bool changed = false;
    for (int i = 0; i < N; ++i) for (int j = 0; j < W; ++j) {
        if (vis[i][j] || g[i][j] == '0') continue;
        char c = g[i][j];
        vector<pair<int,int>> region;
        queue<pair<int,int>> q; q.push({i, j}); vis[i][j] = 1;
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            region.push_back({x, y});
            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx<0||nx>=N||ny<0||ny>=W) continue;
                if (vis[nx][ny] || g[nx][ny] != c) continue;
                vis[nx][ny] = 1; q.push({nx, ny});
            }
        }
        if ((int)region.size() >= K)
            for (auto& p : region) toErase.push_back(p);
    }
    for (auto& p : toErase) { g[p.first][p.second] = '0'; changed = true; }
    // Gravity per column.
    for (int j = 0; j < W; ++j) {
        string col;
        for (int i = 0; i < N; ++i) if (g[i][j] != '0') col += g[i][j];
        for (int i = 0; i < N; ++i) {
            int from = i - (N - (int)col.size());
            g[i][j] = (from < 0) ? '0' : col[from];
        }
    }
    return changed;
}

int main() {
    cin >> N >> K;
    g.resize(N);
    for (auto& r : g) cin >> r;
    while (step()) {}
    for (auto& r : g) cout << r << "\n";
}

Pitfalls

Simultaneous deletion. Collect every region first, then erase; don't delete mid-scan or you'll miscount sizes.
Gravity after deletion, not during. Drop once per cascade step.
4-connectivity only. Diagonals don't connect colors.
Empty regions ('0'). Skip zeros in the flood fill — they're empty, not "color zero".

What Silver December 2018 was actually testing

P1 — binary search on the answer. The canonical "minimize the maximum" pattern with a linear feasibility check.
P2 — event-driven priority-queue simulation. Two passes of "advance time" — one with the queue non-empty, one when idle.
P3 — grid BFS plus a tidy gravity routine. Mooyo is mostly an implementation discipline check.