Competitive programming snippets
These snippets are for use in online programming contests (e.g. on Codeforces, Topcoder, GCJ and other platforms that allow pre-written code).
The snippets provided here serve as model implementations of some frequently used algorithms and techniques in solutions authored [by me] (http://codeforces.com/profile/x3n). The main sources of snippets are CLRS's Introduction to Algorithms and refactored (more readable?) versions of code snippets from e-maxx.ru.
Disclaimer: Although these snippets are mainly for internal use (i.e. to be used by myself with the repository serving as public proof of prior existence of the code), it's not forbidden for anyone to use them on such sites as long as they explicitly allow code that is not authored by the contestant himself.
Included snippets
- Data structures (
data_structures/
)- Disjoint-set union (
dsu.cpp
) - Fenwick tree (
fenwick.cpp
) - Segment tree (
segtree.cpp
) - Segment tree, recursive implementation (
segtree_recursive.cpp
) - Square root decomposition (
sqrt_decomp.cpp
) - Treap (
treap.cpp
) - Treap w/ implicit key (
treap_implicit.cpp
)
- Disjoint-set union (
- Computational geometry (
geometry/
)- Point/vector structure w/ operations (
point.cpp
)
- Point/vector structure w/ operations (
- Graph theory (
graph_theory/
)- Bellman-Ford algoritm (
bellman_ford.cpp
) - Breadth-first search (
bfs.cpp
) - Depth-first search (
dfs.cpp
) - Dijkstra's algorithm (
dijkstra.cpp
) - Edmonds-Karp max-flow algorithm (
edmonds_karp.cpp
) - Floyd-Warshall algorithm (
floyd_warshall.cpp
) - Kosaraju's algorithm for finding SCC (
kosaraju.cpp
) - Kuhn's maximum bipartite matching algorithm (
kuhn.cpp
) - Fold-Fulkerson max-flow method with scaling (
scaling.cpp
) - Topological sort (
topsort.cpp
)
- Bellman-Ford algoritm (
- Number theory (
number_theory/
)- Euler's phi function (
euler_phi.cpp
) - Fast Fourier transform (
fft.cpp
) - Modular exponentiation (
mpow.cpp
) - Overflow-safe exponentiation (
opow.cpp
) - Sieve of Eratosthenes (
sieve.cpp
) - Extended GCD algorithm (
xgcd.cpp
)
- Euler's phi function (
Todo's
- Provide the repository with more snippets (obviously)
- Preface the snippets with meaningful commentaries on the specifics
- Include range-update & range-query RMQ/RSQ segment trees
- Include more algorithms on graphs
- Include solutions for common dynamic programming problems (LCS, LIS, edit distance, knapsack variations)