USACO 2017 US Open · Silver · all three problems
Problem 1 — Paired Up
Statement
There are M cows in total, described by N input lines where each line gives a count y and a milk output x (so y cows each produce x units). M is guaranteed even. Pair cows into M/2 disjoint pairs; the time to milk a pair (a, b) is a + b. Minimize the maximum pair-sum across all pairs.
Constraints
- 1 ≤ N ≤ 100,000 distinct (output, count) lines.
- 1 ≤ total cows M ≤ 109, M even.
- 1 ≤ output value ≤ 109.
- Time limit: 2s.
Key idea
Classical: to minimize the maximum pair-sum you pair the smallest with the largest, then the next-smallest with the next-largest, etc. Sort the (output, count) groups by output and walk a two-pointer inward, consuming min(left_count, right_count) cows per step from each end and recording the worst pair-sum seen. Counts can be up to 109, so don't expand groups — operate on (value, count) blocks.
Complexity target
O(N log N) for the sort; the two-pointer walk is O(N) blocks.
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<pair<ll, ll>> v(N); // {output, count}
for (auto& p : v) cin >> p.second >> p.first;
sort(v.begin(), v.end());
int lo = 0, hi = N - 1;
ll lc = v[lo].second, hc = v[hi].second;
ll ans = 0;
while (lo < hi) {
ans = max(ans, v[lo].first + v[hi].first);
ll take = min(lc, hc);
lc -= take; hc -= take;
if (lc == 0 && ++lo <= hi) lc = v[lo].second;
if (hc == 0 && --hi >= lo) hc = v[hi].second;
}
// If lo == hi remaining, those cows pair among themselves -> pair-sum = 2*output.
if (lo == hi && v[lo].second > 0 && (lc > 0 || hc > 0))
ans = max(ans, 2 * v[lo].first);
cout << ans << "\n";
}
Pitfalls
- M up to 109. Never expand to individual cows; stay on (value, count) tuples.
- Same-block residual. When lo == hi but there are leftover cows in that block, they pair within the block at sum 2·value — account for it.
- 64-bit. Outputs are up to 109; sums are up to 2·109.
- Sort order matters. Read carefully whether the input gives "count value" or "value count"; the sort key is the milk output.
Problem 2 — Bovine Genomics
Statement
N spotty cows and N plain cows, each with a genome of length M over {A, C, G, T}. Count the number of unordered triples of distinct positions (i, j, k) such that no spotty cow's triple of letters at those positions matches any plain cow's triple at the same positions.
Constraints
- 1 ≤ N ≤ 500.
- 3 ≤ M ≤ 50.
- Genomes are over {A, C, G, T}.
- Time limit: 2s.
Key idea
There are C(M, 3) ≤ C(50, 3) = 19600 triples. For each triple, encode each cow's three letters as a 6-bit integer (2 bits per base). Insert all spotty cows' codes into a 64-element bitset, then check if any plain cow's code collides. O(C(M,3) · N) ≈ 19600 · 500 = ~107, well within limits.
Complexity target
O(M3 · N) with a 64-element bitset; ~107 ops.
Reference solution (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int code(char c) {
return c == 'A' ? 0 : c == 'C' ? 1 : c == 'G' ? 2 : 3;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M; cin >> N >> M;
vector<string> sp(N), pl(N);
for (auto& s : sp) cin >> s;
for (auto& s : pl) cin >> s;
// Pre-encode each cow at every column.
vector<vector<int>> SP(N, vector<int>(M)), PL(N, vector<int>(M));
for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j)
SP[i][j] = code(sp[i][j]), PL[i][j] = code(pl[i][j]);
ll ans = 0;
for (int a = 0; a < M; ++a)
for (int b = a + 1; b < M; ++b)
for (int c = b + 1; c < M; ++c) {
uint64_t mask = 0;
for (int i = 0; i < N; ++i)
mask |= 1ULL << ((SP[i][a] << 4) | (SP[i][b] << 2) | SP[i][c]);
bool ok = true;
for (int i = 0; i < N && ok; ++i) {
int k = (PL[i][a] << 4) | (PL[i][b] << 2) | PL[i][c];
if (mask >> k & 1) ok = false;
}
if (ok) ++ans;
}
cout << ans << "\n";
}
Pitfalls
- Order of positions doesn't matter — iterate a < b < c to count each triple once.
- Encode rather than hash. Six bits per triple fits in a single 64-bit bitset; hash maps will TLE at 107.
- Early-out on collision. Break the plain loop the moment a collision is found.
- Don't confuse with Bronze. Bronze asks: how many single positions split the groups? Silver asks: how many triples?
Problem 3 — Where's Bessie?
Statement
Given an N×N grid of uppercase letters A–Z (each letter is a color), find all "Potential Cow Locations" (PCLs). A PCL is an axis-aligned rectangular sub-grid that uses exactly two distinct colors, where one color forms exactly one 4-connected region inside the rectangle and the other color forms two or more 4-connected regions. Additionally, a PCL must not be strictly contained inside another PCL, and two PCLs may not overlap. Output the count of PCLs after applying the non-containment / non-overlap rule.
Constraints
- 1 ≤ N ≤ 20.
- Cells are characters 'A'..'Z'.
- Time limit: 2s.
Key idea
There are only O(N4) = 160,000 sub-rectangles. For each one, scan its cells to collect the distinct letters; if exactly two distinct letters are present, run two small flood fills (one per color inside the rectangle) to count 4-connected regions per color. If one color has exactly 1 region and the other has ≥ 2, mark the rectangle as a candidate PCL. Then filter candidates by the containment / overlap rule (pairwise comparison is O(K2) with K small).
Complexity target
O(N4 · N2) = O(N6) ≈ 64 million worst case — fine in 2s with tight code.
Reference solution (C++)
#include <bits/stdc++.h>
using namespace std;
int N;
vector<string> g;
int seen[22][22];
int regions(int r1, int c1, int r2, int c2, char col, int tag) {
int cnt = 0;
for (int i = r1; i <= r2; ++i)
for (int j = c1; j <= c2; ++j)
if (g[i][j] == col && seen[i][j] != tag) {
++cnt;
// BFS
queue<pair<int,int>> q; q.push({i, j}); seen[i][j] = tag;
int dx[]={-1,1,0,0}, dy[]={0,0,-1,1};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < r1 || nx > r2 || ny < c1 || ny > c2) continue;
if (g[nx][ny] == col && seen[nx][ny] != tag) {
seen[nx][ny] = tag; q.push({nx, ny});
}
}
}
}
return cnt;
}
int main() {
cin >> N; g.assign(N, "");
for (auto& r : g) cin >> r;
vector<tuple<int,int,int,int>> pcls;
int tag = 0;
for (int r1 = 0; r1 < N; ++r1)
for (int c1 = 0; c1 < N; ++c1)
for (int r2 = r1; r2 < N; ++r2)
for (int c2 = c1; c2 < N; ++c2) {
int mask = 0; char two[2]; int k = 0;
for (int i = r1; i <= r2 && k <= 2; ++i)
for (int j = c1; j <= c2 && k <= 2; ++j) {
int b = 1 << (g[i][j] - 'A');
if (!(mask & b)) { mask |= b; if (k < 2) two[k] = g[i][j]; ++k; }
}
if (k != 2) continue;
int a1 = regions(r1, c1, r2, c2, two[0], ++tag);
int a2 = regions(r1, c1, r2, c2, two[1], ++tag);
if ((a1 == 1 && a2 >= 2) || (a2 == 1 && a1 >= 2))
pcls.push_back({r1, c1, r2, c2});
}
// Filter: drop a PCL that is strictly contained in another PCL.
vector<char> keep(pcls.size(), 1);
for (size_t i = 0; i < pcls.size(); ++i)
for (size_t j = 0; j < pcls.size(); ++j) if (i != j) {
auto [a, b, c, d] = pcls[i];
auto [e, f, gg, h] = pcls[j];
if (e <= a && f <= b && c <= gg && d <= h &&
!(a == e && b == f && c == gg && d == h))
keep[i] = 0;
}
int ans = 0; for (char k : keep) ans += k;
cout << ans << "\n";
}
Pitfalls
- Exactly two distinct colors. Single-color or 3+ color rectangles are out immediately.
- 4-connected, not 8-connected. Diagonals don't connect regions.
- Containment rule, not overlap. Re-read the statement: a PCL strictly inside another is discarded. Equal-bbox is kept.
- Re-using a global seen[][] array. Use a per-flood-fill tag id to avoid resetting an N×N array O(N4) times.
What Silver 2017 US Open was actually testing
- P1 — greedy with grouped counts. Big-M needs compressed two-pointer; the pairing rule itself is the standard min-max greedy.
- P2 — combinatorial enumeration + bitset fingerprint. Encode small tuples to integers and test set membership.
- P3 — sub-rectangle enumeration with flood fill. Classic Silver "brute the rectangles, smart-fill inside" pattern.