USACO Solutions

Solutions to USACO training and USACO contest problems.

USACO Training:

| Problem Number | Problem Name | Solution Notes | | -------------- | ------------ | -------------- | | 1.5.1 | [Arithmetic Progressions][1.5.1] | Careful Brute Force | | 1.6.3 | [Superprime Rib][1.6.3] | Brute force | | 2.1.1 | [The Castle][2.1.1] | Floodfill to assign each room a number | | 2.1.2 | [Ordered Fractions][2.1.2] | Generate all possible fractions | | 2.1.3 | [Sorting A Three-Valued Sequence][2.1.3] | Notes written as comments in code | | 2.1.4 | [Healthy Holsteins][2.1.4] | Brute force | | 2.1.5 | [Hamming Codes][2.1.5] | Brute force | | 2.2.1 | [Preface Numbering][2.2.1] | Brute force | | 2.2.2 | [Subset Sums][2.2.2] | DP | | 2.2.3 | [Runaround Numbers][2.2.3] | Brute force | | 2.2.4 | [Party Lamps][2.2.4] | Brute force 2^4, doesn't matter if you press button twice | | 2.3.1 | [Longest Prefix][2.3.1] | DP | | 2.3.2 | [Cow Pedigrees][2.3.2] | DP | | 2.3.3 | [Zero Sum][2.3.3] | Brute force (DFS) | | 2.3.4 | [Money Systems][2.3.4] | DP (VN) | | 2.3.5 | [Controlling Companies][2.3.5] | Recursion | | 2.4.1 | [The Tamworth Two][2.4.1] | Brute force, maximum (100*4)^2 steps before "impossible" | | 2.4.2 | [Overfencing][2.4.2] | run shortest path BFS on two exit nodes | | 2.4.3 | [Cow Tours][2.4.3] | Dijkstra | | 2.4.4 | [Bessie Come Home][2.4.4] | Dijkstra | | 2.4.5 | [Fractions to Decimals][2.4.5] | Recursion | | 3.1.1 | [Agri-Net][3.1.1] | Prim's (or Kruskal) | | 3.1.2 | [Score Inflation][3.1.2] | Knapsack | | 3.1.3 | [Humble Numbers][3.1.3] | Create size N set of possible numbers, brute force | | 3.1.4 | [Contact][3.1.4] | Brute force | | 3.1.5 | [Stamps][3.1.5] | DP | | 3.2.1 | [Factorials][3.2.1] | Count number of twos and fives | | 3.2.2 | [Stringsobits][3.2.2] | Define dp(i, j) = # of numbers with i bits and at most j ones | | 3.2.3 | [Spinning Wheels][3.2.3] | Brute Force, max 360 seconds | | 3.2.4 | [Feed Ratios][3.2.4] | Brute force | | 3.2.5 | [Magic Squares][3.2.5] | BFS | | 3.2.6 | [Sweet Butter][3.2.6] | APSP | | 3.3.1 | [Riding the Fences][3.3.1] | Eulerian Path | | 3.3.2 | [Shopping Offers][3.3.2] | Dijkstra | | 3.3.3 | [Camelot][3.3.3] | Brute force, king can take only two steps | | 3.3.4 | [Home on the Range][3.3.4] | DP | | 3.3.5 | [A Game][3.3.5] | DP | | 3.4.1 | [American Heritage][3.4.1] | Recursively generate tree | | 3.4.2 | [Electric Fence][3.4.2] | Pick's Theorem | | 3.4.3 | [Raucous Rockers][3.4.3] | Brute Force (Bitmasking) | | 4.1.1 | [Beef McNuggets][4.1.1] | DP | | 4.1.2 | [Fence Loops][4.1.2] | Dijkstra | | 4.2.1 | [Drainage Ditches][4.2.1] | Max Flow O(V^2E) | | 4.2.3 | [Job Processing][4.2.3] | Greedy |

Silver USACO Contests:

| Contest Date | Problem ID | Problem Name | Solution Notes | Score | | ------------ | ---------- | ------------ | -------------- | ----- | | Feb 2018 | [reststops][reststops] | Rest Stops | Greedy | 10/10 |

Gold USACO Contests:

Old USACO Gold (Silver):

| Contest Date | Problem ID | Problem Name | Solution Notes | Score | | ------------ | ---------- | ------------ | -------------- | ----- | | Nov 2012 | [clumsy][clumsy] | Clumsy Cows | Greedy | 16/16 | | Nov 2012 | [distant][distant] | Distant Pastures | APSP, dijkstra | 16/16 | | Nov 2012 | [bbreeds][bbreeds] | Balanced Cow Breeds | Same problem as Gold | 16/16 | | Dec 2012 | [crazy][crazy] | Crazy Fences | Computational Geometry | 10/10 | | Dec 2012 | [wifi][wifi] | Wifi Setup | DP | 10/10 | | Dec 2012 | [mroute][mroute] | Milk Routing | Dijkstra | 10/10 | | Jan 2013 | [paint][paint] | Painting the Fence | Coordinate Compression, Store Deltas & Sweep | 10/10 | | Jan 2013 | [squares][squares] | Square Overlap | Sweep | 10/10 | | Jan 2013 | [invite][invite] | Party Invitations | precompute which groups each cow is in | 10/10 | | Feb 2013 | [perimeter][perimeter] | Perimeter | Optimized Floodfill | 10/10 | | Feb 2013 | [tractor][tractor] | Tractor | Binary search for answer, dfs | 10/10 | | Feb 2013 | [msched][msched] | Milk Scheduling | Greedy | 10/10 | | Mar 2013 | [poker][poker] | Poker Hands | Greedy | 10/10 | | Mar 2013 | [painting][painting] | Farm Painting | Sweep | 10/10 | | Mar 2013 | [cowrun][cowrun] | The Cow Run | DP, same as gold | 15/15 | | Open 2013 | [gravity][gravity] | What's Up With Gravity? | Dijkstra | 10/10 | | Open 2013 | [fuel][fuel] | Fuel Economy | Greedy | 10/10 | | Open 2013 | [cruise][cruise] | Luxury River Cruise | Find where sequence repeats | 10/10 | | Nov 2013 | [nocow][nocow] | Farmer John has no Large Brown Cow | Solvable with a bit of math | 10/10 | | Nov 2013 | [crowded][crowded] | Crowded Cows | Sweep, can use multiset instead of monotonic queue | 11/11 | | Nov 2013 | [pogocow][pogocow] | Pogo-Cow | DP, note that Bessie can go either direction | 11/11 | | Dec 2013 | [msched][msched2] | Milk Scheduling | Greedy, sweep | 11/11 | | Dec 2013 | [vacation][vacation] | Vacation Planning | Code is slightly modified from gold version, answer is unnecessarily complicated for silver | 10/10 | | Dec 2013 | [shuffle][shuffle] | The Bessie Shuffle | Repeated Squaring, Permutations, Composing functions/permutations | 10/10 | | Jan 2014 | [slowdown][slowdown] | Bessie Slows Down | Maintain two arrays, simulation | 10/10 | | Jan 2014 | [ccski][ccski] | Cross Country Skiing | Prim's | 10/10 | | Jan 2014 | [recording][recording] | Recording the Moolympics | Greedy | 10/10 | | Feb 2014 | [auto][auto] | Auto-complete | Binary search | 10/10 | | Feb 2014 | [rblock][rblock] | Roadblock | Dijkstra | 10/10 | | Feb 2014 | [scode][scode] | Secret Code | DP | 10/10 | | Mar 2014 | [irrigation][irrigation] | Watering the Fields | Kruskal/MST | 10/10 | | Mar 2014 | [lazy][lazy] | The Lazy Cow | Rotate grid 45 degrees | 10/10 | | Mar 2014 | [mooomoo][mooomoo] | Mooo Moo | DP | 10/10 | | Open 2014 | [fairphoto][fairphoto] | Fair Photography | Sweep | 10/10 | | Open 2014 | [gpsduel][gpsduel] | Dueling GPSs | Dijkstra | 10/10 | | Dec 2014 | [piggyback][piggyback] | Piggy Back | Shortest Path on three nodes | 11/11 | | Dec 2014 | [cowjog][cowjog] | Cow Jog | Sweep | 15/15 | | Jan 2015 | [stampede][stampede] | Stampede | Sweep | 15/15 | | Jan 2015 | [cowroute][cowroute] | Cow Routing | Dijkstra | 12/12 | | Jan 2015 | [meeting][meeting] | Meeting Time | DP | 15/15 | | Feb 2015 | [censor][censor] | Censoring | Rolling Hash | 15/15 | | Feb 2015 | [hopscotch][hopscotch] | Cow Hopscotch | DP | 15/15 | | Feb 2015 | [superbull][superbull] | Superbull | MST, Prim's O(V^2) | 10/10 | | Open 2015 | [bgm][bgm] | Bessie Goes Moo | Parity | 10/10 | | Open 2015 | [trapped][trapped] | Trapped in the Haybales (Silver) | Sort, Sweep | 14/14 |

USACO Gold (2015-now)

| Contest Date | Problem ID | Problem Name | Solution Notes | Score | | ------------ | ---------- | ------------ | -------------- | ----- | | Dec 2015 | [cardgame][cardgame] | High Card Low Card (Gold) | Greedy | 15/15 | | Dec 2015 | [feast][feast] | Fruit Feast | DP (Knapsack) | 12/12 | | Dec 2015 | [dream][dream] | Bessie's Dream | Dijkstra | 16/16 | | Jan 2016 | [radio][radio] | Radio Contact | DP | 10/10 | | Feb 2016 | [cbarn][cbarn] | Circular Barn | Greedy | 10/10 | | Feb 2016 | [cbarn2][cbarn2] | Circular Barn (Revisited) | DP | 10/10 | | Feb 2016 | [fencedin][fencedin] | Fenced In | MST (Kruskal) | 10/10 | | Open 2016 | [split][split] | Splitting The Field | Sweep | 10/10 | | Open 2016 | [closing][closing] | Closing The Farm | UFDS (Note: Runs really close to time limit) | 10/10 | | Open 2016 | [248][248] | 248 | DP | 12/12 | | Dec 2016 | [moocast][moocast] | Moocast | UFDS, brute force | 10/10 | | Dec 2016 | [checklist][checklist] | Cow Checklist | DP | 10/10 | | Dec 2016 | [lasers][lasers] | Lasers and Mirrors | BFS | 11/11 | | Jan 2017 | [bphoto][bphoto] | Balanced Photo | Fenwick Tree | 10/10 | | Jan 2017 | [hps][hps] | Hoof, Paper, Scissors | 3D DP | 10/10 | | Jan 2017 | [cownav][cownav] | Cow Navigation | BFS | 10/10 | | Feb 2017 | [visitfj][visitfj] | Why Did The Cow Cross The Road | Dijkstra | 11/11 | | Feb 2017 | [nocross][nocross] | Why Did The Cow Cross The Road II | DP | 10/10 | | Feb 2017 | [circlecross][circlecross] | Why Did The Cow Cross The Road III | Fenwick Tree (BIT) | 10/10 | | Open 2017 | [cownomics][cownomics] | Bovine Genomics | Rolling Hash | 10/10 | | Open 2017 | [art2][art2] | Modern Art 2 | Calculate start/end points | 10/10 | | Dec 2017 | [piepie][piepie] | A Pie For A Pie | BFS, binary search | 10/10 | | Dec 2017 | [barnpainting][barnpainting] | Barn Painting | DP | 10/10 | | Dec 2017 | [hayfeast][hayfeast] | Haybale Feast | Two Pointers | 10/10 | | Jan 2018 | [mootube][mootube] | MooTube | UFDS | 10/10 | | Jan 2018 | [atlarge][atlarge] | Cow At Large | DFS/BFS | 13/13 | | Jan 2018 | [spainting][spainting] | Stamp Painting | DP, recurrence | 12/12 | | Feb 2018 | [snowboots][snowboots] | Snow Boots | Sort, Doubly-Linked List | 12/12 | | Feb 2018 | [dirtraverse][dirtraverse] | Directory Traversal | DFS | 10/10 | | Feb 2018 | [taming][taming] | Taming The Herd | DP | 11/11 | | Open 2018 | [sort][sort] | Out of Sorts | BIT | 10/10 | | Open 2018 | [milkorder][milkorder] | Milking Order | Topological Sort (Lexicographically earliest) | 10/10 | | Open 2018 | [talent][talent] | Talent Show | Binary search for answer, DP | 10/10 |

Platinum USACO Contests:

Old USACO Platinum (Gold):

| Contest Date | Problem ID | Problem Name | Solution Notes | Score | | ------------ | ---------- | ------------ | -------------- | ----- | | Nov 2012 | [bbreeds][bbreeds] | Balanced Cow Breeds | DP | 16/16 | | Dec 2012 | [gangs][gangs] | Gangs of Istanbull/Cowstantinople | Greedy | 12/12 | | Dec 2012 | [first][first] | First! | trie, checking DAG for cycles | 12/12 | | Dec 2012 | [runaway][runaway] | Running Away From the Barn | | 10/10 | | Jan 2013 | [lineup][lineup] | Cow Lineup | sweep with two pointers | 10/10 | | Jan 2013 | [island][island] | Island Travels | bfs | 11/11 | | Jan 2013 | [seating][seating] | Sea