README.md

This was my practice run for ICPC. There are more than 250 accepted solutions listed here. I have also added tags for some of the problems.

• At first try to come up with a solution by yourself.
• If you can't then read some article on the associated tags and try again.
• If you still can't then you proceed to the solution. Try to understand what is going on. Then try your own approach.

The CSES problems can be found here: https://cses.fi/problemset/list/ This set has some classic problems.

Milestones:

• 25/11/2021: Solved all Introductory Problems
• 30/11/2021: Solved all Tree Problems
• 29/12/2021: Solved 100th Problem
• 05/05/2022: Solved 150th Problem
• 04/10/2022: Solved all Geometry Problems
• 05/12/2022: Solved 200th Problem
• 06/11/2023: Solved all Range Query Problems
• 11/11/2023: Solved 250th Problem
• 03/12/2023: Solved all Sorting and Searching Problems

Introductory Problems

Status	Name	Tags	Link
✔	Weird Algorithm		Code
✔	Missing Number		Code
✔	Repetitions		Code
✔	Increasing Array		Code
✔	Permutations		Code
✔	Number Spiral		Code
✔	Two Knights		Code
✔	Two Sets		Code
✔	Bit Strings		Code
✔	Trailing Zeros		Code
✔	Coin Piles		Code
✔	Palindrome Reorder		Code
✔	Gray Code		Code
✔	Tower of Hanoi		Code
✔	Creating Strings		Code
✔	Apple Division		Code
✔	Chessboard and Queens		Code
✔	Digit Queries		Code
✔	Grid Paths		Code

Sorting and Searching

Status	Name	Tags	Link
✔	Distinct Numbers		Code
✔	Apartments		Code
✔	Ferris Wheel		Code
✔	Concert Tickets		Code
✔	Restaurant Customers		Code
✔	Movie Festival		Code
✔	Sum of Two Values		Code
✔	Maximum Subarray Sum		Code
✔	Stick Lengths		Code
✔	Missing Coin Sum		Code
✔	Collecting Numbers		Code
✔	Collecting Numbers II		Code
✔	Playlist		Code
✔	Towers		Code
✔	Traffic Lights		Code
✔	Josephus Problem I		Code
✔	Josephus Problem II	OST	Code
✔	Nested Ranges Check		Code
✔	Nested Ranges Count	Point Update Range Sum	Code
✔	Room Allocation		Code
✔	Factory Machines		Code
✔	Tasks and Deadlines		Code
✔	Reading Books		Code
✔	Sum of Three Values		Code
✔	Sum of Four Values		Code
✔	Nearest Smaller Values		Code
✔	Subarray Sums I		Code
✔	Subarray Sums II		Code
✔	Subarray Divisibility		Code
✔	Subarray Distinct Values	Two pointers Sliding Window	Code
✔	Array Division		Code
✔	Sliding Median		Code
✔	Sliding Cost	OST Point Update Range Sum	Code
✔	Movie Festival II	Greedy Scheduling Binary Search	Code
✔	Maximum Subarray Sum II		Code

Dynamic Programming

Status	Name	Tags	Link
✔	Dice Combinations	Coin change DP	Code
✔	Minimizing Coins	Coin change DP	Code
✔	Coin Combinations I	Coin change DP	Code
✔	Coin Combinations II	Coin change DP	Code
✔	Removing Digits		Code
✔	Grid Paths		Code
✔	Book Shop		Code
✔	Array Description		Code
✔	Counting Towers		Code
✔	Edit Distance		Code
✔	Rectangle Cutting		Code
✔	Money Sums		Code
✔	Removal Game		Code
✔	Two Sets II	Knapsack DP	Code
✔	Increasing Subsequence	LIS	Code
✔	Projects		Code
	Elevator Rides		Code
✔	Counting Tilings	Broken Profile DP Bitmask	Code
✔	Counting Numbers	Digit Dp	Code

Graph Algorithms

Status	Name	Tags	Link
✔	Counting Rooms	BFS	Code
✔	Labyrinth	BFS	Code
✔	Building Roads	BFS DFS Forest Counting	Code
✔	Message Route	BFS	Code
✔	Building Teams	Bicoloring DFS	Code
✔	Round Trip	Cycle in undirected graph DFS	Code
✔	Monsters	BFS	Code
✔	Shortest Routes I	Single Source Shortest Path Dijkstra	Code
✔	Shortest Routes II	All Pair Shortes Path Floyd Warshall	Code
✔	High Score	Single Source Shortest Path Bellman Ford	Code
✔	Flight Discount	Single Source Shortest Path Dijkstra	Code
✔	Cycle Finding	Negative Cycle Bellman Ford	Code
	Flight Routes		Code
✔	Round Trip II	DFS Cycle in directed graph	Code
✔	Course Schedule	Topological Sort	Code
✔	Longest Flight Route	Topological Sort DP	Code
✔	Game Routes	Topological Sort DP	Code
✔	Investigation	Dijkstra	Code
✔	Planets Queries I	Binary Lifting	Code
	Planets Queries II		Code
✔	Planets Cycles	DFS	Code
✔	Road Reparation	Minimum Spanning Tree Kruskal	Code
✔	Road Construction	DSU	Code
✔	Flight Routes Check	Strongly Connected Components	Code
✔	Planets and Kingdoms	Strongly Connected Components	Code
✔	Giant Pizza	2-SAT	Code
✔	Coin Collector	Condensation Graph Topological Sort DP	Code
✔	Mail Delivery	Euler Tour - Undirected	Code
	De Bruijn Sequence		Code
✔	Teleporters Path	Euler Path - Directed	Code
✔	Hamiltonian Flights	Hamiltonian Path Bitmask DP	Code
✔	Knight's Tour	Hamiltonian Path Heuristics	Code
✔	Download Speed	Max Flow Min Cut Push Relabel Dinic	Code
✔	Police Chase	Max Flow Min Cut Push Relabel	Code
✔	School Dance	Max Flow``Bipartite Matching Hopkroft Carp	Code
✔	Distinct Routes	Max Flow Dinic Path reconstruction	Code

Range Queries

Status	Name	Tags	Link
✔	Static Range Sum Queries		Code
✔	Static Range Minimum Queries		Code
✔	Dynamic Range Sum Queries		Code
✔	Dynamic Range Minimum Queries		Code
✔	Range Xor Queries		Code
✔	Range Update Queries		Code
✔	Forest Queries		Code
✔	Hotel Queries		Code
✔	List Removals		Code
✔	Salary Queries		Code
✔	Prefix Sum Queries		Code
✔	Pizzeria Queries		Code
✔	Subarray Sum Queries		Code
✔	Distinct Values Queries		Code
✔	Increasing Array Queries	Segment tree Tree walking	Code
✔	Forest Queries II		Code
✔	Range Updates and Sums		Code
✔	Polynomial Queries	Lazy Segment Tree	Code
✔	Range Queries and Copies	Persistent Segment Tree	Code

Tree Algorithms

Status	Name	Tags	Link
✔	Subordinates	Subtree DP	Code
✔	Tree Matching	Tree DP	Code
✔	Tree Diameter	Tree Diameter	Code
✔	Tree Distances I	Tree Diameter	Code
✔	Tree Distances II	Tree Rerooting DP	Code
✔	Company Queries I	Binary Lifting	Code
✔	Company Queries II	LCA	Code
✔	Distance Queries	LCA	Code
✔	Counting Paths	HLD	Code
✔	Subtree Queries	HLD	Code
✔	Path Queries	HLD	Code
✔	Path Queries II	HLD	Code
✔	Distinct Colors	MO on Tree / Sack Small to Large	Code Code
✔	Finding a Centroid	Centroid	Code
✔	Fixed-Length Paths I	Centroid Decomposition	Code
✔	Fixed-Length Paths II	Centroid Decomposition	Code

Mathematics

Status	Name	Tags	Link
✔	Josephus Queries		Code
✔	Exponentiation		Code
✔	Exponentiation II		Code
✔	Counting Divisors		Code
✔	Common Divisors		Code
✔	Sum of Divisors		Code
✔	Divisor Analysis		Code
✔	Prime Multiples		Code
✔	Counting Coprime Pairs		Code
✔	Binomial Coefficients		Code
✔	Creating Strings II		Code
✔	Distributing Apples		Code
✔	Christmas Party		Code
✔	Bracket Sequences I		Code
✔	Bracket Sequences II		Code
✔	Counting Necklaces		Code
✔	Counting Grids		Code
✔	Fibonacci Numbers		Code
✔	Throwing Dice		Code
✔	Graph Paths I		Code
✔	Graph Paths II		Code
✔	Dice Probability		Code
	Moving Robots		Code
✔	Candy Lottery	Expected Value	Code
	Inversion Probability		Code
✔	Stick Game		Code
✔	Nim Game I		Code
✔	Nim Game II		Code
✔	Stair Game		Code
✔	Grundy's Game		Code
✔	Another Game		Code

String Algorithms

Status	Name	Tags	Link
✔	Word Combinations	Trie DP	Code
✔	String Matching	Suffix array / Hashing	Code
✔	Finding Borders	Z function Prefix function / Hashing	Code
✔	Finding Periods	Z function Prefix function / Hashing	Code
✔	Minimal Rotation	Suffix Automata	Code
✔	Longest Palindrome	Manacher	Code
	Required Substring		Code
✔	Palindrome Queries	Range Sum Hashing	Code
✔	Finding Patterns		Code
✔	Counting Patterns		Code
✔	Pattern Positions		Code
✔	Distinct Substrings		Code
✔	Repeating Substring	Hashing Binary Search	Code
✔	String Functions		Code
✔	Substring Order I		Code
✔	Substring Order II		Code
✔	Substring Distribution	Suffix Array Longest Common Prefix	Code

Geometry

Status	Name	Tags	Link
✔	Point Location Test		Code
✔	Line Segment Intersection		Code
✔	Polygon Area		Code
✔	Point in Polygon		Code
✔	Polygon Lattice Points		Code
✔	Minimum Euclidean Distance		Code
✔	Convex Hull		Code

Advanced Techniques

Status	Name	Tags	Link
✔	Meet in the Middle		Code
✔	Hamming Distance		Code
✔	Beautiful Subgrids	Bitset	Code
✔	Reachable Nodes		Code
✔	Reachability Queries		Code
✔	Cut and Paste	Implicit Treap	Code
✔	Substring Reversals	Implicit Treap	Code
✔	Reversals and Sums	Implicit Treap	Code
✔	Necessary Roads	Bridges	Code
✔	Necessary Cities	Articulation Points	Code
	Eulerian Subgraphs		Code
✔	Monster Game I	DP Convex Hull Optimization	Code
✔	Monster Game II	DP Convex Hull Optimization	Code
✔	Subarray Squares	DP Convex Hull Optimization	Code
	Houses and Schools		Code
✔	Knuth Division	DP Knuth Optimization	Code
✔	Apples and Bananas	FFT	Code
✔	One Bit Positions	FFT	Code
✔	Signal Processing	FFT	Code
✔	New Roads Queries	HLD	Code
✔	Dynamic Connectivity	Dynamic DSU	Code
✔	Parcel Delivery	Max Flow Min Cost Fixed flow	Code
✔	Task Assignment	Max Flow Min Cost	Code
✔	Distinct Routes II	Max Flow Min Cost Path reconstruction	Code

Additional Problems

Status	Name	Tags	Link
✔	Shortest Subsequence		Code
✔	Counting Bits		Code
✔	Swap Game		Code
✔	Prüfer Code	Prüfer Code	Code
✔	Acyclic Graph Edges		Code
✔	Strongly Connected Edges	Bridge	Code
	Even Outdegree Edges		Code
✔	Multiplication Table	Binary Search Harmonic Progression	Code
✔	Advertisement	Segment Tree	Code
✔	Special Substrings	Constructive Hashing	Code
	Permutation Inversions		Code
✔	Maximum Xor Subarray	Trie Divide and Conquer	Code
✔	Movie Festival Queries	Greedy Scheduling RMQ Binary Lifting	Code
✔	Chess Tournament	Greedy	Code
✔	Tree Traversals		Code
✔	Network Renovation	Euler Tour	Code
✔	Graph Girth	BFS Tree	Code
✔	Intersection Points	Range Query with Sweep Line	Code
✔	Inverse Inversions		Code
	Monotone Subsequences		Code
	String Reorder		Code
	Stack Weights		Code
	Pyramid Array		Code
✔	Increasing Subsequence II		Code
✔	String Removals	DP Cumulative sum	Code
✔	Bit Inversions		Code
✔	Xor Pyramid		Code
✔	Writing Numbers		Code
✔	String Transform	Inverse Burrows Wheeler Transform	Code
	Letter Pair Move Game		Code
✔	Maximum Building I	Segment Tree	Code
	Sorting Methods		Code
✔	Cyclic Array	Binary Search Greedy	Code
	List of Sums		Code
	Increasing Array II		Code
	Food Division		Code
✔	Bit Problem	SOS DP	Code
	Swap Round Sorting		Code
	Binary Subsequences		Code
✔	Tree Isomorphism I	Tree Isomorphism rooted	Code
✔	Counting Sequences	Inclusion Exclusion Principle	Code
✔	Critical Cities	Dominator Tree	Code
✔	School Excursion	Knapsack DP Bitset	Code
	Coin Grid		Code
	Robot Path		Code
	Programmers and Artists		Code
	Course Schedule II		Code
	Removing Digits II		Code
	Coin Arrangement		Code
	Counting Bishops		Code
✔	Grid Puzzle I	Max Flow Min Cut	Code
✔	Grid Puzzle II	Max Flow Max Cost	Code
	Empty String		Code
✔	Grid Paths	DP Inclusion Exclusion Principle	Code
✔	Bit Substrings	FFT	Code
✔	Reversal Sorting	Implicit Treap	Code
	Counting Reorders		Code
	Book Shop II		Code
✔	Network Breakdown	DSU with rollback	Code
	Visiting Cities		Code
	Missing Coin Sum Queries		Code
✔	Number Grid	Constructive	Code
	Maximum Building II		Code
	Filling Trominos		Code
✔	Stick Divisions	Huffman Coding greedy	Code
✔	Coding Company	Open and Close Interval DP	Code
	Flight Route Requests		Code
	Two Stacks Sorting		Code
✔	Tree Isomorphism II	Tree Isomorphism unrooted	Code
✔	Forbidden Cities	Block Cut Tree	Code
✔	Area of Rectangles	Range Query and Update with Sweep Line	Code
	Grid Completion		Code
	Creating Offices		Code
✔	Permutations II	Connected Component DP	Code
	Functional Graph Distribution		Code
	New Flight Routes		Code
	Grid Path Construction		Code