/competitive_programming_codebook

Programming Contest Book.

Codebook for programming I store some Advanced Algorithms and data structures here. Of course, everything here is implemented

I tried to explain the algorithm in the code

Template c++

  • Basic Template
  • Super Template

Number Theory

  • Baby Step-Giant Step
  • Phi Function
  • Linear Seive
  • PRIME TEST(miller_robin)
  • PRIME TEST (BPSW)(100%)
  • NUMBER OF PRIME FACTOR(10^18)
  • NUMBER OF PRIME FACTOR(SQUFOF) Faster (10^18)
  • NUMBER OF DIVISORS (1-10^18)
  • Modular Inverse if mod is not prime
  • Modular inverse(1 to N)__O(N)
  • Factorial modulo (n!%p)
  • DIVISORS ___SUM OF DIVISORS____MULT OF DIVISORS____N<=10^16
  • ax+by=c everything ____extended euclid
  • n! % k^x==0 find x
  • Expression solving
  • BURNSIDE LEMMA
  • floor number sum
  • quadric resduie (can any sqrt(x) represents with a number)
  • Farey Sequence
  • Chinese Remainder Theorem(Garner's)
  • Sum of Kth power____Find (1^k+2^k+...+n^k %) mod____O(K)

Graph

  • DSU
  • MST
  • Strongly Connected Component
  • Dijkstra
  • LCA
  • Directed MST
  • Floyd Warshall
  • Articulation Point
  • BellManFord (negative cycle ditect)
  • Dinic's-Maxflow
  • Dominator Tree
  • MaxFlowMinCut(SPFA)
  • Centroid Decomposition(normal Implementation)
  • Centroid Decomposition(Path Problem)
  • Finding the shortest path of two-node in every query
  • HopcroftKarp (BPM Unweighted)
  • LCA finding ____offline query ___O(1) time each query
  • dynamic connectivity problem
  • Blossom Algorithm (maximum matching in the general graph)
  • BronKerbosch (Maximum clique)
  • Kirchhoff matrix theorem(Finding the number of spanning trees)

GEOMETRY

  • Point Template
  • Line Template
  • Segment Template
  • Circle Template
  • 3D geometry Template
  • 3D Plane template
  • Line 3D Template
  • Finding the area of ​​the union of triangles
  • PolyGons
  • Picks Theorem (the number of points with integer coordinates that lie strictly inside the polygon)
  • Polyhedrons
  • Spherical geometry
  • Convex hull___NlogN
  • Check point for belonging to a convex polygon
  • Constructing a convex hull by Graham bypass___Nlogn
  • Deleting points from Convex Hull ___(nlogn*q)
  • Dynamic Convex hull___Adding Points to an Existing Convex Hull__complexity o(n*q)
  • Finding the largest inscribed circle in a convex polygon using a ternary search

Data Structure

  • Fenwick Tree
  • FenwickTree2D
  • Sparse Table
  • Merge Sort Tree
  • Segment Tree(single update)
  • Segment Tree with lazy (range update )
  • Sqrt Decomposition (add & sum)
  • l to r maximum subarray sum with update
  • Mo’s Algorithm (normal, add, remove, query sort)
  • Mo’s Algorithm (gilbertorder)
  • Mo’s on Tree
  • Mo’s with DSU
  • Mo’s with update
  • Mo's Online
  • DSU on Tree
  • Sum of all possible triplet product in an array
  • NTT & FFT
  • Fast Walsh Hadamard Transformation(All pair Xor___AND___OR Sum)
  • Trie (subarray xor less than k)
  • Trie (Xor Max-Min)
  • wavelet tree
  • HLD
  • Lis in every Query___ when array element sum<=1000000
  • Persistent Trie
  • Treap

STRING

  • Rolling Hash
  • 2D hashing
  • KMP
  • Aho corasick
  • palindromic Tree
  • Suffix Array O(n)
  • Suffix Automaton

XOR ___ GCD___LCM

  • basis vector___everything for xor subset
  • All pair GCD
  • All pair GCD(II)
  • All pair LCM
  • GCD & XOR (how many pair with same gcd and xor)
  • maximum pair lcm in an array

Others

  • BigInt with fft(add,mult,div)___nlogn__10^5 length Number
  • JAVA BigInteger
  • MatExpo
  • Number Theory Notes
  • Random Genarator

Disclaimer

  • Don't use directly in code
  • Learn about these algorithms.
  • you can find some useful website, tutorial, and motivations Here
  • If you want to add more. Fork it. Add them. and give me a pull request.
  • Try to customize your own code.

Thank you