Competitive Programming Library

PDF Version

Algorithms

Algorithms

• Count inversions
• Ternary search (integer)
• Ternary search (real)

Combinatorics

• Process all paritions of a set

Contest

• bash config
• brute
• debug
• run
• short template
• template
• vim config

Data Structures

• 2D Segment Tree

  • Point update query sum

• Hash

  • Hash range query
  • Double hash range query
  • Hash unsigned long long

• Segment Tree

  • struct
  • query min

• Segment Tree Lazy

  • struct
  • increment update sum query

• Segment Tree Lazy Sparse

  • range add sum query modular
  • struct

• Segment Tree Point Update Range Query (Top Down)

  • Query hash (top down)

• Sqrt Decomposition

  • two sequence queries

• 2D Sparse Table

• Bitree 2D

• Convex hull trick

• DSU (with rollback)

• DSU

• Lichao tree dynamic

• Merge sort tree

• Mex with update

• Ordered set (GNU PBDS)

• Prefix sum 2D

• Sparse table

• Static range queries

• Venice set (complete)

• Venice set

• Wavelet tree

Dynamic Programming

• Binary knapsack
• Edit distance
• Knapsack
• Lis pro max
• Longest increasing subsequence
• Money sum
• SOS
• Steiner tree
• Travelling salesman problem
• tree knapsack

Extras

• int128t stream
• Binary to gray
• Get permutation cycles
• Max & min check (binary search)
• Merge Interals
• Mo's algorithm

Geometry

• .Verify Helper

• All i know about 2D stuff

• Angle between three points

• Area: polygon

• Check if point belongs to line

• Check if point belongs to segment

• Check if point is inside polygon

• Convex hull

• Cross product between points

• Define line from two points

• Determinant

• Distance: point to point

• Halfplane intersection

• Integer angle comparison

• Lattice points

• Left of polygon cut

• Perimeter: polygon

• Point

• Polygon (regular): apothem

• Polygon (regular): circumradius

• Polygon: check if is convex

• Rectangle intersection

• area of union of rectangles

• point rotation

• template

Graphs

• Flow

  • Maximum flow (Dinic)
  • Minimum cost flow

• Heavy Light Decomposition (Point Update)

  • Maximum number on path

• 2 SAT

• BFS 01

• Bellman Ford (find negative cycle)

• Bellman Ford

• Biconnected components

• Binary lifting

• Bipartite Graph

• Block Cut tree

• Centroid decomposition

• Count mandatory nodes on a single path

• D'Esopo Pape

• DSU query

• Dijkstra (K shortest pahts)

• Dijkstra

• Extra edges to make directed graph fully connected

• Find Bridges

• Find articulation points

• Find bridges (online)

• Find centroid

• Floyd Warshall

• Heavy light decomposition (supreme)

• Kruskal

• Lowest common ancestor (binary lifting)

• Lowest common ancestor (sparse table)

• Minimum vertex cover (already divided)

• Prim

• Shortest path with K edges

• Strongly connected components

• Topological sorting (Kahn)

• Tree diameter (DP)

• Tree edge queries

• Tree isomorphism (non rooted)

• Tree isomorphism (rooted)

• Virtual Tree

• eulerian cycle undirected

• eulerian path undirected

• find undirected unweighted graph diameter

• functional graph

• reroot dp

• two edge connected component

Linear Algebra

• Matrix (primitive)

Math

• Arithmetic progression sum
• Binomial mod
• Binomial
• Chinese remainder theorem
• Derangement
• Euler phi (in range)
• Euler phi
• Extended Euclidian algorithm
• FFT convolution and exponentiation
• Factorial factorization
• Factorization (Pollard's rho)
• Factorization
• Fast pow
• Find linear recurrence (Berlekamp Massey)
• Find multiplicatinve inverse
• Floor division
• GCD
• Gauss XOR
• Guess K th (Berlekamp Massey)
• Integer partition
• LCM
• Linear diophantine equation (count)
• Linear diophantine equation (solve)
• Linear recurrence
• List N elements choose K
• List primes (Sieve of Eratosthenes)
• Matrix exponentiation
• NTT convolution and exponentiation (2 mods)
• NTT convolution and exponentiation
• Polynomial Taylor Shift
• Polyominoes
• fibonacci mod m period
• polynomial composition
• spf

Primitives

• Bigint
• Integer Mod (complete)
• Integer Mod
• Matrix

Probability

• binomial distribution probability mass function dp
• binomial distribution probability mass function log

Strings

• Z Function

  • z function build
  • z function approximate pattern matching
  • z function pattern matching
  • z function find period

• Count distinct anagrams

• K th digit in digit string

• KMP

• Longest palindrome substring (Manacher)

• Longest palindrome

• Lyndon factorization

• Rabin Karp

• Suffix Tree (Ukkonen's Algorithm)

• Suffix array (supreme)

• Suffix array

• Trie

• kmp automaton

• preffix automaton

• suffix automaton

Tree

• tree flatten

References & Courses

• KACTL ICPC Code Library

• PauloMiranda98's Library

• Thalisson's Library

• IME algoritmos

• UFMG Library

• SSRS lib

• Macacário

• Competitive Programmer's Handbook

• Algorithms for Competitive Programming

• Competitive Programing Book

• UnBalloon

• Neps Academy

• USACO Guide

• TEP