README.md

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