Skip to content

Latest commit

 

History

History
90 lines (71 loc) · 6.91 KB

README.md

File metadata and controls

90 lines (71 loc) · 6.91 KB

Competitive Programming

Repository of algorithms / code snippets commonly used in CP, mostly in C++ and Python. Haven't done documentation of solved problems in awhile, but those can be found in Archives.

The aim is to create a reliable, bug free library of code for saving time in CP contests. Also includes reference code for some (simpler) algorithms.

VSCode Snippets

Contains a collection of libraries formatted in VSCode snippets. Does not contain reference code.

Sorting Algorithms

  • Merge Sort
  • Quicksort w DNF partitioning

Data Structures

  • Fenwick Tree
  • Lazy Segment Tree
  • Range Minimum Query
  • Disjoint Set Union
  • Ordered Set

Graphs

  • Dijkstra
  • Articulation Points and Bridges
  • SCCs, Kosaraju
  • MSTs, Kruskal
  • Bellman Ford
  • Floyd Warshall

Math

  • Combinatorics
  • Prime Counting
  • Prime factorization
  • Tortoise hare cycle finding

Strings

  • String hashing
  • Suffix Array

Generics

  • Fast I/O Templates
  • Bitwise Operations

Sorting Algorithms

  • Merge Sort O(N log N)
  • QuickSort w DNF partitioning

Data Structures

  • Vector/ArrLis reference
  • UFDS
  • Priority Queue Reference
  • Fenwick Tree, RUPQ, RURQ
  • Array Rotation

Dynamic Programming

  • Kadane's Algorithm
  • Longest Increasing Subsequence (with backtrack)
  • 0/1 Knapsack (with backtrack)
  • Coin Change
  • Travelling Salesman Problem

Graph Theory

  • Graph Traversal
  • Flood Fill
  • Topological Sort (DFS / Kahn's Algorithm)
  • Bipartite / Cycle Checks (DFS)
  • Articulation Points and Bridges (DFS)
  • SCCs, Kosaraju's Algorithm
  • MSTs, Kruskal's Algorithm (with UFDS)
  • SSSP Dijkstra
  • SSSP Bellman Ford
  • APSP Floyd Warshall

Discrete Mathematics

  • PnC
  • GCD, LCM
  • Fast exponentiation
  • Primes

Misc

  • Rabin-Karp Algorithm with rolling hash