tarek99samy/ACMlib

Collection of useful algorithms for problem solving

Competitive Programming Code Library

Collection of algorithms I personally use a lot written in C++ for problem solving.

There are useful formulae and identities in the Theoretical Computer Science Cheat Sheet

Contents

• Data Structures
• Dynamic Programming
• Geometry
• Graphs
• Maths
• Misc

Data Structures

• Binary Indexed Tree/Fenwick Tree
• Segment Tree
• Sparse Table
• Trie

Dynamic Programming

• LCS
• LIS O(n^2) with path
• LIS O(nlog(n))

Geometry

TBA

Graphs

• Bellman Ford
• Breadth First Search (BFS)
• Depth First Search (DFS)
• Dijkstra
• Disjoint Set Union (DSU)
• Floyd Warshall
• Bipartite Graph Check
• Kruskall's MST
• Tarjan's SCC recursive
• LCA O(log(n)) w/ K'th Ancestor
• LCA O(1)
• Longest path in Weighted Graphs
• Tree Diameter

Maths

• Extended Euclidean
• Euler's Totient Function (Euler's phi)
• Fastpower with mod
• IsPrime check
• nCr with mod
• Prime Factorization
• Sieve
• Smallest Prime Factor
• Misc

Misc

• DigitSum
• IsPalindrome check
• Matrix Power
• toBinary

References

• Sayed Alesawy library
• Momentum's library
• Coach Mohamed Abdelwahab's library