Check out the USACO Guide to get better at competitive programming!
Speed up compile times: https://codeforces.com/blog/entry/53909
g++ -std=c++11 /usr/include/path_to/bits/stdc++.h
Competitive Programming Solutions This repository contains solutions to various competitive programming problems.
Command to find problems solved:
find -type f -name "*.cpp" ! -name "*main*" -not -path "./cpbook-code/*" -not -path "./alphastar/*summer*/*" -not -path "./**/*game*/*" | wc -l
Note: Nothing below is kept up to date anymore!!
Solutions to USACO training and USACO contest problems.
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.2 The Perfect Stall Max Bipartite Matching 4.2.3 Job Processing Greedy 4.3.1 Buy Low, Buy Lower DP, BigInteger (less than + addition) 4.3.2 Street Race DFS, Set, Brute Force 4.3.3 Letter Game String permutation, brute force, map/set 4.4.1 Shuttle Puzzle Brute Force, BFS (Queue), Implementation 4.4.2 Pollutant Control Max Flow Min Cut, minimize removed edges 4.4.3 Frame Up All Topological Sorts 5.1.1 Fencing the Cows Simple Convex Hull 5.1.2 Starry Night Floodfill, Implementation 5.1.3 Musical Themes Sliding Window Iterative DP, Longest Repeating Non-Overlapping Substring, deltas 5.2.1 Snail Trail Brute Force, Implementation, Recursion 5.3.1 Milk Measuring DP, Optimization, Sliding Window 5.3.2 Window Area Implementation, Calculating overlapping rectangle area - Split rectangle into four parts 5.3.3 Network of Schools Min additional edges to form SCC 5.3.4 Big Barn Prefix Sums + Binary Search, doable with DP as well 5.4.1 Canada Tour DP 5.4.2 Character Recognition DP, Bit manipulation for Optimization/Pruning 5.4.3 TeleCowmunication Max Flow Min Cut, Split Nodes 5.5.1 Picture Line Sweep 5.5.2 Hidden Passwords String Processing 5.5.3 Two Five DP
Contest Date Problem ID Problem Name Solution Notes Feb 2018 reststops Rest Stops Greedy Feb 2019 revegetate The Great Revegetation Graph, DFS, Tricky
Contest Date Problem ID Problem Name Solution Notes Nov 2012 clumsy Clumsy Cows Greedy Nov 2012 distant Distant Pastures APSP, dijkstra Nov 2012 bbreeds Balanced Cow Breeds Same problem as Gold Dec 2012 crazy Crazy Fences Computational Geometry Dec 2012 wifi Wifi Setup DP Dec 2012 mroute Milk Routing Dijkstra Jan 2013 paint Painting the Fence Coordinate Compression, Store Deltas & Sweep Jan 2013 squares Square Overlap Sweep Jan 2013 invite Party Invitations precompute which groups each cow is in Feb 2013 perimeter Perimeter Optimized Floodfill Feb 2013 tractor Tractor Binary search for answer, dfs Feb 2013 msched Milk Scheduling Greedy Mar 2013 poker Poker Hands Greedy Mar 2013 painting Farm Painting Sweep Mar 2013 cowrun The Cow Run DP, same as gold Open 2013 gravity What's Up With Gravity? Dijkstra Open 2013 fuel Fuel Economy Greedy Open 2013 cruise Luxury River Cruise Find where sequence repeats Nov 2013 nocow Farmer John has no Large Brown Cow Solvable with a bit of math Nov 2013 crowded Crowded Cows Sweep, can use multiset instead of monotonic queue Nov 2013 pogocow Pogo-Cow DP, note that Bessie can go either direction Dec 2013 msched Milk Scheduling Greedy, sweep Dec 2013 vacation Vacation Planning Code is slightly modified from gold version, answer is unnecessarily complicated for silver Dec 2013 shuffle The Bessie Shuffle Repeated Squaring, Permutations, Composing functions/permutations Jan 2014 slowdown Bessie Slows Down Maintain two arrays, simulation Jan 2014 ccski Cross Country Skiing Prim's Jan 2014 recording Recording the Moolympics Greedy Feb 2014 auto Auto-complete Binary search Feb 2014 rblock Roadblock Dijkstra Feb 2014 scode Secret Code DP Mar 2014 irrigation Watering the Fields Kruskal/MST Mar 2014 lazy The Lazy Cow Rotate grid 45 degrees Mar 2014 mooomoo Mooo Moo DP Open 2014 fairphoto Fair Photography Sweep Open 2014 gpsduel Dueling GPSs Dijkstra Open 2014 odometer Odometer DP Construction Dec 2014 piggyback Piggy Back Shortest Path on three nodes Dec 2014 marathon Marathon DP Dec 2014 cowjog Cow Jog Sweep Jan 2015 stampede Stampede Sweep Jan 2015 cowroute Cow Routing Dijkstra Jan 2015 meeting Meeting Time DP Feb 2015 censor Censoring Rolling Hash Feb 2015 hopscotch Cow Hopscotch DP Feb 2015 superbull Superbull MST, Prim's O(V^2) Open 2015 bgm Bessie Goes Moo Parity Open 2015 trapped Trapped in the Haybales (Silver) Sort, Sweep Open 2015 buffet Bessie's Birthday Buffet
Contest Date Problem ID Problem Name Solution Notes Dec 2015 cardgame High Card Low Card (Gold) Greedy Dec 2015 feast Fruit Feast DP (Knapsack) Dec 2015 dream Bessie's Dream Dijkstra Jan 2016 angry Angry Cows Sweep/Greedy/DP, Binary Search (Optional) Jan 2016 radio Radio Contact DP Jan 2016 lightsout Lights Out Simulation, Coordinates, Brute Force, Implementation Feb 2016 cbarn Circular Barn Greedy Feb 2016 cbarn2 Circular Barn (Revisited) DP Feb 2016 fencedin Fenced In MST (Kruskal) Open 2016 split Splitting The Field Sweep Open 2016 closing Closing The Farm UFDS (Note: Runs really close to time limit) Open 2016 248 248 DP Dec 2016 moocast Moocast UFDS, brute force Dec 2016 checklist Cow Checklist DP Dec 2016 lasers Lasers and Mirrors BFS Jan 2017 bphoto Balanced Photo Fenwick Tree Jan 2017 hps Hoof, Paper, Scissors 3D DP Jan 2017 cownav Cow Navigation BFS Feb 2017 visitfj Why Did The Cow Cross The Road Dijkstra Feb 2017 nocross Why Did The Cow Cross The Road II DP Feb 2017 circlecross Why Did The Cow Cross The Road III Fenwick Tree (BIT) Open 2017 cownomics Bovine Genomics Rolling Hash Open 2017 art2 Modern Art 2 Calculate start/end points Dec 2017 piepie A Pie For A Pie BFS, binary search Dec 2017 barnpainting Barn Painting DP Dec 2017 hayfeast Haybale Feast Two Pointers Jan 2018 mootube MooTube UFDS Jan 2018 atlarge Cow At Large DFS/BFS Jan 2018 spainting Stamp Painting DP, recurrence Feb 2018 snowboots Snow Boots Sort, Doubly-Linked List Feb 2018 dirtraverse Directory Traversal DFS Feb 2018 taming Taming The Herd DP Open 2018 sort Out of Sorts BIT Open 2018 milkorder Milking Order Topological Sort (Lexicographically earliest) Open 2018 talent Talent Show Binary search for answer, DP Dec 2018 dining Fine Dining Dijkstra Dec 2018 cowpatibility Cowpatibility PIE Dec 2018 teamwork Teamwork DP Jan 2019 poetry Cow Poetry DP, power under mod, math Jan 2019 sleepy Sleepy Cow Sorting Fenwick Tree Jan 2019 shortcut Shortcut Dijkstra, find path Feb 2019 cowland Cow Land Tree Traversal Array, or alternatively Heavy-Light Decomposition Feb 2019 dishes Dishwashing Greedy (Also doable with Greedy + Binary Search ) Feb 2019 paintbarn Painting the Barn Geometry, Prefix Sums, Line Sweep Open 2019 balance Balancing Inversions
Old USACO Platinum (Gold): Contest Date Problem ID Problem Name Solution Notes Nov 2012 bbreeds Balanced Cow Breeds DP Nov 2012 cbs Concurrently Balanced Strings Prefix Sums Dec 2012 gangs Gangs of Istanbull/Cowstantinople Greedy Dec 2012 first First! trie, checking DAG for cycles Dec 2012 runaway Running Away From the Barn Jan 2013 lineup Cow Lineup sweep with two pointers Jan 2013 island Island Travels bfs Jan 2013 seating Seating Binary Tree, Lazy Propagation Feb 2013 partition Partitioning The Farm DP Feb 2013 taxi Taxi Min Cost Matching, calculate distance driven w/o cow Feb 2013 route Route Designing DP Mar 2013 cowrun The Cow Run DP Mar 2013 hillwalk Hill Walk Line sweep, find a way to order hills Nov 2013 nochange No Change DP, 2^k state Nov 2013 sight Line of Sight If two cows can see the same point on the silo, they can see each other Nov 2013 empty Empty Stalls Sweep Dec 2013 vacationgold Vacation Planning (Gold) Dijkstra Dec 2013 optmilk Optimal Milking Binary Tree Jan 2014 skicourse Building A Ski Course DP Jan 2014 skilevel Ski Course Rating Kruskal Feb 2014 rblock Roadblock Dijkstra Feb 2014 dec Cow Decathlon DP Mar 2014 sabotage Sabotage Binary search, 1D max sum Mar 2014 fcount Counting Friends Brute Force, greedily connect friends Dec 2014 guard Guard Mark DP Dec 2014 marathon Marathon Segment Tree Dec 2014 cowjog Cow Jog Longest Non-Increasing Subsequence Jan 2015 cowrect Cow Rectangles Sweep, assume we have to take one of the Holsteins Jan 2015 movie Moovie Mooving DP, bitmasking Open 2015 palpath Palindromic Paths DP Open 2015 trapped Trapped in the Haybales Sort haybales by weight Open 2015 buffet Bessie's Birthday Buffet DP
USACO Platinum (2015-now): Contest Date Problem ID Problem Name Solution Notes Dec 2015 maxflow Max Flow LCA, prefix sums Dec 2015 cardgame High Card Low Card Greedy Dec 2015 haybales Counting Haybales Seg Tree, Lazy, Min Query & Sum Query Jan 2016 fortmoo Fort Moo DP/Sliding Window Jan 2016 mowing Mowing The Field 2D Range Tree Feb 2016 balancing Load Balancing Binary Search, BIT Feb 2016 fencedinplat Fenced In Open 2016 262144 262144 DP Dec 2016 team Team Building DP Jan 2017 promote Promotion Counting BIT on preorder of tree Jan 2017 tallbarn Building a Tall Barn Binary Search Jan 2017 subrev Subsequence Reversal DP Feb 2017 mincross Why Did The Cow Cross The Road Fenwick Tree Feb 2017 nocross Why Did The Cow Cross The Road II DP, RMQ (Seg Tree) Feb 2017 friendcross Why Did The Cow Cross The Road III 2D Seg Tree Open 2017 art Modern Art Prefix Sums/Deltas Open 2017 grass Switch Grass MST, Sets, I/O Optimization Dec 2017 pushabox Push A Box Biconnected Components, BFS Dec 2017 greedy Greedy Gift Takers Binary Search, Prefix Sums Open 2018 disrupt Disruption Method 1: (Merging small to large, pool pointers method). Method 2: (LCA + Path Compression). Method 3: (HLD). Method 4: (2D Seg Tree, Graphically thinking) Dec 2018 balance Balance Beam Convex Hull / Visualizing Geometry Jan 2018 lifeguards Lifeguards DP (Note: Solution code is very sketchy and really shouldn't run in time) Feb 2018 newbarn New Barns Centroid Decomposition Jan 2019 redistricting Redistricting DP, Monotonic Queue Feb 2019 cowdate Cow Dating Two pointers, math Open 2019 treeboxes Tree Boxes LCA, Implementation, Interactive
Solutions to various Codeforces problems. List no longer updated!
Here is the complete solutions folder.
Problem ID Problem Name Solution Notes 321C C. Ciel the Commander Centroid Decomposition 342E E. Xenia and Tree Centroid Decomposition, LCA 383D D. Antimatter DP 497A A. Reorder The Array Multiset 762B B. USB vs PS/2 Sorting, Greedy 762E E. Radio Stations Segment Tree 809A A. Do you want a date? Math, power, mod 817D D. Imbalanced Array Stack, Sweep, Math 937A A. Olympiad Set 946D D. Timetable DP 989D D. A Shade of Moonlight Binary Search, Math 991B B. Getting an A Sorting 1012B B. Chemical table Bipartite Graph 1038C C. Gambling 1061D D. TV Shows Multiset, Greedy 1067B B. Multihedgehog 1095F F. Make it Connected UFDS 1098A A. Sum in the tree 1099F F. Cookies Fenwick Tree 1104A A. Splitting into digits brute force 1104B B. Game with string Stack 1104C C. Grid Game Ad Hoc 1104D D. Game with modulo binary search, math 1105A A. Salem and Sticks 1105B B. Zuhair and Strings 1105C C. Ayoub and Lost Array 1105D D. Kilani and the Game 1111A A. Superhero Transformation 1111C C. Creative Snap 1113A A. Sasha and His Trip Greedy 1113B B. Sasha and Magnetic Machines 1113C C. Sasha and a Bit of Relax 1113D D. Sasha and One More Name 1114D D. Flood Fill 1117E E. Decypher the String Math, string processing 1118E E. Yet Another Ball Problem Constructive Algorithms, Ad Hoc 1130A A. Be Positive Ad Hoc 1130B B. Two Cakes Greedy 1130C C. Connect Floodfill, Brute Force 1130D1 D. Toy Train (Simplified) Simulation 1130D2 D. Toy Train Math, Precomputation 1131D D. Gourmet Choice DAG, Detecting Cycles, Topo Sort 1132D D. Stressful Training Binary Search, Greedy, Implementation 1133F1 F1. Spanning Tree With Maximum Degree Greedy, UFDS, Kruskal 1133F2 F2. Spanning Tree With One Fixed Degree Greedy, UFDS, Kruskal, Construction 1137D D. Cooperative Game Math, Number Theory, Mods 1139E E. Maximize Mex Bipartite Graph, Flow 1141F1 F1. Same Sum Blocks (Easy) See 1141F2, though O(N^4) dp should also work 1141F2 F2. Same Sum Blocks (Hard) Prefix sums O(N^2) 1141G G. Privatization of Roads in Treeland Greedy, Implementation, DFS 1151A A. Maxim and Biology Brute Force 1151B B. Dima and a Bad XOR Brute Force, XOR (Note: Solution code is brute force/DP but a O(n*m) solution exists with observation) 1151C C. Problem for Nazar Math, Implementation 1151D D. Stas and the Queue at the Buffet Greedy, light math 1153A A. Serval and Bus Math 1153B B. Serval and Toy Bricks Greedy 1153C C. Serval and Parenthesis Sequence Greedy 1153D D. Serval and Rooted Tree Tree traversal, DP (ish) 1153E E. Serval and Snake Binary Search, Brute Force 1169D D. Good Triple Brute Force 1173A A. Nauuo and Votes Greedy 1173B B. Nauuo and Chess Greedy, Constructive Algorithms 1173C C. Nauuo and Cards Greedy 1173D D. Nauuo and Circle Combinatorics, DP, trees 1173E1 E1. Nauuo and Pictures (easy version) DP, probability, Modular Multiplicative Inverses 1176A A. Divide It Brute Force, Recursion 1176B B. Merge It Greedy 1176C C. Lose It Greedy 1176D D. Recover It multiset, prime generation, greedy 1176E E. Cover It Bicoloring (ish) 1181A A. Chunga-Changa 1181B B. Split a Number 1181C C. Flag 1181D D. Irrigation
International Olympiad in Informatics (IOI) Problem Name Solution Notes 2003 A. Trail Maintenance Union Find 2004 B. Hermes DP, Iterative, Sliding Window 2004 D. Empodia Read header of file, IDK why solution gets AC :P 2014 E. Friend Induction Trick
Solutions Folder
UVa Online Judge (Competitive Programming 3, Starred) Solutions to UVa Online Judge problems. Mostly starred problems from Competitive Programming 3.
Solutions Folder
Solutions to various Google Kick Start competitions.
Problem Name Solution Notes A - Even Digits Ad Hoc A - Lucky Dip Brute Force / Binary Search A - Scrambled Words Strings, implementation B - No Nine Digit DP (Alternatively, Ad Hoc)
Problem Name Solution Notes A - Training Sorting, Prefix Sums A - Parcels Multi-Source BFS, Manhattan Distance B - Building Palindromes Prefix Sums B - Energy Stones DP Knapsack, sorting B - Diverse Subarray Segment Tree
Solutions to various Google Code Jam competitions.
Round Problem Name Solution Notes 1A Waffle Choppers Prefix sums, greedy 1A Bit Party Binary Search 2 Falling Balls Implementation
Round Problem Name Solution Notes Qualification Foregone Solution Greedy Qualification You Can Go Your Own Way Greedy Qualification Cryptopangrams GCD, BigInteger, Math Qualification Dat Bae Interactive, similar strategy to CodeForces 1117E 1A Pylons Construction, Implementation 1A Golf Gophers Chinese Remainder Theorem 1B Manhattan Crepe Cart Sweep lines 1B Draupnir (Visible Set Only) Solving systems of equations (math) 1B Fair Fight Segment Tree, Binary Search
Solutions to CSES Problem Set .
Problem Name Solution Notes Weird Algorithm Simulation, careful with integer overflow Missing Number Basic Arrays Repetitions Maximum length substring with same characters Increasing Array Greedy Permutations Ad Hoc, Construction
Solutions Folder