Thecodingwizard Competitive Programming Save

Solutions to various competitive programming problems I've solved. Check out the USACO Guide to improve at competitive programming!

Project README

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!!

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.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

Silver USACO Contests:

Contest Date Problem ID Problem Name Solution Notes
Feb 2018 reststops Rest Stops Greedy
Feb 2019 revegetate The Great Revegetation Graph, DFS, Tricky

Gold USACO Contests:

Old USACO Gold (Silver):

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

USACO Gold (2015-now)

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

Platinum USACO Contests:

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

Codeforces

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

Google Kick Start

Solutions to various Google Kick Start competitions.

Kick Start 2018

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)

Kick Start 2019

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

Google Code Jam

Solutions to various Google Code Jam competitions.

Code Jam 2018

Round Problem Name Solution Notes
1A Waffle Choppers Prefix sums, greedy
1A Bit Party Binary Search
2 Falling Balls Implementation

Code Jam 2019

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

CSES

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

Open Source Agenda is not affiliated with "Thecodingwizard Competitive Programming" Project. README Source: thecodingwizard/competitive-programming

Open Source Agenda Badge

Open Source Agenda Rating