Starscream-11813/Competitive-Programming-1

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

Competitive Programming

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

My profile: Codeforces, Dunjudge.me

Contest templates

• My template C++

Graph

• Graph Traversing (DFS, BFS)
• Flood Fill
• Minimum Spanning Tree (Kruskal, Prim)
• Single-Source Shortest Paths (Dijkstra, Bellman-Ford)
• All-Pair Shortest Paths (Floyd Warshall)
• Strongly Connected Components (Tarjan, Kosaraju)
• Bipartite Matching
• Topological Sort
• 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
• Matrix Chain Multiplication
• Travelling Salesman Problem

Data Structure

• Sparse Table
• Fenwick Tree
• Segment Tree
• SQRT Decomposition + Mo's Algoithm
• Union-Find Disjoint Sets
• Policy-based data structures C++ STL

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

Other Classic Problems

• N-queen
• Maximum Histogram Area

Contests & Competitions

• Google Code Jam
• Singapore National Olympiad in Informatics (NOI)