/snippets

Competitive programming snippets

Primary LanguageC++

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)
  • Computational geometry (geometry/)
    • Point/vector structure w/ operations (point.cpp)
  • 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)
  • 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)

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)