Adilet.org

Algos

Algos is a collection of different algorithms, mainly used for programming competitions (like ACM ICPC).

Contains algorithms divided by topic. Most algorithms are runnable from the file as is. All algorithms have a reference problem on which they can be tested (or are waiting for this problem to be provided).

Feel free to use for any purposes (you may contact authors before, if need be).

You may also see the original repository of Algos. Feel free to contribute.

For any suggestions, corrections or questions contact adilet@adilet.org

Table of content:

  1. Data Structures

  2. Dynamic Programming

  3. Geometry

  4. Graphs

  5. Number Theory

  6. Other

  7. Strings

Data Structures

Cartesian Tree

Reference problem: #2782
Complexity: O(logN) per operation.

Cartesian tree is a randomized balanced binary search tree.

Cartesian Tree with implicit keys

Reference problem: #111240
Complexity: O(logN) per operation.

Cartesian tree with implicit keys is a powerful modification of cartesian tree, which can be used to solve many interesting problems. This implementation solves the problem of finding range minimum and also can perform reverse of an array segment.

Fenwick tree

Reference problem: #3317
Complexity: O(logN) per operation.

Fenwick tree is a simple and easy-to-write data structure which can be used to find the value of some reversible function on the interval and also change the value of some element. This implementation can find the sum on the interval and update any arbitrary element.

Fenwick tree 2D

Reference problem: #3013
Complexity: O(log2N) on query.

Extension of Fenwick tree on 2D case. This code can find the sum on the rectangle and update any arbitrary element.

Implicit segment tree

Reference problem: #3327
Complexity: O(logN) per query.
Memory: O(QlogN). Q — number of queries, N — interval length

Implicit segment tree is a modification of segment tree which creates nodes only when they are needed. It can be used on big intervals like [1..109]. This code performs addition on the interval and getting the value of some element.

Queue with minimum

Reference problem: #756
Complexity: O(1) on operation.

Modification of queue, which allows finding the minimum element in it.

Segment Tree (Assign-Sum)

Reference problem: Problem C from here
Complexity: O(logN) per operation.

Segment tree is a powerful data structure which can perform many operations on the intervals in O(logN) time. This implementation performs assignment and gets the sum on the interval.

Segment Tree (minimum on a segment and update)

Reference problem: #3309
Complexity: O(logN) per operation.

Segment tree. Solves RMQ problem (maximum on a segment and value update).

Sparse table

Reference problem: #3309
Complexity: O(NlogN) on precalculation, O(1) on query.

Solves static RMQ problem (range minimum/maximum query without element changes).

Dynamic Programming

Convex Hull trick

Reference problem: CFR#189, task C
Complexity: O(N).

Convex Hull trick is a geometry based dynamic programming modification. More about it

Longest Increasing Sequence

Reference problem: #1794
Complexity: O(NlogN).

Fast way to find longest increasing subsequence (subsequence in which each next element is greater than previous).

Geometry

Closest pair of points.

Reference problem: CLOPPAIR
Complexity: O(NlogN).

Divide-and-conquer approach to find the closest pair of points.

Convex Hull

Reference problems: #638, #290
Complexity: O(NlogN).

Graham-Andrew and Graham scan methods to find convex hull (the least convex polygon containing all given points).

Graphs

Bellman-Ford algorithm

Reference problem: #178
Complexity: O(N * M).

Bellman-Ford algorithm finding shortest distances from a single vertex in graph.

Bipartite matching

Reference problem: #1683
Complexity: O(N * M).

Kuhn algorithm for maximum matching in bipartite graph.

Bridges search

Reference problem: Problem C from here
Complexity: O(N + M).

Algorithm for finding all bridges in the graph (edges, after removal of which graph divides into several components).

Cutpoints search

Reference problem: Problem D from here
Complexity: O(N + M).

Algorithm for finding all cutpoints in the graph (vertices, after removal of which graph divides into several components).

Dijkstra algorithm

Reference problem: Codeforces, 20C
Complexity: O(MlogM).

Finding minimum distances from the single source with Dijkstra algorithm. No negative edges are allowed. Best for sparse graphs. Two versions using set and heap.

Dinic maxflow

Reference problem: #2784
Complexity: O(N * M * log(MC)), where MC is maximum edge capacity.

Dinic algorithm with scaling for finding the maximum flow.

Eulerian path/cycle

Reference problem: #1704
Complexity: O(M).

Algorithm for finding the Eulerian path/cycle — path/cycle that visits every edge of the graph exactly once.

Floyd-Warshall algorithm

Reference problem: #95
Complexity: O(N3).

Floyd-Warshall algorithm finding shortest distance between all pairs of vertices in graph.

Ford-Fulkerson maxflow

Reference problem: #2783
Complexity: O(M|f|), |f| - maxflow value.

Ford-Fulkerson algorithm for finding the maximum flow.

Heavy-light decomposition

Reference problem: #1553
Complexity: O(N) on building,
O(log2N) on query.

Heavy-light decomposition with segment trees in paths. Used for finding maximum on the path between two vertices.

Hungarian matching

Reference problem: #394
Complexity: O(N3).

Hungarian algorithm for solving the assignment problem.

LCA. Binary ascent.

Reference problem: #111796
Complexity: O(NlogN) for preprocessing, O(logN) on query.

Finding LCA (Least common ancestor) of two vertices in the tree. Uses dp calculated on powers of 2.

LCA. Heavy-light decomposition.

Reference problem: #111796
Complexity: O(N) for preprocessing, O(logN) on query.

Finding LCA (Least common ancestor) of two vertices in the tree. Uses heavy-light decomposition.

MinCost MaxFlow Dijkstra

Reference problem: #394
Complexity: O(N5) or O(N * M2 * logN). Less on practice.
O(N3) for bipartite matching case.

Solution to MinCost MaxFlow (or simply MinCost Flow) using Dijkstra algorithm with potentials as shortest path search method.

MinCost MaxFlow Ford-Bellman

Reference problem: #394
Complexity: O(N6). Less on practice.
O(N4) for bipartite matching case.

Solution to MinCost MaxFlow (or simply MinCost Flow) using Ford-Bellman algorithm as shortest path search method

Minimum spanning tree. Kruskal algorithm

Reference problem: #1377
Complexity: O(MlogM).

Kruskal algorithm for finding the minimum spanning tree (tree connecting the given graph with minumim sum of edges).

Minimum spanning tree. Prim algorithm

Reference problem: #185
Complexity: O(N2).

Prim algorithm for finding the minimum spanning tree (tree connecting the given graph with minumim sum of edges).

Number Theory

BigInt

Reference problem: not added yet.
Complexity: depends on function.

Structure implementing long arithmetic in C++. Analogous to BigInteger in Java.

Catalan numbers

Reference problem: #140
Complexity: O(N * loglogN)

Finding Nth Catalan number modulo some mod (mod is not necessary prime). Uses Eratosthenes sieve for fast factorization

Diophantine equation

Reference problem: #4188
Complexity: O(logX), where X — the biggest number in equation.

Solving Diophantine equations in form of a * x + b * y = c.
Uses extended Euclid algorithm (which finds such x, y that a * x + b * y = gcd(a, b))

Fast Fourier transformation

Reference problem: #317
Complexity: O(NlogN).

Fast Fourier transformation used to multiply long numbers. Fast non-recursive version.

Gauss

Reference problem: #198
Complexity: O(N3).
More presicely: O(min(N, M) * N * M), where N — number of equations, M — number of variables.

Gauss method of solving systems of linear algebraic equation.

Number by permutation

Reference problem: #2388
Complexity: O(N2).

Finding number of permutation in lexicographical order

Permutation by number

Reference problem: #190
Complexity: O(N2).

Finding permutation by its length and number in lexicographical order

Other

Expression result calculation

Reference problem: not added yet
Complexity: O(N)

Calculation of the value of the algebraic expression (like 2 * (5 + 7) - 25 / 5). Uses recursive descend. See code for the list of supported operations.

Merge sort

Reference problem: #766
Complexity: O(NlogN)

Merge sort for sorting the array of integers.

Quick sort

Reference problem: #766
Complexity: O(NlogN)

Quick sort with random pivoting for sorting the array of integers.

Radix sort

Reference problem: #766
Complexity: O(N * len), where len - maximum length of numbers.

Radix sort for sorting the array of integers.

Strings

Aho-Corasick

Reference problem: Problem K from here
Complexity: O(len of queries + sum len of initial strings)

Aho-Corasick algorithm. This code finds all words in the text that contain any of the initially given words.

Hashing

Reference problem: Problem C from here
Complexity: O(N) on precalculation, O(1) on query

Hashing in strings based problems. This code compares substrings using two hashes (one uses 2^64 as a modulo, another 10^9 + 7)

Manacher's algorithm

Reference problem: Problem L from here
Complexity: O(N)

Manacher's algorithm for finding all subpalindromes in the string.

Palindrome tree

Reference problem: #1750
Complexity: O(N)

Useful structure to deal with palindromes in strings. This code counts number of palindrome substrings of the string.

Prefix function

Reference problem: #1323
Complexity: O(N)

Calculating the prefix function of the given string.

Suffix Array

Reference problem: Problem I from here
Complexity: O(NlogN)

Building suffix array in O(NlogN). Also LCP array is calculated. This code counts number of different substrings in the string.

Trie

Reference problem: Problem B from here
Complexity: O(total length of strings)

Builds trie (tree with characters on the edges) from the set of strings. This code counts number of different substrings in the string.

Suffix Tree. Ukkonen's algorithm

Reference problem: Problem I from here
Complexity: O(N)

Ukkonen's algorithm for building the suffix tree. Uses sibling lists in the nodes. This code counts number of different substrings in the string.

Z function

Reference problem: #1324
Complexity: O(N)

Calculating the Z-function of the given string.