U USACO Prep

USACO 2016 US Open · Bronze · all three problems

← Full 2016 US Open set · Official results

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

Statement

Bessie has N diamonds with integer sizes s1, …, sN. She wants to display diamonds in a single case but only if the largest and smallest displayed diamond differ by at most K in size. Choose a subset of the diamonds satisfying this rule and output the maximum size of that subset.

Constraints

Key idea

Sort sizes ascending. The optimal subset is then a contiguous range in the sorted array (any non-contiguous skip can only reduce the count without helping the spread). Use a two-pointer / sliding window: for each left index i, advance j while s[j] − s[i] ≤ K, and track max(j − i + 1).

Complexity target

O(N log N) for the sort, O(N) for the sweep. With N ≤ 1000 even O(N2) passes easily.

Reference solution (C++)

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

int main() {
    int N; long long K;
    cin >> N >> K;
    vector<long long> s(N);
    for (auto& x : s) cin >> x;
    sort(s.begin(), s.end());

    int best = 0, j = 0;
    for (int i = 0; i < N; ++i) {
        if (j < i) j = i;
        while (j < N && s[j] - s[i] <= K) ++j;
        best = max(best, j - i);
    }
    cout << best << "\n";
}

Pitfalls

Problem 2 — Bull in a China Shop

Statement

A bull starts at a known cell in a small N×N grid. In one "move" the bull walks in any of the 8 compass directions (N, NE, E, SE, S, SW, W, NW) some positive number of cells, stopping whenever it likes (i.e. each move is a queen-like ray of any positive length within the grid). After exactly K moves, how many distinct cells could the bull occupy?

Constraints

Key idea

Brute-force BFS / DFS where the state is (row, col, moves used). From each cell, enumerate the 8 directions and every positive step length that stays on the grid. Track visited (r, c, k); at the end, count cells (r, c) that were ever visited with exactly k = K. Because N ≤ 10 and K is tiny, the state space is ≤ 10×10×K and the per-state branching is bounded by 8×9 = 72.

Complexity target

O(N2 · K · 8N) ≤ a few thousand operations.

Reference solution (C++)

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

int N, K;
int dr[8] = {-1,-1,0,1,1, 1, 0,-1};
int dc[8] = { 0, 1,1,1,0,-1,-1,-1};
bool vis[12][12][10];

void dfs(int r, int c, int k) {
    if (vis[r][c][k]) return;
    vis[r][c][k] = true;
    if (k == K) return;
    for (int d = 0; d < 8; ++d)
        for (int step = 1; ; ++step) {
            int nr = r + dr[d]*step, nc = c + dc[d]*step;
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) break;
            dfs(nr, nc, k + 1);
        }
}

int main() {
    int sr, sc;
    cin >> N >> K >> sr >> sc;
    dfs(sr, sc, 0);
    int ans = 0;
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            if (vis[r][c][K]) ++ans;
    cout << ans << "\n";
}

Pitfalls

Problem 3 — Field Reduction

Statement

FJ has N cows at integer positions (xi, yi). The "field" is the smallest axis-aligned bounding rectangle that contains all cows; its area is (max x − min x) · (max y − min y). Remove exactly 3 cows so the bounding-box area of the remaining N−3 cows is minimized. Output the minimum area.

Constraints

Key idea

The minimum bounding box after removal only depends on the four extremes — the cows with min x, max x, min y, max y. To reduce the box, one of the removed cows must be one of these four "extreme" cows. So the candidate set of removable cows is at most the 4 cows holding the four extremes — plus, to be safe, a few more cows holding the next-best extremes (top-3 smallest x, top-3 largest x, top-3 smallest y, top-3 largest y — at most 12 distinct cows). Try every 3-subset of those ≤ 12 candidates; for each, recompute the bounding box on the remaining cows and take the minimum.

Complexity target

O(N) to pick candidate sets, O(C(12,3) · N) ≤ 220 N to evaluate. About 107.

Reference solution (C++)

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

int main() {
    int N; cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    auto topK = [&](auto cmp) {
        vector<int> idx(N); iota(idx.begin(), idx.end(), 0);
        partial_sort(idx.begin(), idx.begin()+3, idx.end(), cmp);
        return vector<int>(idx.begin(), idx.begin()+3);
    };
    set<int> cand;
    for (int i : topK([&](int a, int b){ return X[a] < X[b]; })) cand.insert(i);
    for (int i : topK([&](int a, int b){ return X[a] > X[b]; })) cand.insert(i);
    for (int i : topK([&](int a, int b){ return Y[a] < Y[b]; })) cand.insert(i);
    for (int i : topK([&](int a, int b){ return Y[a] > Y[b]; })) cand.insert(i);

    vector<int> c(cand.begin(), cand.end());
    long long ans = LLONG_MAX;
    int M = c.size();
    for (int a = 0; a < M; ++a)
      for (int b = a+1; b < M; ++b)
        for (int d = b+1; d < M; ++d) {
            set<int> skip = {c[a], c[b], c[d]};
            int xl = INT_MAX, xh = INT_MIN, yl = INT_MAX, yh = INT_MIN;
            for (int i = 0; i < N; ++i) if (!skip.count(i)) {
                xl = min(xl, X[i]); xh = max(xh, X[i]);
                yl = min(yl, Y[i]); yh = max(yh, Y[i]);
            }
            ans = min(ans, (long long)(xh-xl)*(yh-yl));
        }
    cout << ans << "\n";
}

Pitfalls

What Bronze 2016 US Open was actually testing