This repository contains efficient C++ implementations for algorithms useful in competitive programming.
I collect here non-trivial algorithms which might be useful for solving CodeForces-style problems. Algorithms are implemented in such a way that it's easy to quickly copy-paste them into solution.
This repository is mostly for private use, but I don't mind anyone using the code as long as you are not violating any competition rules.
Every file contains some algorithms as C++ functions and classes and main() function which tests the algorithms and returns 0 if and only if all tests pass.
- Most algorithms presented here are described on https://cp-algorithms.com/. Some code was taken from that site.
Here is list of my successful submission on Codeforces which use some algorithms. I might check in some of them into this repository later.
-
Matrix multiplication, discrete root/log: https://codeforces.com/contest/1106/submission/49511444
-
Max clique (randomized heuristic): https://codeforces.com/contest/1105/submission/48640589
-
Good random: https://codeforces.com/contest/1114/submission/49737616
-
Diophantine equation ax+by=c;x,y>=0;x+y->min: https://codeforces.com/contest/1244/submission/62513297
-
Longest common subsequence (of 2 or 3 strings): https://codeforces.com/contest/1789/submission/195068679
-
Segment tree:
-
With addition on segment and global minimum: https://codeforces.com/contest/1108/submission/48909309
-
With SET and SUM on segment: https://codeforces.com/contest/1478/submission/107305419
-
With update on range and query on range: https://codeforces.com/contest/1114/submission/49736495
-
Binary search on segment tree (example): https://codeforces.com/contest/1440/submission/102673366
-
-
LCA + XorBasis: https://codeforces.com/contest/1902/submission/260593439
-
Trie: https://codeforces.com/contest/1902/submission/260591332
-
Sparse table: https://codeforces.com/contest/1879/submission/262920880
-
0-1 BFS: https://codeforces.com/contest/1860/submission/263679738
-
Eulerian Path (undirected): https://codeforces.com/contest/1981/submission/263688257
-
Eulerian Path (directed): https://codeforces.com/contest/508/submission/263690188
-
Minimum Spanning Tree (Kruskal+DSU): https://codeforces.com/contest/1981/submission/263693183
-
DP over tree edges (example): https://codeforces.com/contest/1984/submission/264981777
-
BitVector + fast DP over bitmasks: https://codeforces.com/contest/1995/submission/278184683
-
XOR hashing: https://codeforces.com/contest/2014/submission/282526837