cp-templates

Overview

This repository contains templates for Competitive Programming in C++ envisioned and built by your one and only, Ahmad Dzuizz Annajib.

Comprehensive list of available templates:

1. Data Structures

   • Segment Tree
     • Range Addition Update, Range Sum Query with Lazy Propagation (array)
     • Range Addition Update, Range Sum Query with Lazy Propagation and Lazy Nodes (pointer)
     • All-In-One Implementation (pointer) - To Be Implemented
   • Fenwick Tree (Binary Indexed Tree)
     • Range Addition Update, Range Sum Query (2 BITs approach)
   • Disjoint Set Union (Union-Find)
     • Disjoint Set Union with Path Compression and Union by Size
     • Disjoint Set Union with Path Compression and Union by Rank -- To Be Implemented
     • Count no. of Connected Components in a Graph
   • Sparse Table - To Be Implemented
   • Trie (Prefix Tree) - To Be Implemented
   • Median Heap
     • Median Heap with 2 Heaps (Min Heap and Max Heap) - To Be Implemented
   • Balanced Binary Search Tree (e.g., AVL Tree, Red-Black Tree) - To Be Implemented
   • Queue with Min/Max - To Be Implemented
   • Persistent Data Structures - To Be Implemented

2. Graph Theory

   • Dijkstra's Algorithm
   • Breadth-First Search (BFS)
     • Flood Fill Algorithm
   • Depth-First Search (DFS)
     • Flood Fill Algorithm - To Be Implemented
   • Bellman-Ford Algorithm - To Be Implemented
   • Floyd-Warshall Algorithm
   • Kruskal's Algorithm - To Be Implemented
   • Tarjan's Algorithm - To Be Implemented
   • Topological Sorting - To Be Implemented
   • Bridges and Articulation Points - To Be Implemented
   • Graph Matching Algorithms - To Be Implemented
   • Flow Networks (Max Flow, Min Cut) - To Be Implemented

3. Trees

   • LCA (Lowest Common Ancestor) with Binary Lifting, a.k.a 2k Decomposition
   • APSP (All Pairs Shortest Path) with Binary Lifting, a.k.a 2k Decomposition
   • Diameter of a Tree
   • Centroid Decomposition - To Be Implemented
   • Heavy-Light Decomposition - To Be Implemented
   • Euler Tour Technique - To Be Implemented
   • DP on Tree - To Be Implemented

4. Algebra

   • Matrix Exponentiation - To Be Implemented
   • Extended Euclidean Algorithm - To Be Implemented
   • Sieve of Eratosthenes - To Be Implemented
   • Modular Arithmetic Operations - To Be Implemented
   • Prime Factorization - To Be Implemented
   • Modular Exponentiation - To Be Implemented
   • GCD/LCM - To Be Implemented
   • Fast Multiplication (Karatsuba, FFT) - To Be Implemented
   • Combinatorics (Combinations, Permutations) - To Be Implemented

5. Dynamic Programming

   • 0/1 Knapsack Problem - To Be Implemented
   • Longest Common Subsequence - To Be Implemented
   • Coin Change Problem - To Be Implemented
   • Edit Distance - To Be Implemented
   • Matrix Chain Multiplication - To Be Implemented
   • Longest Increasing Subsequence - To Be Implemented
   • Digit DP - To Be Implemented
   • Bitmask DP - To Be Implemented
   • DP on Trees - To Be Implemented
   • Knuth Optimization - To Be Implemented
   • DP with Probabilities - To Be Implemented

6. Geometry

   • Convex Hull (Graham's Scan)
     • Dynamic Convex Hull Trick for DP optimization
     • Monotone Chain Algorithm - To Be Implemented
   • Line Intersection - To Be Implemented
   • Closest Pair of Points - To Be Implemented
   • Polygon Area - To Be Implemented
   • Point Inside a Polygon Check - To Be Implemented
   • Geometric Transformations - To Be Implemented
   • Rotating Calipers - To Be Implemented

7. String Processing

   • KMP Algorithm - To Be Implemented
   • Z-Algorithm
   • Manacher's Algorithm - To Be Implemented
   • Rabin-Karp Algorithm - To Be Implemented
   • Suffix Array and LCP - To Be Implemented
   • Aho-Corasick Algorithm - To Be Implemented
   • Suffix Automaton - To Be Implemented

8. Numerical Algorithms

   • Fast Fourier Transform - To Be Implemented
   • Binary Exponentiation - To Be Implemented
   • Chinese Remainder Theorem - To Be Implemented
   • Euclidean Algorithm for GCD - To Be Implemented
   • Newton-Raphson Method for Numerical Root Finding - To Be Implemented
   • Simpson's Rule (Numerical Integration) - To Be Implemented
   • Linear Algebra Techniques - To Be Implemented

9. Classic Techniques

   • Binary Search - To Be Implemented
   • Two Pointers - To Be Implemented
   • Sliding Window - To Be Implemented
   • Meet in the Middle - To Be Implemented
   • Divide and Conquer - To Be Implemented
   • Greedy Algorithms - To Be Implemented
   • Backtracking - To Be Implemented
   • Brute Force - To Be Implemented
   • Recursive Techniques - To Be Implemented

10. Miscellaneous

    • Counting Inversions with Merge Sort - To Be Implemented
    • Sliding Window Technique - To Be Implemented
    • Two Pointers Technique - To Be Implemented
    • Bitmasking Techniques - To Be Implemented
    • Game Theory (Nim Game, Grundy Numbers) - To Be Implemented
    • Mo's Algorithm - To Be Implemented
    • Randomized Algorithms - To Be Implemented
    • Optimization Techniques (Hill Climbing, Simulated Annealing) - To Be Implemented

My Contact

If you have any suggestions on any improvements, please do not hesitate to contact me at [email protected].

---