Skip to content
forked from bira37/cp-lib

My library of algorithms and topics focused on competitive programming

Notifications You must be signed in to change notification settings

CP-Mangue/cp-lib

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

63 Commits
 
 
 
 

Repository files navigation

Ubiratan Correia Barbosa Neto - Competitive Programming Library

This repository contains algorithms that I learned through my journey on competitive programming:

  • Data Structures

    • Segment Tree
    • Binary Indexed Tree
    • Dynamic/Persistent Segment Tree
    • Trie
    • Lichao Segment Tree (Online Convex Hull Trick)/ Integer and Float Version
    • Offline Convex Hull Trick
    • Ordered Set
  • Uncategorized

    • Longest Increase Subsequence
    • 2D Longest Increase Subsequence
    • Inversion Count Offline (Merge-Sort)
    • Mos Query Decomposition
  • Basic 2D Geometry

    • Point/Vector Structure
    • Vector Structure
    • Line/Segment Structure
    • Distance from Point to Line
    • Distance from Point to Segment
    • Distance from Line to Segment
    • Distance from Point to Ray
    • Distance from Segment to Ray
    • Distance from Line to Ray
    • Distance between Segments
    • Distance between Rays
    • Distance between Lines
    • Line-Line Intersection
    • Segment-Segment Intersection
    • Line-Segment Intersection
    • Circle-Circle Intersection Area
    • Circle-Circle Intersection Points (NOT TESTED)
    • Tangent Line to a Circle Given a Point
    • Circle of Radius R Passing Through 2 Given Points
    • Barycenter, Circumcenter, Incenter, Excenter, Orthocenter, Centroid...
  • 2D Geometry Algorithms

    • Closest Pair of Points
    • Convex Hull(Monotone Chain) + Perimeter/Area Calculation
    • Smallest Enclosing Circle Randomized Algorithm
    • Check if a Point Lies in Convex Hull
  • Math and Number Theory

    • Binomial Coefficient
    • Euler Totient
    • Sieve of Erathostenes
    • Miller Rabin Primality Test
    • Count Primes/Divisors for Large Numbers + Sum Of Divisors of a Number
    • Matrix Exponentiation
    • Fast Fourier Transform (Iterative + Recursive)
    • Chinese Remainder Theorem
    • Diophantine Equations
    • Shank's Baby-Step Giant-Steps
  • Strings

    • Knuth - Morris - Pratt (KMP)
    • Z-Function
    • Rolling Hash
    • Aho-Corasick
    • Suffix Array + Linear Sorting (O(nlogn) S.Array)
  • Graphs

    • LCA
    • Max-Flow (Dinic's Algorithm)
    • Minimum Path Cover in Directed Acyclic Graphs
    • Minimum Edge Cover in Bipartite Graph
    • Minimum Cut in Flow Network
    • Minimum Vertex Cover in Bipartite Graph
    • Bellman Ford Shortest Path Algorithm
      • Dynammic Connectivity for connected(u,v) - query
      • Eulerian Circuit Directed/Undirected Graphs
      • Tarjan Algorithm for Bridges/Articulation Points
      • Heavy-Light Decomposition
      • Centroid Decomposition
      • Kosaraju's Strong Connected Components Algorithm

About

My library of algorithms and topics focused on competitive programming

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 100.0%