Skip to content

Latest commit

 

History

History
505 lines (363 loc) · 23 KB

README.md

File metadata and controls

505 lines (363 loc) · 23 KB
Raw

CircleCI

This repo contains algorithms and data structures written for use in online programming competitions.

These programs have been validated against real competition problems using online judges.

For example, test/data_structures/segment_tree/distinct_characters_queries/ contains a solution to the problem Distinct Characters Queries using data_structures/segment_tree.cpp:

// Problem: https://codeforces.com/problemset/problem/1234/D

#include <iostream>
using namespace std;

// {{{ data_structures/segment_tree }}}

int main() {
...

Replacing the comment // {{{ path/to/source }}} with the library code produces a complete solution. Sample inputs and outputs for the problem are rehosted in this repo and serve as unit tests.

Contents

Usage

All classes compile on C++ 17.

Some files require the contents of other files, denoted by a comment // {{{ <filepath> }}}. If you would like to generate buildable code from the usage examples, a small script is provided to pull in dependencies. Run:

python2 expand_dependencies.py <input path> <output path> <path to repository root>

Passing function objects as arguments

Some functions expect function objects as arguments, typically either:

  • A binary operation used to accumulate stored values (e.g. segment_tree's constructor)
  • A unary operation used to initialize a range of elements (e.g. segment_tree's assign)

You can pass a function pointer:

int add(int a, int b) {
    return a + b;
}

segment_tree<int, int(*)(int, int)> s(SZ, 0, add);

Or a lambda expression:

auto add = [](int a, int b) {
    return a + b;
};

segment_tree<int, decltype(add)> s(SZ, 0, add);

Or a struct with operator ():

struct adder {
    int operator()(int a, int b) {
        return a + b;
    }
};

segment_tree<int, adder> s(SZ, 0, adder{});

functional.h defines some useful function objects:

segment_tree<int, plus<int>> s(SZ, 0, plus<int>());

Since C++17 you can generally omit the template arguments:

segment_tree s(SZ, 0, [](int a, int b) { return a + b; });

Passing iterators as arguments

Some functions expect a pair of iterators first and last as arguments (e.g. knuth_morris_pratt's constructor).

  • The range of elements operated on is always the semi-open interval [first, last).

You'll typically pass either string iterators:

string s;
knuth_morris_pratt kmp(s.begin(), s.end());

Or vector iterators:

vector<int> s;
knuth_morris_pratt kmp(s.begin(), s.end());

Data Structures

Union Find

Maintains a partition of the set {0, 1, ..., N-1} supporting:

  • Retrieval of an identifier for the subset containing a specified element
  • Replacement of two specified subsets with their union

Amortized runtime complexity is near constant for both operations.

Usage Examples:

Union Find (Bipartite)

Maintains information about bipartitions of the set {0, 1, ..., N-1} supporting:

  • Constrainment of two specified elements to appearing in opposite subsets
  • Constrainment of two specified elements to appearing in the same subset
  • Constrainment of a specified element to a specified subset
  • Counting the number of bipartitions satisfying all configured constraints
  • Computing the smallest size of a particular subset over all satisfying bipartitions

Amortized runtime complexity is near constant for all operations.

Usage Examples:

Union Find (Rewindable)

Maintains a partition of the set {0, 1, ..., N-1} supporting:

  • Retrieval of an identifier for the subset containing a specified element in O(log(N))
  • Replacement of two specified subsets with their union in O(1)
  • Reversion of the most recent "union" operation in O(1)

Can process a sequence of E edge insertions and deletions in O(E log(E) log(N)).

Usage Examples:

Segment Tree

Maintains an array of N elements supporting:

  • Modification of a specific element in O(log(N))
  • Accumulation of a range of elements in O(log(N))

Usage Examples:

Segment Tree (Lazy Propagation)

Maintains an array of N elements supporting:

  • Modification of a range of elements in O(log(N))
  • Accumulation of a range of elements in O(log(N))

Usage Examples:

Segment Tree (Persistent)

Maintains an array of N elements supporting:

  • Modification of a specific element at a specified point in time in O(log(N))
  • Accumulation of a range of elements as they were at a specified point in time in O(log(N))

Writes must be made with non-decreasing timestamps; there is no restriction on reads. Reads and writes can be interspersed in an arbitrary fashion.

Consumes O(log(N)) additional memory on each write.

Usage Examples:

Segment Tree (Searchable)

Adds a binary search feature to the Segment Tree class which accepts an index first and a predicate p, returning the first index last such that p(accumulate(first, last)) evaluates to true. Requires that the predicate is non-decreasing as last increases.

Rounds up internal size to the next power of 2. For a segment tree over N elements, search is O(log(N)).

Usage Examples:

Binary Indexed Tree

Maintains an array of N elements supporting:

  • Modification of a specific element in O(log(N))
  • Accumulation of a prefix of elements in O(log(N))

Less general than a Segment Tree; offers better constant factor performance.

Usage Examples:

Sparse Table

Accepts a static array of N elements and an idempotent binary operation f. Supports:

  • Accumulation of a range of elements in O(1)

Precomputation is O(N log(N)). Typically used with f = min<T> or f = max<T>.

Usage Examples:

Sqrt Decomposition (Range Update, Point Query)

Maintains an array of N elements supporting:

  • Modification of a range of elements in O(sqrt(N))
  • Querying the value of a single element in O(1)

Usage Examples:

Line Container

Maintains a collection of lines. Supports:

  • Insertion of a line f(x) = a * x + b
  • Querying for the maximum value among all inserted lines at a specified value of x

Runtime complexity for both operations is O(log(container size)).

Usage Examples:

Line Container (Monotonic)

Maintains a collection of lines. Supports:

  • Insertion of a line f(x) = a * x + b, where a is non-decreasing across all insertions
  • Querying for the maximum value among all inserted lines at a specified value of x

Runtime complexity for insertion is amortized O(1). Runtime complexity for arbitrary queries is O(log(container size)). If get_maximum_monotonic is used, total runtime complexity over a sequence of queries made with non-decreasing x is linear.

Usage Examples:

Static to Dynamic Transformation

Adds the ability to insert new elements into a static data structure. Requires that queries to the data structure are decomposable; for any pair of disjoint sets of elements, the answer to a query over their union must be computable from answers to the query over the individual sets.

Over a sequence of N insertions, the K-th most recently inserted element is involved in log(K) constructions of the static data structure. A query made after N elements have been inserted is decomposed into log(N) queries on disjoint subsets of the inserted elements.

Usage Examples:

Graphs

Tree

Computes and stores basic properties of a rooted tree on V nodes:

  • The parent, depth, and subtree size of each node
  • The neighbor list for each node in non-increasing order of subtree size
  • A preorder traversal of the tree

Precomputation is O(V log(V)) to compute sorted neighbor lists and O(V) otherwise.

Usage Examples:

Lowest Common Ancestor

Computes and stores the euler tour representation of a tree on V nodes:

  • Supports queries for the lowest common ancestor of two nodes in O(1)
  • Supports queries for the distance between two nodes in O(1)
  • Supports queries for whether the simple path between two nodes visits a third node in O(1)
  • Supports queries for whether a specified node is an ancestor of another in O(1)
  • Supports queries for the first step on the simple path between two nodes in O(1)

Precomputation is O(V log(V)).

Usage Examples:

Heavy Path Decomposition

Given a rooted tree on V nodes, computes a permutation p of its vertices such that:

  • Any simple path in the tree can be decomposed into log(V) contiguous oriented intervals in p
  • Any subtree's vertex set occurs as a single contiguous interval in p

Accepts an instance of the Tree class. Additional precomputation is O(V).

Usage Examples:

Dijkstra

An implementation of Dijkstra's Algorithm for computing shortest path trees.

Runs in O(V + E log(E)) on a graph with V vertices and E edges.

Usage Examples:

Two Sat

Implication graph for boolean two-satisfiability. Constructs a satisfying assignment or detects that none exist. Runtime is linear in the size of the implication graph.

Classifies each variable as true in all satisfying assignments, false in all satisfying assignments, or neither. Runtime is O(N * N / MACHINE_WORD_SIZE).

Usage Examples:

Min Cost Vertex Cover

Given a graph on N weighted vertices, computes the minimum total weight among vertex covers of the graph. A vertex cover is a set of vertices that includes at least one endpoint of every edge of the graph.

Runs in O(V * 2^(V/2)) on a graph with V vertices.

Usage Examples:

Misc

Subset Sum

Given a set of integers with sum T, computes its set of subset sums in O(T sqrt(T) / MACHINE_WORD_SIZE).

Usage Examples:

Count Distinct In Range

Processes a sequence of comparable elements and a parameter copies_allowed. Supports queries for the number of elements in a specified range of the sequence if only the first copies_allowed appearances of each distinct value are counted.

Usage Examples:

Numeric

ModNum

Performs modular arithmetic:

  • Implements basic operators (+, -, *, /)
  • Computes inverses in O(log(MOD))
  • Computes discrete logarithms in O(sqrt(MOD))
  • Caches roots of unity
  • Caches factorials and inverse factorials to compute:
    • Binomial coefficients in O(1)
    • Inverses in O(1)

MOD is configured as a template parameter. If the modulus isn't known at compile-time, move MOD inside the struct as a static member.

Usage Examples:

Number Theoretic Transform

Convolves polynomials over the field of integers modulo P.

Requires that P is prime. Let D be the smallest power of 2 exceeding the degree of the returned polynomial. D must divide P-1.

The runtime complexity is O(D log(D)).

Usage Examples:

Complex FFT

Convolves polynomials over the field of doubles.

Provides a routine for convolution of polynomials over the integers modulo P without Number Theoretic Transform's constraint that D divides P - 1. This routine seems to be safe for N,M <= 150,000 but isn't precise enough for some adversarial cases around N = M = 180,000.

Usage Examples:

Discrete Logarithm

Given integers x, y, and MOD, computes and returns the smallest non-negative integer K such that x^K === y (mod MOD). Returns -1 if no such integer exists. Runs in O(sqrt(MOD)).

Usage Examples:

Tonelli-Shanks

Given integers n and MOD, computes and returns an integer r such that r * r === n (mod MOD). Returns -1 if no such integer exists.

Requires that MOD is a prime power. If MOD = 2^S * Q with Q odd, runs in O(S log(S) / log(log(S))).

Usage Examples:

BigNum (Add Power of 2, Compare)

Large integer representation. Starts with a representation of 0 and supports:

  • Representation of the sum of a represented integer with an arbitrary power of 2
  • Comparison of two represented integers

Runtime complexity for both operations is logarithmic in the number of digits of precision. Constructing a sum also consumes additional memory logarithmic in the number of digits of precision.

Usage Examples:

Strings

Knuth-Morris-Pratt

Given a string S, computes for each prefix the longest proper suffix which is also a prefix of S. Supports:

  • Characterizing occurrences (and partial occurrences) of S in a specified pattern T in O(|T|)

Precomputation is O(|S|).

Usage Examples:

Z Algorithm

Given a string S, computes the length of the longest common prefix between S and each of its suffixes.

Runs in O(|S|).

Usage Examples:

Palindromes

Given a string S:

  • Computes the length of the longest palindrome centered at each character
  • Computes the length of the longest palindrome centered between each pair of adjacent characters
  • Supports queries for the length of the longest palindrome within a specified substring of S in O(log(|S|))

Precomputation is O(|S|). Additional precomputation for substring queries is O(|S| log(|S|)).

Usage Examples:

Polynomial Hash

A rolling hash for probabilistic string equality checks. Supports:

  • Hashing a character in O(1)
  • Concatenating two hashes in O(1)
  • Computing hashes for all prefixes of a given string S in O(|S|)
  • Given prefix hashes for a string S, extracting the hash for an arbitrary substring of S in O(1)

Increasing parameter EvaluationPoints lowers the probability of two distinct strings producing the same hash.

Usage Examples:

Suffix Array

Given a string S:

  • Computes the lexicographic ordering of its suffixes
  • Computes the length of longest common prefix between each pair of adjacent suffixes in the lexicographic ordering
  • Supports queries for the longest common prefix between an arbitrary pair of suffixes
  • Supports queries for the range of ranks at which a specified substring occurs
  • Supports queries for the first occurrence of a specified substring

Precomputation is O(|S| log(|S|)).

Usage Examples:

Suffix Automaton

Given a string S, computes the minimal finite automaton accepting all suffixes of S.

  • Supports queries for the first occurrence in S of a specified pattern T in O(|T|)
  • Supports queries for the number of occurrences in S of a specified pattern T in O(|T|)

Precomputation is O(|S|).

Usage Examples:

Trie

Given a collection of strings S, supports:

  • Computing the total number of occurrences over all strings in S within a specified pattern T in O(|T|)
  • Computing the number of occurrences of each string in S within a specified pattern T in O(|S| + |T|)
  • Finding the indices of all occurrences of each string in S within a specified pattern T in O(|T| + |S| + total number of occurrences)

Precomputation is linear in the sum of the lengths of the strings in S.

Usage Examples:

Mutable String

Maintains a string over a finite alphabet, supporting:

  • Modification of a specified character in O(sqrt(|S|))
  • Queries for the number of appearances of a specified pattern T in a specified substring of S in O(|T|sqrt(|S|))

Usage Examples:

Mutable String (Bitset)

Maintains a string over a finite alphabet, supporting:

  • Modification of a specified character in O(1)
  • Queries for the number of appearances of a specified pattern T in a specified substring of S in O(|T| * |S| / MACHINE_WORD_SIZE)

Usage Examples: