/cp-templates

Templates for Competitive Programming

Primary LanguageC++

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 ahmad.dzuizz.annajib@gmail.com.