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
• debug
• run
• short template
• simple template
• template
• vim config

Data Structures

• 2D Segment Tree

  • Point update query sum

• Segment Tree (Dynamic)

  • Range query sum point sum update
  • Range query max point max assign

• Segment Tree Point Update Range Query (Bottom Up)

  • Struct
  • Query sum
  • Query GCD
  • Query min
  • Query Max Subarray Sum

• Segment Tree Point Update Range Query (Top Down)

  • Query hash (top down)

• Segment Tree Range Update Range Query

  • Increment update query min & max (bottom up)
  • Arithmetic progression sum update query sum (top down)
  • Increment update sum query (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

• Segment Tree Update Range Query (bottom up)

• Sparse table

• Static range queries

• Venice set (complete)

• Venice set

• Wavelet tree

Dynamic Programming

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

Extras

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

Geometry

• All i know about 2D stuff
• Angle between three points
• Area of union of rectangles
• 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
• Lattice points
• Left of polygon cut
• Perimeter: polygon
• Point
• Polygon (regular): apothem
• Polygon (regular): circumradius
• Polygon: check if is convex
• Rectangle intersection
• template

Graphs

• 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 bridge tree components

• Find bridges (online)

• Find centroid

• Floyd Warshall

• Function graph

• Heavy light decomposition (supreme)

• Kruskal

• Lowest common ancestor (binary lifting)

• Lowest common ancestor (sparse table)

• Maximum flow (Dinic)

• Minimum cost flow

• Minimum vertex cover (already divided)

• Prim

• Reachability Tree

• Shortest path with K edges

• Strongly connected components

• Topological sorting (Kahn)

• Topological sorting (Tarjan)

• Tree diameter (DP)

• Tree edge queries

• Tree isomorphism (non rooted)

• Tree isomorphism (rooted)

• Virtual Tree

• find undirected unweighted graph diameter

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

Numerical Methods

Primitives

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

Probability

• k success in binomial distribution

Problems

• 2081 Fixed Lenght Paths II
• Fixed lenght pahts I
• Fixed lenght paths II

Strings

• Z Function

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

• Count distinct anagrams

• Double hash range query

• Hash range query

• Hash unsigned long long

• K th digit in digit string

• KMP

• Longest palindrome substring (Manacher)

• Longest palindrome

• Lyndon factorization

• Rabin Karp

• Suffix Automaton

• Suffix Tree (Ukkonen's Algorithm)

• Suffix array (supreme)

• Suffix array

• Suffix automaton

• Trie

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