Competitive Programming

My own templates and implementation of important algorithms and data structures for competitive programming

My profile: Codeforces, AtCoder

Contest templates

• My template C++

Graph

• Graph Traversing (DFS, BFS)
• Flood Fill
• Minimum Spanning Tree (Kruskal, Prim)
• Shortest Paths (Dijkstra, Bellman-Ford, 0-1 BFS, Floyd Warshall)
• Bridges and Articulation Points
• Strongly Connected Components (Tarjan, Kosaraju)
• Bipartite Matching
• Topological Sort (DFS, in_deg)
• Maximum FLow (Edmonds-Karp, Dinic)
• Lowest Common Ancestor (Binary Lifting, RMQ)

Dynamic Programming

• 0-1 Knapsack
• Coin Change
• Max Sum Subarray: 1D, 2D
• Longest Common Subsequence
• Longest Increasing Subsequence
• Digit DP
• SOS DP
• Weighted Job Scheduling
• Cutting Sticks
• Matrix Chain
• Elevator Rides
• Travelling Salesman Problem
• Deque Trick
• Divide & Conquer Trick
• Convex Hull Trick

Data Structure

• Sparse Table
• Fenwick Tree
• Segment Tree
• Treap
• SQRT Decomposition + Mo’s Algorithm
• Disjoint Set Union
• Trie
• Suffix Array
• Policy-based data structures C++ STL
• Heavy Light Decomposition

String Algorithm

• Pattern Searching (KMP, Z-Algorithm, Rabin-Karp)

Number Theory

• Sieve of Eratosthenes
• Greatest Common Divisor (Euclidean Algorithm)
• Quick Exponentiation
• Fibonacci
• Binomial Coefficients

Computational Geometry

• Sweep Line: Closet Pairs, Rectangle Union

Other Classic Problems

• N-queen
• Median Heap
• Maximum Histogram Area
• Meet In The Middle
• 2-SAT
• Offline Dynamic Connectivity
• Closest Points (Divide & Conquer)