Open-Source Competitive Programming Library Atlas

This repository was started as a personal book for ACM competitions, but it quickly grew out of control. Our aim is to create the world's first fully open-source large atlas of algorithms, data structures and mathematical concepts used in competitive programming that can be easily modified, printed and used in ACM competitions.

The problem with sources

The implementations are taken from various of sources with mostly CC0 license. For some of the implementations, I have lost or I wasn't able to find the original author. So, if you know the authors and see that they are not included, make a pull request!

Some known sources that need to be included for many of the algorithms are:

• KACTL Library
• EkzLIB
• CP-Algorithms

Coding Style

The coding style is not yet fully defined due to the newness of the book and the many sources that are included. The goal is to have relatively short pieces of code, but too short that it will make them unreadable and difficult to modify.

Contribution

Everyone is encouraged to contribute, add, fix, change and improve the book. I hope more and more people contribute! All contributors will be added to a contributor section at the end of the book.

Building the book

Locally, we use the MikTeX package to build the book. However, for the "minted" package, you will also need to install Python and pip install Pygments for the package to compile.

Open issues:

• Contributors section (List of contributors)
• Fill all sections with algorithmic implementations
• Coding Style
• Authors mention
• Algorithms/Data Structures in C++ form
• Unit Tests
• References
• LaTeX fixes

Change Log

• 01.10.2023
  • 2SAT
  • Chromatic Number
  • LCA
  • HLD
  • Centroid
  • CRT
  • Rotations
  • Graham Scan
  • Persistent Segment Tree
  • Kinetic Tournament Data Structure
  • Persistent Array
  • Treap
  • 3D Coordinate-Wise Domination
  • 3D Geometry
  • Circle Helper Functions
  • Convex Layers
  • Online Convex Hull Merger
  • GJK
  • Graham Scan Python Implementation
  • Half-Plane Intersection in O(N log N)
  • Random Geometry Stuff
  • BerlekampMassey Algorithm
  • FFT
  • GCD Convolution
  • Kth Permutation
  • NTT
  • Pollard & Miller Rabin
  • Operations on Polynomials
  • Primes
  • Calendar Conversions
  • Exact Cover
  • Roman Numerals
  • Picked solutions
  • Aho Corassick
  • KMP
  • MDST
• 02.10.2023
  • 2D Sparse Segment Tree
  • 2D Sparse Table
  • Binary Indexed Heap
  • Fenwick Tree
  • Lazy Segment Tree
  • Min-Max Heap
  • Persistent Heap
  • Segment Tree
  • Skew Heap
  • Nearest Smaller
  • Binary Exponentiation
  • Gosper's Hack