Competitive Programming

In this repository, you'll find algorithms and data structure implementations for competitive programming, along with a printable notebook with the implementations

Algorithms

• Data Structures

  • matrix
  • merge sort tree
  • mex
  • mex update
  • rmq
  • segtree
  • segtree2d
  • segtreelazy
  • segtreelazy generic
  • ufds
  • wavelet tree

• Dynamic Programming

  • kadane
  • lis

• Extras

  • stream int128t

• Geometry

  • circle
  • convex hull
  • convex hull trick
  • lichao tree
  • point in polygon
  • point to segment
  • point vector
  • polygon
  • polyominoes
  • sweep line
  • triangulo

• Graphs

  • articulation points
  • bellman ford
  • bfs 01
  • binary lifting
  • bridges
  • cycle bellman ford
  • cycle floyd warshall
  • dijkstra
  • floyd warshall
  • graph
  • kahn
  • kosaraju
  • kruskal
  • minimax
  • msf
  • msg
  • prim
  • retrieve path
  • retrieve path 2d
  • second best mst
  • tarjan

• Math

  • binomial
  • count divisors
  • count divisors range
  • factorization
  • factorization with sieve
  • fast doubling
  • fast exp
  • fast exp iterative
  • fft
  • gcd
  • integer mod
  • is prime
  • lcm
  • phi
  • sieve
  • sum divisors
  • sum of diference

• Problems

  • kth digit string
  • lcs ks strings
  • substring order II

• Strings

  • aho corasick
  • edit distance
  • lcp suffix array
  • manacher
  • rabin karp
  • suffix array
  • suffix array op
  • suffix automaton
  • suffix tree
  • z function

• Trees

  • lca binary lifting (cp algo)
  • lca segtree (cp algo)
  • lca sparse table
  • tree flatten
  • tree isomorph

Contributing

If you want to contribute to this repository, you can do it by adding new algorithms or improving the existing ones. To do so, you can follow the steps below:

1. Fork this repository
2. Add or improve the algorithm you want
3. Create a pull request
4. Wait for the pull request to be reviewed and merged

Obs: You don't need to update the notebook, because it is generated automatically. Just add the algorithm to the algorithms folder and make sure that you have added it to the correct category folder such as algorithms/math, algorithms/graphs, etc.

How to run locally?

If you want to create your own notebook, it is possible as follows:

Clone the project repository with the following command:

git clone https://github.com/mateusvrs/competitive-programming.git

To run the project, you need to install the global dependencies, which are:

• Docker Engine v24 (or higher)

From that, you can delete the algorithms inside the algorithms folder and add your own inside the same algorithms folder that are empty now. To customize the README.md, you can edit the scripts/gen-readme.py file. Finally, you can edit the university logo changing the assets/logo.jpg file (keeping the same name and extension) and uncommenting line 57 at the file "scripts/notebook/template.tex".

Now, you can run the following command:

# Change the "Your Team Name" to the name of your own team
docker run -w /notebook -v .:/notebook mateusvrs/cp-notebook:v1.0 make team_name="Your Team Name"      

References & Courses

• TEP
• Competitive Programming Algorithms
• UnBalloon
• Algorithms for Competitive Programming
• Competitive Programing Book
• Competitive Programmer's Handbook