Zephyril/usaco-1 forked from thecodingwizard/usaco

Solutions to USACO Training and USACO Contest Problems
This branch is even with thecodingwizard:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
alphastar-turing
usaco-contests
usaco-training
.gitignore
CMakeLists.txt
main.cpp
run

USACO Solutions

Solutions to USACO training and USACO contest problems.

USACO Training:

Problem Number Problem Name Solution Notes
1.5.1 Arithmetic Progressions Careful Brute Force
1.6.3 Superprime Rib Brute force
2.1.1 The Castle Floodfill to assign each room a number
2.1.2 Ordered Fractions Generate all possible fractions
2.1.3 Sorting A Three-Valued Sequence Notes written as comments in code
2.1.4 Healthy Holsteins Brute force
2.1.5 Hamming Codes Brute force
2.2.1 Preface Numbering Brute force
2.2.2 Subset Sums DP
2.2.3 Runaround Numbers Brute force
2.2.4 Party Lamps Brute force 2^4, doesn't matter if you press button twice
2.3.1 Longest Prefix DP
2.3.2 Cow Pedigrees DP
2.3.3 Zero Sum Brute force (DFS)
2.3.4 Money Systems DP (VN)
2.3.5 Controlling Companies Recursion
2.4.1 The Tamworth Two Brute force, maximum (100*4)^2 steps before "impossible"
2.4.2 Overfencing run shortest path BFS on two exit nodes
2.4.3 Cow Tours Dijkstra
2.4.4 Bessie Come Home Dijkstra
2.4.5 Fractions to Decimals Recursion
3.1.1 Agri-Net Prim's (or Kruskal)
3.1.2 Score Inflation Knapsack
3.1.3 Humble Numbers Create size N set of possible numbers, brute force
3.1.4 Contact Brute force
3.1.5 Stamps DP
3.2.1 Factorials Count number of twos and fives
3.2.2 Stringsobits Define `dp(i, j) = # of numbers with i bits and at most j ones`
3.2.3 Spinning Wheels Brute Force, max 360 seconds
3.2.4 Feed Ratios Brute force
3.2.5 Magic Squares BFS
3.2.6 Sweet Butter APSP
3.3.1 Riding the Fences Eulerian Path
3.3.2 Shopping Offers Dijkstra
3.3.3 Camelot Brute force, king can take only two steps
3.3.4 Home on the Range DP
3.3.5 A Game DP
3.4.1 American Heritage Recursively generate tree
3.4.2 Electric Fence Pick's Theorem
3.4.3 Raucous Rockers Brute Force (Bitmasking)
4.1.1 Beef McNuggets DP
4.1.2 Fence Loops Dijkstra
4.2.1 Drainage Ditches 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 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 Cows Greedy 16/16
Nov 2012 distant Distant Pastures APSP, dijkstra 16/16
Nov 2012 bbreeds Balanced Cow Breeds Same problem as Gold 16/16
Dec 2012 crazy Crazy Fences Computational Geometry 10/10
Dec 2012 wifi Wifi Setup DP 10/10
Dec 2012 mroute Milk Routing Dijkstra 10/10
Jan 2013 paint Painting the Fence Coordinate Compression, Store Deltas & Sweep 10/10
Jan 2013 squares Square Overlap Sweep 10/10
Jan 2013 invite Party Invitations precompute which groups each cow is in 10/10
Feb 2013 perimeter Perimeter Optimized Floodfill 10/10
Feb 2013 tractor Tractor Binary search for answer, dfs 10/10
Feb 2013 msched Milk Scheduling Greedy 10/10
Mar 2013 poker Poker Hands Greedy 10/10
Mar 2013 painting Farm Painting Sweep 10/10
Mar 2013 cowrun The Cow Run DP, same as gold 15/15
Open 2013 gravity What's Up With Gravity? Dijkstra 10/10
Open 2013 fuel Fuel Economy Greedy 10/10
Open 2013 cruise Luxury River Cruise Find where sequence repeats 10/10
Nov 2013 nocow Farmer John has no Large Brown Cow Solvable with a bit of math 10/10
Nov 2013 crowded Crowded Cows Sweep, can use multiset instead of monotonic queue 11/11
Nov 2013 pogocow Pogo-Cow DP, note that Bessie can go either direction 11/11
Dec 2013 msched Milk Scheduling Greedy, sweep 11/11
Dec 2013 vacation Vacation Planning Code is slightly modified from gold version, answer is unnecessarily complicated for silver 10/10
Dec 2013 shuffle The Bessie Shuffle Repeated Squaring, Permutations, Composing functions/permutations 10/10
Jan 2014 slowdown Bessie Slows Down Maintain two arrays, simulation 10/10
Jan 2014 ccski Cross Country Skiing Prim's 10/10
Jan 2014 recording Recording the Moolympics Greedy 10/10
Feb 2014 auto Auto-complete Binary search 10/10
Feb 2014 rblock Roadblock Dijkstra 10/10
Feb 2014 scode Secret Code DP 10/10
Mar 2014 irrigation Watering the Fields Kruskal/MST 10/10
Mar 2014 lazy The Lazy Cow Rotate grid 45 degrees 10/10
Mar 2014 mooomoo Mooo Moo DP 10/10
Open 2014 fairphoto Fair Photography Sweep 10/10
Open 2014 gpsduel Dueling GPSs Dijkstra 10/10
Dec 2014 piggyback Piggy Back Shortest Path on three nodes 11/11
Dec 2014 cowjog Cow Jog Sweep 15/15
Jan 2015 stampede Stampede Sweep 15/15
Jan 2015 cowroute Cow Routing Dijkstra 12/12
Jan 2015 meeting Meeting Time DP 15/15
Feb 2015 censor Censoring Rolling Hash 15/15
Feb 2015 hopscotch Cow Hopscotch DP 15/15
Feb 2015 superbull Superbull MST, Prim's O(V^2) 10/10
Open 2015 bgm Bessie Goes Moo Parity 10/10
Open 2015 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 High Card Low Card (Gold) Greedy 15/15
Dec 2015 feast Fruit Feast DP (Knapsack) 12/12
Dec 2015 dream Bessie's Dream Dijkstra 16/16
Feb 2016 cbarn Circular Barn Greedy 10/10
Feb 2016 cbarn2 Circular Barn (Revisited) DP 10/10
Feb 2016 fencedin Fenced In MST (Kruskal) 10/10
Open 2016 split Splitting The Field Sweep 10/10
Open 2016 closing Closing The Farm UFDS (Note: Runs really close to time limit) 10/10
Open 2016 248 248 DP 12/12
Dec 2016 moocast Moocast UFDS, brute force 10/10
Dec 2016 checklist Cow Checklist DP 10/10
Dec 2016 lasers Lasers and Mirrors BFS 11/11
Jan 2017 bphoto Balanced Photo Fenwick Tree 10/10
Jan 2017 hps Hoof, Paper, Scissors 3D DP 10/10
Jan 2017 cownav Cow Navigation BFS 10/10
Feb 2017 visitfj Why Did The Cow Cross The Road Dijkstra 11/11
Feb 2017 nocross Why Did The Cow Cross The Road II DP 10/10
Feb 2017 circlecross Why Did The Cow Cross The Road III Fenwick Tree (BIT) 10/10
Open 2017 cownomics Bovine Genomics Rolling Hash 10/10
Open 2017 art2 Modern Art 2 Calculate start/end points 10/10
Dec 2017 piepie A Pie For A Pie BFS, binary search 10/10
Dec 2017 barnpainting Barn Painting DP 10/10
Dec 2017 hayfeast Haybale Feast Two Pointers 10/10
Jan 2018 mootube MooTube UFDS 10/10
Jan 2018 atlarge Cow At Large DFS/BFS 13/13
Jan 2018 spainting Stamp Painting DP, recurrence 12/12
Feb 2018 snowboots Snow Boots Sort, Doubly-Linked List 12/12
Feb 2018 dirtraverse Directory Traversal DFS 10/10
Feb 2018 taming Taming The Herd DP 11/11
Open 2018 sort Out of Sorts BIT 10/10
Open 2018 milkorder Milking Order Topological Sort (Lexicographically earliest) 10/10
Open 2018 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 Balanced Cow Breeds DP 16/16
Dec 2012 gangs Gangs of Istanbull/Cowstantinople Greedy 12/12
Dec 2012 first First! trie, checking DAG for cycles 12/12
Dec 2012 runaway Running Away From the Barn 10/10
Jan 2013 lineup Cow Lineup sweep with two pointers 10/10
Jan 2013 island Island Travels bfs 11/11
Jan 2013 seating Seating Binary Tree, Lazy Propagation 10/10
Feb 2013 partition Partitioning The Farm DP 17/17
Feb 2013 taxi Taxi Min Cost Matching, calculate distance driven w/o cow 12/12
Feb 2013 route Route Designing DP 10/10
Mar 2013 cowrun The Cow Run DP 14/14
Mar 2013 hillwalk Hill Walk Line sweep, find a way to order hills 12/12
Nov 2013 nochange No Change DP, 2^k state 13/13
Nov 2013 sight Line of Sight If two cows can see the same point on the silo, they can see each other 11/11
Nov 2013 empty Empty Stalls Sweep 11/11
Dec 2013 vacationgold Vacation Planning (Gold) Dijkstra 10/10
Dec 2013 optmilk Optimal Milking Binary Tree 11/11
Jan 2014 skicourse Building A Ski Course DP 10/10
Jan 2014 skilevel Ski Course Rating Kruskal 10/10
Feb 2014 rblock Roadblock Dijkstra 10/10
Feb 2014 dec Cow Decathlon DP 10/10
Mar 2014 sabotage Sabotage Binary search, 1D max sum 14/14
Mar 2014 fcount Counting Friends Brute Force, greedily connect friends 11/11
Dec 2014 guard Guard Mark DP 12/12
Dec 2014 marathon Marathon Segment Tree 10/10
Dec 2014 cowjog Cow Jog Longest Non-Increasing Subsequence 14/14
Jan 2015 cowrect Cow Rectangles Sweep, assume we have to take one of the Holsteins 14/14
Jan 2015 movie Moovie Mooving DP, bitmasking 14/14
Open 2015 palpath Palindromic Paths DP 12/12
Open 2015 trapped Trapped in the Haybales Sort haybales by weight 15/15
Open 2015 buffet Bessie's Birthday Buffet DP 15/15

USACO Platinum (2015-now):

Contest Date Problem ID Problem Name Solution Notes Score
Dec 2015 maxflow Max Flow LCA, prefix sums 15/15
Dec 2015 cardgame High Card Low Card Greedy 15/15
Dec 2015 haybales Counting Haybales Seg Tree, Lazy, Min Query & Sum Query 10/10
Jan 2016 fortmoo Fort Moo DP/Sliding Window 13/13
Jan 2016 mowing Mowing The Field 2D Range Tree 10/10
Feb 2016 balancing Load Balancing Binary Search, BIT 15/15
Feb 2016 fencedinplat Fenced In 10/10
Open 2016 262144 262144 DP 12/12
Dec 2016 team Team Building DP 9/9
Jan 2017 promote Promotion Counting BIT on preorder of tree 10/10
Jan 2017 tallbarn Building a Tall Barn Binary Search 12/12
Jan 2017 subrev Subsequence Reversal DP 10/10
Feb 2017 mincross Why Did The Cow Cross The Road Fenwick Tree 10/10
Feb 2017 nocross Why Did The Cow Cross The Road II DP, RMQ (Seg Tree) 10/10

Note: Code primarily written in C++.

You can’t perform that action at this time.