Competitive Programming
My own templates and implementation of important algorithms and data structures for competitive programming purposes
My profile: Codeforces, Dunjudge.me
Contest templates
Graph
- Graph Traversing (DFS, BFS)
- Flood Fill
- Minimum Spanning Tree (Kruskal, Prim)
- Single-Source Shortest Paths (Dijkstra, Bellman-Ford, 0-1 BFS)
- All-Pair Shortest Paths (Floyd Warshall)
- Bridges and Articulation Points
- Strongly Connected Components (Tarjan, Kosaraju)
- Bipartite Matching
- Topological Sort (DFS, in_deg)
- Maximum FLow (Edmonds-Karp)
- Lowest Common Ancestor (Binary Lifting, RMQ)
Dynamic Programming
- 0-1 Knapsack
- Coin Change
- Max Sum Subarray (Kadane's Alogorithm): 1D, 2D
- Longest Common Subsequence
- Longest Increasing Subsequence
- Digit DP
- Weighted Job Scheduling
- Matrix Chain Multiplication
- Elevator Rides
- Travelling Salesman Problem
Data Structure
- Sparse Table
- Fenwick Tree
- Segment Tree
- Persistent Data Structure
- SQRT Decomposition + Mo's Algoithm
- Union-Find Disjoint Sets
- Trie
- Policy-based data structures C++ STL
- Heavy Light Decomposition
String Algorithm
- Pattern Searching (KMP, Z-Algorithm)
Number Theory
- Sieve of Eratosthenes
- Greatest Common Divisor (Euclidean Algorithm)
- Quick Exponentiation
- Fibonancci
- Binomial Coefficients
Computational Geometry
- Sweep Line
- Convex Hull