/Training

Library for ICPC competitons

Primary LanguageC++

Traning Repository

Used:

  • Handbook of geometry for competitive programmers, Victor Lecomte
  • Introduction to Algorithms, Cormen
  • Competitive Programming 3, Halim
  • Wikipedia
  • Geek for geeks
  • cp-algorithms.com

Data Structures

  • BIT / Fenwick Tree (OK)
  • Segment Tree (with lazy prop.) (OK)
  • Union-Find (OK)
  • Sparse Table (OK)
  • Mo's
  • Sqrt Decomposition
  • Treap - Cartesian Tree
  • Persistent Union-Find

Graphs

  • Prüfer (OK)
  • Havel-Haimiki
  • DFS (OK)
  • BFS (OK)
  • Topological Ordering (OK)
  • Biconnected Components - Lowpt (undirected) algorithm (OK)
  • Strongly Connected Components - Lowpt (directed) algorithm (OK)
  • Shortest paths - One to All - Dijkstra's algorithm (OK)
  • Shortest paths - All to All Floyd-Warshall algorithm (OK)
  • Euler path - Hierholzer (OK)
  • Transitive closure - Warshall algorithm (OK)
  • Lowest Common Ancestor (OK)
  • Flow - Dinitz
  • Bipartite Maximum Matching - Hopcroft–Karp
  • Edge Cover
  • Genral Maximum Matching - Blossom algorithm
  • Centroid Decomposition
  • Cycle compression

Geometry

  • Simple tasks (~OK)
  • Convex Hull (OK)
  • Point inside Polygon (OK)
  • Polygon area - Shoelace formula (OK)
  • Determine if a list of points is in (counter)clockwise order (OK)
  • Closest pair of points (OK)
  • Binary Search in a Polygon
  • Farthest pair of points
  • Intersections
  • Line Sweep
  • Plane Sweep
  • Minkowsky Sum

Dynamic Programming

  • Knapsack problem
  • DP otimization
  • Travelling Salesman approaches

Math

  • Root of quadratic polynom
  • Polynomial long division
  • Fast Expo (recursive and iterative)
  • Number Theory
  • FFT
  • Multiplicative functions
  • Meet in the middle
  • Baby steps, Giant steps

String

  • Manacher (OK)
  • Z-Algorithm (OK)
  • KMP
  • Trie
  • Suffix Array
  • Suffix Tree
  • Aho–Corasick

Others

  • Nim game
  • Two pointers
  • Hashing