dragonslayerx / competitive-programming-repository

Competitive Programming templates that I used during the past few years.

Competitive-Programming-Repository

Collection of algorithms and data structures in C++ used widely in Competitive programming contests.

The following topics are covered:

Range Updates and Queries

• Range Aggregate Queries :
  • Binary Indexed Trees (BIT) :
    • Point Update Range Query
    • Range Update Range Query
    • Order Statistic Query
    • 2D Binary Indexed Trees
  • Segment Trees (SegTree) :
    • Point Update Range Query
    • Fast Iterative Segtrees
    • Range Update Point Query - Lazy Propogation
    • Max subsegment sum in range
    • 2D Segment Trees
    • Dynamic Segment Trees - Insertion/Deletion between elements
    • Dynamic Segment Trees - Reverse a segment
  • Merge Sort Trees :
    • Merge sort trees
    • Merge sort trees - Order Statistics
  • Sparse Table :
    • Range Minimum Query
  • Mo Algorithm :
    • Mo Algorithm - Arrays
• Dynamic Programming :
  • Dynamic Programming Templates :
    • Digit DP / Bitwise DP
  • Standard DP Problems :
    • Longest Increasing Subsequence
    • Longest Palindromic Subsequence
    • Levenstein Distance / Edit Distance
• Graphs :
  • Single Source Shortest Path Algorithms :
    • Dijkstra in dense graphs
    • Dijkstra using priority queue
    • Kth Shortest Path between Nodes using Dijkstra
    • Bellman Ford Negative cycle detection
  • All Pair shortest path :
    • Using Binary exponentiation
    • Floyd Warshall
  • Cycle Detection :
    • Cycle detection in Undirected/Directed Graphs
  • Minimum Spanning tree :
    • Kruskal Algorithm
  • Topological Sort / Strongly Connected Component :
    • Topological Sort
    • Strongly Connected Component
  • Maxflow/Matching :
    • Hopkroft Karp Max Matching
    • Dinic Max Flow
  • Misc :
    • Bridges in Graph
    • Connectivity
    • Bipartite Check
• Trees :
  • Ancestor queries :
    • Lowest Common Ancestor
    • Kth Ancestor
  • Path queries :
    • Sparse Table *
    • Heavy Light Decomposition Weighted Nodes
    • Heavy Light Decomposition Weighted Edges
  • Misc :
    • Diameter of Tree
    • Preorder/Postorder stamps, Is it in Subtree?
• Binary Exponentiation :
  • Calculate n^m using Binary exponentiation
  • Solving Linear Recurrences
• Strings :
  • String Algorithms :
    • Z Algorithm
    • KMP algorithm
    • Rolling String Hashing
    • Rolling String Hashing for Dynamic Strings
  • String Data Structures :
    • Suffix Array *
• Sorting :
  • Merge Sort
  • Quick Select
• Fast Input/Output, String/Integer Conversion :
  • Fast Input/Output
  • String/Integer Conversion
• Misc. Data Structures :
  • Disjoint Set
  • Disjoint Set (Supports Undo Operation)
  • Max/Min Priority Queue with update
  • Binary Trie for xor maximization/minimization
  • Bigint *
  • Augmented Binary Tree for order statistics and rank query
  • Monotone Priority Queue
  • Trie
• Persistent Data Structures :
  • Persistent Segment Trees (SegTree) :
    • Persistent Segment Tree
    • Persistent Segment Tree - Order Statistics
• Number Theory Algorithms :
  • Primality Check :
    • Fermat's Primality Check
  • Sieve :
    • Sieve of Eratosthenes
    • Segmented Sieve for large primes
    • Counting Prime Factors
  • Polynomial Multiplication :
    • Fast Fourier Tranform
    • Karatsuba
  • Misc :
    • Combinatorial and Catalan - Factorial preprocessing
    • Mobeius Function
    • Euler Totient Function
    • Lucas Theorm - Combinatorics
• Computational Geometry :
  • Convex Hull
• Misc :
  • Sum of floor(x) with x=1:n
  • Sum of cyclic functions *
  • Closest larger element before/after every element
  • Multiply Long Long Integers
  • Multiply Long Long Integers - Overflow detection
  • Scanline - Merge intersecting intervals

competitive-programming-repository's Issues

src/bigint_library.cpp mis behavior with value 0

If I create Bigint with value 0. stream operation and logical operations seems not work properly. like the example below:

int main() {
    Bigint A("0"); // Construct Bigint using string representation
    Bigint B(0); // Construct Bigint using integer representation
    Bigint C("456789");
    cout << A * B << endl; // Overridden ostream
    cout << A * B + C << endl; // Chaining operations
    cout << (A > B) << endl;
    // logical operations
    if (A > B) cout << "A is greater than B" << endl;
    else cout << "B is greater than A" << endl;
}

Output:

456789
1
A is greater than B

Requirement for new codes.

This library is not exhaustive as it still needs several key algorithms and data structures which are widely used in Competitive Programming. The lack is partially due to my lack of knowledge about them or
my laziness to implement and test them.

I'm listing some of the key algorithms here which this library needs.

1. A simple concise implementation of Centroid Decomposition, Bridge trees.
2. Knuth Morris Pratt (KMP), Manacher, Aho corasick : One can find an obselete code of kmp in obselete folder, I have used it several time but code is not concise.
3. A library for Computational Geometry including some key algorithms like finding convex hull of a set of points.

Any new cool completive programming template is also welcome ! Please report bugs in case u get one during using any of the template.

I would like to invite competitive programming enthusiasts to contribute to this library and let the knowledge grow. :)