Solutions to various competitive programming problems I've solved. Check out the USACO Guide to improve at competitive programming!
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
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 |
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 |
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 |
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 to UVa Online Judge problems. Mostly starred problems from Competitive Programming 3.
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 |