Algorithms

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.

Repository structure

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.

References

• Most algorithms presented here are described on https://cp-algorithms.com/. Some code was taken from that site.

Useful submissions

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