usaco.org/index.php?page=viewproblem2&cpid=…, cpids 919–930).
Round metadata
| Contest | USACO 2019 January |
|---|---|
| Window | Roughly Jan 25–28, 2019 (4-day window, single 4-hour personal timer) |
| Length per division | 4 hours (Dec/Jan/Feb format; US Open is the 5-hour round) |
| Problems per division | 3 |
| Total problems | 12 (Bronze 1–3, Silver 1–3, Gold 1–3, Platinum 1–3) |
| Scoring | IOI-style partial credit, 1000 points per problem, 3000 max per division |
| Allowed languages | C, C++11, Java, Python 2.7, Python 3.6 (C++17 was not yet a default option in early 2019). |
| Promotion cutoffs | Set per-contest by USACO; check the results page for exact thresholds. |
The contest at a glance
Bronze · 3 problems
1. Shell Game — simulate Bessie's three-shell game and count how many guesses were correct (direct simulation).
2. Mixing Milk — repeatedly pour bucket i into bucket i+1 (mod 3) for 100 steps; print final volumes (simulation with capacities).
3. Sleepy Cow Sorting (Bronze) — minimum number of suffix "insertions" to sort a permutation: find longest already-sorted suffix and answer is N − that length.
Silver · 3 problems
1. Grass Planting — tree where each edge needs a grass type and no two edges sharing a vertex may share a type; answer = max degree (graph coloring observation).
2. Sleepy Cow Sorting (Silver) — given a permutation, output the number of moves and indices needed when each move takes the front cow and reinserts it into the sorted suffix.
3. Icy Perimeter — in a grid of '#' / '.', find the connected component with largest area; tiebreak by smallest perimeter (flood-fill + boundary counting).
Gold · 3 problems
1. Sleepy Cow Sorting (Gold) — count permutations that are reachable in exactly K moves of "take any element and push it to the end"; combinatorial DP / binomial sums.
2. Shortcut — Farmer John adds one zero-time edge from the barn to any field; choose the field that maximizes total cow time saved over single-source shortest paths (Dijkstra + subtree sums on shortest-path tree).
3. Cow Poetry — count K-line poems with rhyme scheme constraints, words of given syllable counts and rhyme classes; knapsack-style line counts then group by rhyme class with exponentiation.
Platinum · 3 problems
1. Train Tracking 2 — reconstruct number of valid car-weight sequences from a sliding-window minimum array of length N−K+1; segment tree + combinatorics modulo prime.
2. Redistricting — partition N cows on a line into contiguous districts of size ≤ K, minimize number of districts won by the wrong breed; deque-optimized DP.
3. Sleepy Cow Sorting (Platinum) — sleepy-cow generalization: query-heavy interactive variant tracking the operation cost on permutations under updates; advanced segment tree / persistent structures.
How to use this set
- Pick your division. Open the full division page and read the three statements before writing any code.
- Solve P1 first, P2 if time, P3 only if you're cruising. January problem 1s are usually the cheapest points.
- Time-box. 4 hours total. Don't spend more than ~90 minutes on a single problem without a working subtask submission.
- Compare to the reference C++. Each problem on the division page has a ~30–50 line reference solution. If yours is much longer, ask why.
- Verify with the editorial. Official editorials are linked from each problem page on usaco.org.