U USACO Prep

USACO 2016 US Open — the finals round, all four divisions.

The US Open is the final contest of the USACO season — the 5-hour finals that feed the camp-invitation pipeline. This page indexes the 2016 US Open end-to-end: Bronze through Platinum, with the official statement link, the key idea, complexity target, and a runnable C++ reference for each problem on the per-division pages.

Bronze (all 3) → Silver (all 3) → Gold (all 3) → Platinum (all 3) →
Authoritative source. All problem titles, constraints, and results below are taken from the official 2016 US Open results page on usaco.org: usaco.org/index.php?page=open16results. Each problem links to its canonical statement on usaco.org/index.php?page=viewproblem2&cpid=… (cpids 639–650). Several titles — Diamond Collector, Field Reduction, Closing the Farm, Bull in a China Shop — appear at two division levels with progressively harder constraints, a hallmark of the 2016 Open round.

Round metadata

ContestUSACO 2016 US Open
Window4-day contest window, late March / early April 2016
Length per division5 hours (US Open is the long finals round; the Dec/Jan/Feb regular-season rounds are 4 hours)
SignificanceFinal contest of the season — results plus regular-season scores determine invitations to the USACO summer training camp
Problems per division3
Total problems12 (Bronze 1–3, Silver 1–3, Gold 1–3, Platinum 1–3)
ScoringIOI-style partial credit, 1000 points per problem, 3000 max per division
Allowed languagesC, C++11, Java, Python 2.7, Python 3
Promotion cutoffCompetitors scoring at least 750/3000 in a division were typically auto-promoted for next season.

The contest at a glance

Bronze

Bronze · 3 problems

1. Diamond Collector — sort N diamond sizes, find the longest contiguous subarray whose max−min ≤ K.

2. Bull in a China Shop — brute-force search over K-step bull moves on a small grid; count distinct reachable cells.

3. Field Reduction — given N cow positions, remove exactly 3 to minimize the bounding-box area; try all 4 extreme-corner candidates.

Open Bronze write-up →
 Silver

Silver · 3 problems

1. Field Reduction — Silver version: still remove 3 cows of up to 50 000, but pick from a small "extreme" candidate set per axis.

2. Diamond Collector — choose two non-overlapping sets of diamonds, each with spread ≤ K; sweep + best-suffix DP.

3. Closing the Farm — offline reverse-time DSU: process barn closures in reverse as union operations.

Open Silver write-up →
 Gold

Gold · 3 problems

1. Splitting the Field — partition N points into two axis-aligned bounding rectangles, minimize total area; sweep + prefix mins.

2. Closing the Farm — Gold version: same reverse-DSU pattern but bigger graph, watch the I/O.

3. 248 — 2048-style interval DP: merge adjacent equal values into value+1; maximize final tile.

Open Gold write-up →
 Platinum

Platinum · 3 problems

1. 262144 — N up to 262144; sparse DP where dp[v][i] = right endpoint of an interval starting at i that collapses to v.

2. Bull in a China Shop — count triples of shattered figurine pieces that, under translation, rotation and reflection, perfectly reassemble the original picture (Zobrist hashing over covered cells).

3. Landscaping — transform flowerbed dirt amounts at min cost given buy / dispose / transport prices; 1D min-cost matching via regret-augmented priority queue.

Open Platinum write-up →

How to use this set

  1. Pick your division. Open the full division page and read all three statements before writing any code.
  2. Solve P1 first, P2 if time, P3 only if you're cruising. US Open P1s are usually still the cheapest points; the 5-hour budget lets you finish P2 cleanly.
  3. Time-box. 5 hours total. Don't spend more than ~120 minutes on a single problem without a working subtask submission.
  4. Compare to the reference C++. Each problem on the division page has a short reference solution; if yours is much longer, ask why.
  5. Verify with the editorial. Official editorials are linked from each problem page on usaco.org.