weekly-algorithm-sheet

https://docs.google.com/spreadsheets/d/1hM7PbKN9GULMXMk_Vjf9HlFVROBp85VVwf3F0p4BZ_0/edit#gid=1508691920
Source : progvar.fun

GRAPH ALGORITHMS:			

Basic Implementation																
																			
1	HR Handshake															
2	CF330B - Road Construction															
3	CF574B - Bear and Three Musketeers															
4	CF292B - Network Topology															
5	CF402C - Searching for Graph								New Cpncept : Laman Graph Constructive Algorithm							
6	CF990D - Graph And Its Complement							Nice Construction							
7	CF22C - System Administrator															
9	ABC054 C - One-stroke Path								Simple Rec DFS with Bit masking							
10	ABC061 B - Counting Roads								Very Easy							
11	ABC073 D - joisino's travel								Excellent!! Steiner Tree: Floyd Warshall + BITMASK DFS							
12	ABC110 C - String Transformation							Very Very Nice Constructive Proof(Invariant based.) 							



Tree	Traversal															

1	HR Tree: Preorder Traversal															
2	HR Tree: Postorder Traversal															
3	HR Tree: Inorder Traversal															
4	HR Tree: Level Order Traversal															
5	CF115A - Party															
7	CF1244D - Paint the Tree							Easy DP on Trees							
8	CF61D - Eternal Victory								Easy 							
9	CF34D - Road Map															
10	CF14D - Two Paths								Excellent Example for Rerooting In-Out DP Technique							
11	UVa 12347 Binary Search Tree															
12	CF29D - Ant on the Tree								New Idea : DFS twice. Kinda similar to Morris Traversal							
13	ABC070 D - Transit Tree Path							Good Idea							
14	ABC126 D - Even Relation							Easy coloring proof							
15	ABC146 D - Coloring Edges on Tree						Good coloring problem . V. Easy 							
16	ABC148 F - Playing Tag on Tree							V. Good Optimal Strategy Game							




DFS	Connectivity	Cycle-Finding														

1	CF500A - New Year Transportation						V. Easy							
2	HR Journey to the Moon															
3	CF771A - Bear and Friendship Condition						Clique or Not ?  Complete Graph							
4	CF1263D - Secret Passwords															
5	CF500B - New Year Permutation															
6	CF475B - Strongly Connected City						Easy but Nice Problem							
7	UVa 11690 Money Matters								Easy But Good for practise							
8	CF177C2 - Party									DSU							
11	ABC075 C - Bridge								Bridges & Articulation Points Crystal Clear Concept							
12	ABC126 E - 1 or 2														
13	ABC142 F - Pure									Cool BFS with min Cycle.							
14	ABC157 D - Friend Suggestions							Another Good DSU							
15	ABC049 D - 連結 / Connectivity						      Excellent Trick! Intersection of Union Find Algorithm in O(1)							



5. Depth-First Search (Tutorial on CP Algorithms)																
6. Search for Connected Components in a Graph (Tutorial on CP Algorithms)																
7. Checking a Graph for Acyclicity and Finding a Cycle in O(M) (Tutorial on CP Algorithms)																

BFS	Unweighted SP															

1	HR Breadth First Search: Shortest Reach															
2	HR Snakes and Ladders: The Quickest Way Up															
3	CF1037D - Valid BFS?								One more trick with Sorting Adjacency list							
4	CF601A - The Two Routes								Shortest Cycle in a directed Graph							
5	CF1205B - Shortest Cycle							Very Nice: Shortest Cycle in a undirected graph							
6	CF689B - Mike and Shortcuts															
7	CF543B - Destroying Roads							Good Problem : LCA inspired.							
8	CF877D - Olya and Energy Drinks							Excellent Optimization over Simple BFS. Prune the uncessary queue update.							
9	HR Rust & Murderer								Modified BFS for Complement of Sparse Graph							
10	CF59E - Shortest Path								Excellent BFS Variant: Queueing Vector and its Parent.							
12	ABC132 E - Hopscotch Addict							Easy Variant of BFS							
13	ABC168 D - .. (Double Dots)							Simple Straight-foreward BFS							


Grid-Graphs																

1	CF377A - Maze								Easy Troll Question							
2	HR Count Luck								Easy Question							
3	CF510B - Fox And Two Dots						Straight Foreward							
4	HR KnightL on a Chessboard						Easy?? But is O(1) there?							
5	CF598D - Igor In the Museum						Easy							
6	CF540C - Ice Cave							Easy							
7	CF329B - Biridian Forest															
10	CF585B - Phillip and Trains						V.Good							



BiPartite Graph																

2	CF217A - Ice Skating															
3	CF277A - Learning Languages						Biparitite tranformation trick!!							
4	CF862B - Mahmoud and Ehab and the bipartiteness															
6	CF1012B - Chemical table															
10	CC FILLMTR - Fill The Matrix						Nice Bipartite Concept							
11	ABC131 F - Must Be Rectangular!						Excellent Idea: Variant of Ice-Skating. Walking along the grid....							
12	https://codeforces.com/contest/1594/problem/D				Bipartite, Nice concept. Think as undirected graphs!!							

Topological Sort																

2	CF510C - Fox And Names															
3	CF501C - Misha and Forest															
5	CF825E - Minimal Labels							Very Imp Concept: Minimum Topological Labelling.							
6	CF909E - Coprocessor							Kahn with Exchange Argument							
7	SPOJ- Toposort															



Topological Sorting (Tutorial on CP Algorithms)																


Union-Find									Trick: For pure delete: Reverse and use DSU							

1	HR Merging Communities															
3	CF722C - Destroying Array						Looks like dynamic connectivity but tricked by reverse DSU							
4	CF371D - Vessels															
7	ABC120 D - Decayed Bridges						Reverse DSU Trick!							


Disjoint-Set Union (Tutorial on CP Algorithms)																
Union-Find (Video Lectures from Princeton on Coursera)																


Minimum Spanning Trees																

1	HR Roads and Libraries															
4	CF1245D - Shichikuji and Power Grid					Excellent problem on Prim's algorithm							
7	CF1081D - Maximum Distance						Very Nice Problem on Kruskal Algorithm							
8	CF17B - Hierarchy															
10	ABC065 D - Built?							Dense->Sparse MST Use Kruskal							


Directed Acyclic Graph-SP																

1	CF721C - Journey															
2	HR Kingdom Connectivity							Extremely instructive Graph problem'							
3	CF30C - Shooting Gallery						Nice combo of dp + probabilities. 					
4	CF793D - Presents in Bankopolis						Excellent idea for Interval DP. Hard Problem							
5	ABC139 E - League							Outstanding use of Kahn algorithm with edge-transformed graph							


Shortest Path-Single Source																

1	CF20C - Dijkstra?							Straightforeward							
2	HR Dijkstra: Shortest Reach 2						Straightforeward							
3	CF707B - Bakery								Easy, Think easily, Not a dijkstra							
4	CF449B - Jzzhu and Cities						Modified Dijkstra: finding count of all optimal path leading to a vertex.							
6	CF916C - Jamie and Interesting Graph					Constructive Proof: Easy.							
7	HR Jack goes to Rapture							Modified dijkstras: Exposes the idea of greedy when dist(x) <= dist(y) if |x| < |y|							
8	CC MINWALK - Minimum Cost Walk						Do Dijkstra 3 times							
10	CC REVERSE - Chef and Reversing						Modified Dijkstra							
11	ABC164 E - Two Currencies						Modified Dijkstra: Best Problem to learn the idea behind algorithm. dynamic approach							
12	ABC170 F - Pond Skater							Olga and Energy Drinks with larger constraints. use Map							
13	ABC175 F - Making Palindrome						Dijkstra: How dijkstra can be used to solve optimality problems? Excellent!!!							
14	ARC061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip			Tricky 0/1 BFS transformation. Use virtual vertices.							


0/1 BFS																

2	SPOJ KATHTHI - KATHTHI							Easy 0/1 bfs							
4	CF100625J - Jailbreak							Excellent idea. Popular problem							



0-1 BFS (Tutorial on CP Algorithms)																
0-1 BFS [Tutorial] (Codeforces Blog Post)																



Single Source with Negative Weights																

8	CC AVGSHORT - Short in Average						Bellman ford: Standard, but excellent idea!!							
9	ABC061 D - Score Attack							Easy: Only remember that negative cycle has to contain the src and dest vertex							



Shortest Path with All-Pairs																

1	CC ACM14KG3 - Discount on crackers					Easy Floyd Warshall : Transitive Closure!							
2	CF295B - Greg and Graph							Standard when you know FW well.							
4	CF1204C - Anna, Svyatoslav and Maps					Good FW application							
5	CF25C - Roads in Berland						FW like, Can try virtual vertex approach							
7	ABC051 D - Candidates of No Shortest Paths				Easy FW Application							
8	ABC079 D - Wall								Easy FW. FW=BF for dense graph							







DYNAMIC PROGRAMMING			Classic DP								Comments								

1	HR The Maximum Subarray							Kadane's Algorithm, Easy Peasy							
2	UVa 10405 Longest Common Subsequence					Easy DP on Subsequence								
3	UVa 10003 Cutting Sticks						Matrix Chain Multiplication 								
4	SPOJ EDIST - Edit distance						Edit Distance - Easy Implemetation							
5	UVa 357 Let Me Count The Ways						Coin Change Problem - Linear Space Complexity. 						
6	UVa 111 History Grading							LIS is equivalent to LCS, however LIS can be O(nlogn)				 			
7	SPOJ FARIDA - Princess Farida						Inclusion Exclusion DP - Easy Peasy							
8	UVa 10130 SuperSale							Knapsack 0/1 with multiple queries							
9	UVa 562 Dividing coins							Min Sum Partition : Boolean DP 								
10	CF416B - Art Union							Simple DP. Can be space reduced?							
11	UVa 10304 Optimal Binary Search Tree					Nice application of Matrix Chain Multiplication 				 			
12	ABC079 B - Lucas Number							BInary Expo for Linear Recurrences							


Pattern DP																

1	CF455A - Boredom							Dp on the range of the values. 			
2	CF698A - Vacations							Easy DP								
3	CF706C - Hard problem							Easy DP with String Comparisons Use 1 << 62 for INF in LL 				 			
4	CF467C - George and Job							Easy DP with Prefix Sum						
5	SPOJ MIXTURES - Mixtures						Easy Matrix Multiplication DP Trick 							
6	CF5C - Longest Regular Bracket Sequence					DP with Stack, LBS DP				
6.5	HR-Balanced Sequence							Interesting Application of MCP				
7	CF225C - Barcode							Good boolean matrix DP with Precalc				
8	CF711C - Coloring Trees							Nice DP problem Adhoc DP				
9	CF855B - Marvolo Gaunt's Ring						Easy DP 					
10	CF626B - Cards								Constructive Problem : Easy						
11	CF607B - Zuma								Excellent Application of MCP, DP on Range				
12	CF814C - An impassioned circulation of affection			Sliding Window O(N) solution								
13	CF82D - Two out of Three						Very Nice DP problem with Solution Construction, Structure Hyp				 			
14	ABC054 D - Mixing Experiment						Forward and Backward DP examples. Easy								
15	ABC125 D - Flipping Signs						Easy Mathematical Solution Exist								
16      CF1155D - Beautiful Array						Kadane's Algorithm: Tweak needed. DP on the structure

Dynamic Programming (Tutorial from NOI.PH IOI Training 2018)																




Pre-Caculation	Double DP															

1	CF946D - Timetable							Very Good Problem with Two Precalculated Dp+Prefix Sum				Mar 10				
2	CF75D - Big Maximum Sum							Nice Application of Max Subarray Sum								
3	CF1498- Planar Reflection						Very Very Nice Prefix DP Problem							


Presorting DP																

1	CF864E - Fire								Very Cool Exchange Argument DP 								
2	CODE FESTIVAL 2017 Final						Standard Exchange Argument DP								
3	ABC145 E - All-you-can-eat						Basic Sorting DP							
4	ABC163 E - Active Infants						Excellent Example of EA with MCP						
5	CF101933A - Altruistic Amphibians					Hard DP problem. Hint : MLE in using LONG LONG.					


Solution Construction																

1	CF4D - Mysterious Present							Easy LIS problem 								
2	CF2B - The least round way							Very Tricky Matrix DP Path Problem						
3	HR Password Cracker								Word Break O(ns) solution exist. Iterate from the last greedily. 
4	HR Arithmetic Expressions							Nice DP with Math trick and Soln construction				 			
5	CF82D - Two out of Three							Already done in pattern DP 							
6	CF56D - Changing a String							Levenstein Distance with construction						
8	CF119C - Education Reform							Cool DP state var reduction trick						
10	ABC118 D - Match Matching			 				Very Important DP problem							
11	ARC081 E - Don't Be a Subsequence						Nice Tick with NEXT function						





Digit DP																

1	CF1036C - Classy Numbers							 Loose branches can be calculated in O(1) time.				 				
2	CF204A - Little Elephant and Interval						 Nice Math & loose branch O(1) time yes 				 			
3	CF914C - Travelling Salesman and Special Numbers				 Builtin_popcount Precount DP							
4	CF628D - Magic Numbers							 	 Both Left_Tight & Right_Tight								
9	CC DIGIMU - Logan and DIGIT IMMUNE numbers					 Very Nice Problem with Another LCM trick 				 			
10	CC WORKCHEF - Chef and special numbers						 Nice Problem with Cool LCM trick & Bitmasking				 				
12	HR Count Pairs: Used							 	 Hard : Digit DP on Pairs of Integers. Very Nice!				 			
13	ABC154 E - Almost Everywhere Zero						 Easy Math Digit DP problem							
14	F-Coincidence							 		 Very Imp: DP on Digits for Integer Pairs				 			

DP on Trees																

1	HR Even Tree									 Very Nice Parity Trick							
2	CF580C - Kefa and Park								 Very Easy Bottom Up Tree DP								
3	HR Cut the Tree									 Basic DP on Trees						
4	CF429A - Xor-tree								 Easy Tree with Propagation Tree Concept				 			
5	CF219D - Choosing Capital for Treeland						 Nice Application Rerooting Technique	
6	CF461B - Appleman and Tree							 Hard DP on Trees, Tricky DP structure & cool combine trick			 			
7	HR Kingdom Division								 Very Nice DP on Tree Coloring. Caution: MOD				 			
8	CF814D - An overnight dance in discotheque					 Dp on Trees and Greedy Geometry	
9	CF855C - Helga Hufflepuff's Cup							 Very Tricky DP on Tree with further dp optimization in combine phase				 			
14	HR Fanciful Fruit								 Hard Tree with Math Problem						

			BITMASKING DYNAMIC PROGRAMMING 													


Bitmasking																

1	CF580D - Kefa and Dishes							Easy Bitmasking								
2	SPOJ ASSIGN - Assignments							Hungarian Assigment Problem Variant								
4	CF401D - Roman and Numbers							Iterative Approach								
5	CF895C - Square Subsets							        Tough Implementation of Bitmask over Primes								
6	CF16E - Fish									Very Nice 								
7	CF8C - Looking for Order							Important to Practice								
8	CF417D - Cunning Gena								Very Very Important for Structural DP Ideas								
9	CC WORKCHEF - Chef and special numbers						Nice Problem with Cool LCM trick & Bitmasking								
10	ABC142 E - Get Everything							Easy Iterative Version								
11	CF1245F - Daniel and Spring Cleaning						Digit DP								



Profile DP																

12	UVa 10918 Tri Tiling								Broken Paraquet								




BITMASK DP																
16	Felicity's Big Secret Revealed															
17	HIST2 - Histogram															
22	Little Poney and harmony Chest							Excellent Problem with Submasking & Bitmasking over Primes								



Topics to be Covered : 																

DIFFERENCE ARRAY																

Problems : 																

1	Greg and Array															
2	Karen and Coffee															
3	Little Girl and Maximum Sum															
4	Encrypting Messages															

STRING HASHING																

1	https://codeforces.com/blog/entry/13741															
2	https://codeforces.com/blog/entry/60445															
3	https://codeforces.com/blog/entry/60442															

	Read other blogs for String Hashing Algorithms															

	Rabin Karp															

	https://codeforces.com/blog/entry/88474															
	https://codeforces.com/blog/entry/4710															
	https://codeforces.com/blog/entry/64860															

CHINESE REMAINDER THEOREM	

	https://codeforces.com/blog/entry/61290																										


ADVANCED ALGORITHMIC PROBLEMS																


1	PHONELST	https://www.spoj.com/problems/PHONELST/					Easy Trie Implementation Based									
2	MAXXOR	https://www.hackerrank.com/challenges/maximum-xor/editorial			Classic Max Xor Trie Implementation									
3	MAXXORSUB										Maximum Xor Subarray, Use above trick + storing xor[1....n]									
4	SUBXOR	https://www.spoj.com/problems/SUBXOR/						Bit Trie: Xor subarray less k, wasted time in indexing, stupid bug!!									



RANGE QUERIES																




1	https://codeforces.com/contest/1567/problem/E				2200		Standard implementation based									
2	https://codeforces.com/contest/446/problem/C				2400		Classic Lazy Propagation technique									
3	https://codeforces.com/problemset/problem/474/F				2100		Standard Segment Tree									
4	http://codeforces.com/problemset/problem/369/E				2200		Difference Array trick gives TLE, Used adhoc approach + Fenwick Tree 									
6	https://atcoder.jp/contests/abc185/tasks/abc185_f			1000		Straight-foreward Fenwick Tree									
7	https://atcoder.jp/contests/abc186/tasks/abc186_f			2200		Sorting + Fenwick Tree, Must DO									
8	https://codeforces.com/problemset/problem/380/C				2000		Great Seg Tree: Classical, POC is cool! in github									
9	https://codeforces.com/contest/339/problem/D				1700		Straight-foreward Segment Tree									
10	https://codeforces.com/contest/356/problem/A				1500		Easy Vector, Not really seg tree									
11	https://codeforces.com/contest/459/problem/D				1800		Fenwick + Order Stats + Sorting. Classical + Coordinate Compresison									
12	https://codeforces.com/contest/61/problem/E				1900		Fenwick Tree									
13	https://codeforces.com/contest/292/problem/E				1900		Nice, Lazy Propagation									
14	https://codeforces.com/contest/501/problem/D				2000	 	Very Nice, Factoriadic Concept+PBDS									
17	https://codeforces.com/contest/540/problem/E				2100		Inversion Count + PBDS + Coord Compression									
27	https://codeforces.com/contest/597/problem/C				1900		Classical Dynamic Programming+Fenwick Tree									
29	https://codeforces.com/contest/482/problem/B				1800		TLE using Seg Tree, Very tight limit, Use pure difference array for offline range sum and range query									
30	https://codeforces.com/contest/242/problem/E				2000		Classic Lazy Propagation: Multiple Seg Tree Application + Cool bit trick									
31	https://codeforces.com/contest/383/problem/C				2000		Propagating Tree. V,V,Nice: Euler Tour Technique									
34	https://codeforces.com/contest/629/problem/D				2000		Nice FW+DP, Pitfall: if strictly greater then use custom sorts accordingly. 	Nice FW+DP, Pitfall: if strictly greater then use custom sorts accordingly. 	Nice FW+DP, Pitfall: if strictly greater then use custom sorts accordingly. 							


FENWICK TREES																



39	http://codeforces.com/contest/102/problem/D 				1700		Fenwick Tree+Coordinate Compression+DP									
41	http://codeforces.com/contest/61/problem/E 				1900		Fenwick Tree Idea: Very Classical									
53	https://codeforces.com/contest/1535/problem/D				1900		Cool: Another way of implementation of seg tree in case intermediate node is given									
54	https://www.spoj.com/problems/POSTERS/					1900		Coordinate Compression on Seg Tree + Lazy Propagation, Cool Exercise									


BINARY LIFTING																

57	https://codeforces.com/contest/609/problem/E				2000		V.V.Nice: Binary Lifting + DP + LCA. Excellent Idea									


	



SPOJ Range Query Sprint!!																		

10	https://www.spoj.com/problems/ADATREE/						Merge Sort Tree												
11	https://www.spoj.com/problems/SEGSQRSS/						Lazy Propagation												
15	https://www.spoj.com/problems/FREQUENT/						Classic Combine Segment Tree												
16	https://www.spoj.com/problems/MKTHNUM/						Merge Sort Tree												
19	https://www.spoj.com/problems/ANDROUND/						Seg Tree												
20	https://www.spoj.com/problems/DQUERY/						Interesting Offline Idea for counting distinct in a subsequence												
22	https://www.spoj.com/problems/MATSUM/						Easy implementation of segment tree												
23	https://www.spoj.com/problems/GSS5/						Tough Classical Seg Tree problem