Competitve Programming Templates

Description:

Usually it's helpful for the competitive programmers to keep their own templates.In the time of contest, we have to solve problems and write codes as fast as possible.Some times we need various complex algorithms, data structures etc which will take much times to implement them in contest time.So, keeping the templates and using them when necessary is a good choice.

List of contents:

• Big Integer Library
• Data Structure
• Dynamic Programming
• Graph Theory
• Number Theory
• Strings

Keyword and Short Summary of contents:

Big Integer Library

1. Supports all arithmetic operations.

Data Structure

1. Disjoin Set Union Find ( Finding connected components )
2. Heavy Ligh Decomposition ( On tree query problems, as like as LCA query )
3. MO's Algorithm ( Offline Queries , Complexity: O(M * sqrt(N)))
4. PBDS-Policy Based Data Structure ( Order statics set )
5. Segment Tree ( Effecient Segment tree with query + update )
6. Square Root Decomposition ( Offline Queries )
7. Trie (Data compression + String queris)
8. Wavelet Tree
9. LCA (Lowest Common Ancestro)

Dynamic Programming

1. Coin Change
2. 0 - 1 knapsack
3. Rod Cutting ( maximize or minimize )
4. Bitwise DP ( Subsets )
5. LIS (NlogN) (Longest increasing Subsequence)
6. LCS (longest common subsequence)
7. Maximum Rectange Sum variations

Graph Theory

1. Shortest path
2. Minimum spanning trees
3. Strongly connected components
4. Topological sorting
5. Bridges
6. Cycle Finding

Number Theory

1. Millar Rabin + pollard rho ( Big prime factorisation )
2. Primse , Factorisations, Factorials , Divisors
3. Gcd , Lcm
4. Number theory cpp notes
5. Combinatorics

Strings

1. KMP ( knuth-morrison-prat algorithm, Substring search, longest pallindrome, string compression )
2. Z Algorithm ( Same as kmp )
3. Hashing ( basically it's a data structure but some string operations can be done effeciently)

Sorting Algorithms

1. Bubble Sort ( Complexity : O(N^2) )
2. Counting Sort ( Complexity : O(N) )
3. Heap Sort ( Complexity : O(NlogN) )
4. Insertion Sort ( Complexity : O(N^2) )
5. Merge Sort ( Complexity : O(NlogN) )
6. Quick Sort ( Complexity : O(NlogN) )
7. Selection Sort ( Complexity : O(N^2) )