Competitive programing notes

Introduction

This repository holds all the boilerplate code que that I and my team use during training and actual competitions. Almost all .cpp files are ready to be copied and pasted, including relevant comments. However, for anyone using this repository, we must caution that a good understanding of the code and the theory behind it is needed in order to be effective using it, as it will most likely need some form of modifications for your particular problem.

Printable version

It is posible to auto generate a .pdf file for print based on all the content on the repository. In order to do this, you must compile the main.tex file.

Future updates

Pull requests are welcome, as well as any suggestions by opening an issue or writing to my mail.

Special Thanks

To my teammate and the original creator of this repo, Ignacio Hermosilla. To my coach Pablo Messina who provided a template and some of the code from his notes. And to everyone who has contributed to finding bugs and expanding the repo.

TODO

Add the following

• Python Cheat Sheet
• Prim
• Green's Theorem
• Convex Hull
• Rolling Hashing
• Search
  • Binary
  • Ternary
• Sparse Tables
• Treap
• Wavelet Tree
• DP Examples
  • Travelling Salesman
  • Knapsack Problem
  • Matrix Chain Multiplication
  • Others?
• DP Optimizations
  • Convex Hull Trick
  • Divide & Conquer Optimization
  • Knuth's Optimization
• Toposort
• Strongly Connected Components
  • Tarjan
  • Kosaraju
• Heavy Light Decomposition

Credit

• Strings
  • KMP:
  • Rolling Hashing:
  • Suffix Tree: Javier Reyes
  • Trie: Found by Ignacio Hermosilla
• Math
  • CRT: Pablo Messina
  • Factorial Factorization:
  • Modular Arithmetic:
  • nCr: Nicholas Mc-Donnell
  • Polynomials: Nicholas Mc-Donnell
  • Primality Checks:
    • Sieve of Eratosthenes: Nicholas Mc-Donnell
    • Trial Division: Nicholas Mc-Donnell
    • Miller Rabin: Taken from these notes, with modifications by Nicholas Mc-Donnell
  • Graphs:
    • BFS: Nicholas Mc-Donnell
    • DFS: Nicholas Mc-Donnell
    • Dijsktra: Nicholas Mc-Donnell
    • Bellman Ford: Nicholas Mc-Donnell
    • Floyd Warshall: Nicholas Mc-Donnell
    • Kruskal: Nicholas Mc-Donnell
    • Union Find/DSU: Nicholas Mc-Donnell
    • Dinic: Taken from these notes
    • LCA: Javier Reyes
  • Geometry:
    • Green's theorem: Pablo Messina
    • Simpson's Method: Nicholas Mc-Donnell
    • Vectors 2D: Nicholas Mc-Donnell & Pablo Messina
  • DP:
    • Knapsack: Nicholas Mc-Donnell
    • LIS: Nicholas Mc-Donnell
    • MCM: Nicholas Mc-Donnell
  • Data Structures:
    • Fenwick Tree: Ignacio Hermosilla
    • Fenwick Tree 2D: Ignacio Hermosilla
    • Segment Tree: Taken from these notes
    • Lazy Segment Tree: Taken from these notes
    • Wavelet Tre: Taken from these notes
  • Headers: Taken from these notes, with additions and modifications by Nicholas Mc-Donnell
  • C++ Cheat Sheet: Pablo Messina