Common Lisp code collection for competitive programming

This code collection is maintained mainly for competitive programming, and partly for just understanding algorithms.

License

The greater part of this library is distributed as public domain, or licensed under either CC0 or the MIT license, whichever gives you the most rights in your legislation. Some code, however, has its specific license (usually because it is a dead copy of other library). For the details, please see the header of each file.

Style

Although I put this code collection in a ASDF module, this project is primarily made for competitive programming and the whole structure will be quite different from a common ASDF library. I don't recommend that you directly load this module for your software.

On portability: I try to write portable code as long as the code structure doesn't get too complicated. However, I occasionally use extensions and behaviours of SBCL x86-64, mainly for performance reasons. Below is a SBCL-specific feature that I always depend on:

declaration as assertion

Below are the features that I sometimes use:

bivalent stream
extensible sequence
sb-ext:array-storage-vector and sb-kernel:%vector-raw-bits
sb-c:define-source-transform

Every data structure and algorithm uses a 0-based index and a half-open interval unless otherwise noted.

Test environment

SBCL 2.1.6 (x64, linux) — yukicoder's version
SBCL 2.0.3 (x64, linux) — AtCoder's version
SBCL 1.3.13 (x64, linux) — CodeChef's version
SBCL 1.3.1 (x64, linux) — HackerEarth's version

Unclassified data structures

queue.lisp queue with singly-linked list
deque.lisp double-ended queue with ring buffer
double-stack-deque.lisp double-ended queue with two stacks
binary-heap binary heap for static or dynamic order function
pairing-heap.lisp meldable heap (pairing heap)
radix-heap.lisp radix heap
segment-tree.lisp segment tree over an arbitrary monoid
simple-dual-segment-tree.lisp dual segment tree for a commutative operator
persistent-segment-tree.lisp persistent segment tree
persistent-starry-sky-tree.lisp persistent starry sky tree
binary-indexed-tree.lisp binary indexed tree (aka Fenwick tree) over an arbitrary commutative monoid
biset.lisp binary indexed tree for binary data
2d-bit.lisp 2D binary indexed tree
disjoint-set.lisp disjoint set by Union-Find algorithm
undoable-disjoint-set.lisp undoable disjoint set
persistent-disjoint-set.lisp partially persistent disjoint set
offline-dynamic-connectivity.lisp offline dynamic connectivity
ref-able-treap.lisp ordered set with treap; analogue of std::set or java.util.TreeSet
explicit-treap.lisp ordered map with treap; analogue of std::map or java.util.TreeMap
implicit-treap.lisp treap with implicit key
multiset.lisp multiset
interval-set.lisp ordered set of half-open intervals
disjoint-sparse-table.lisp disjoint sparse table on arbitrary semigroup
range-tree.lisp 2D range tree over an arbitrary commutative monoid
range-tree-fc.lisp 2D range tree with fractional cascading
convex-hull-trick.lisp convex hull trick
succinct-bit-vector.lisp three-layer succinct bit vector
compact-bit-vector.lisp two-layer compact bit vector
wavelet-matrix.lisp wavelet matrix
persistent-vector.lisp persistent vector
dice.lisp six-sided dice
swag.lisp sliding window aggregation
sliding-window.lisp sliding window extremum

Unclassified algorithms

cumulative-sum.lisp n-dimensional cumulative sum
bisect.lisp analogue of std::lower_bound and std::upper_bound
trisect.lisp extremum of strictly unimodal function
monotone-minima.lisp divide-and-conquer algorithm for monotone matrix
quicksort.lisp quicksort
merge-sort.lisp merge sort
inplace-merge-sort.lisp in-place merge sort
binsort.lisp bin sort; counting sort
map-permutations.lisp permutation and combination
next-permutation.lisp next permutation w.r.t. lexicographical order
inversion-sequence.lisp inversion sequence of permutation
mo.lisp Mo's algorithm
inverse-table.lisp inverse lookup table of vector
adjacent-duplicates.lisp deletion of adjacent duplicates
run-length.lisp run-length encoding
inversion-number.lisp counting inversions of vector by merge sort
lis.lisp longest increasing subsequence
mex.lisp minimum excludant on non-negative integers
quickselect.lisp expected O(n) algorithm for k-th order statistic of sequence
symmetric-group.lisp decomposition to cyclic permutations and some operations on a symmetric group
fkm.lisp Fredricksen, Kessler, and Maiorana algorithm
manhattan-fnn.lisp farthest neighbor points in d-dimensional L1 space
round-robin.lisp scheduling algorithm for a round robin tournament (circle method)
hackenbush.lisp game value of Hackenbush
date.lisp some utilities about date

Arithmetic and algebra

mod-power.lisp modular exponentiation
ext-gcd.lisp extended euclidean algorithm
mod-inverse.lisp modular inverse
mod-log.lisp modular logarithm
bsgs.lisp baby-step giant-step algorithm for discrete logarithm problem on (semi)group
bezout.lisp Bezout equation
mod-linear-algebra.lisp modular linear algebra
power.lisp exponentiation over an arbitrary monoid
binom-mod-prime.lisp binomial coefficient modulo prime; linear-time construction of tables of inverses, factorials, and inverse of factorials
binom-mod-small.lisp binomial coefficient modulo small number
partition-number.lisp partition number
bounded-partition-number.lisp partition number with upper-bound
perfect-kth-powers.lisp sequence of perfect powers
eulerian-polynomial.lisp Eulerian polynomial
mod-operations.lisp modular arithmetic
lagrange-interpolation.lisp Lagrange interpolation
eratosthenes.lisp enumeration of primes; prime factorization
linear-sieve.lisp linear sieve; fast prime factorization
divisor.lisp enumeration of divisors of a given number
divisor-table.lisp enumeration of divisors of first n natural numbers
primality.lisp primality test (deterministic Miller-Rabin)
integer-root integer nth root
gemm.lisp matrix multiplication over semiring
freiwald.lisp Freiwalds' algorithm
f2.lisp linear algebra on GF(2)
walsh-hadamard.lisp fast Walsh-Hadamard transform
zeta-transform.lisp fast zeta/Möbius transform
zeta-integer.lisp fast zeta/Möbius transform w.r.t. divisors or multiples of integer
farey.lisp iteration on Farey sequence
farey-next.lisp next/previous element on Farey sequence

Real and complex

fft.lisp complex FFT (radix-2)
fft-real.lisp real FFT (radix-2)
fft-recursive.lisp naive FFT by simple recursion
relative-error.lisp relative error
log-factorial.lisp logarithm of factorial (logarithm of gamma function)

Bit operations

bit-basher.lisp efficient operations on simple-bit-vector
gray-code.lisp Gray code
tzcount.lisp TZCNT operation
logreverse.lisp bit-reversal operation

Graph

bipartite-matching.lisp maximum bipartite matching (Ford-Fulkerson)
hopcroft-karp.lisp maximum bipartite matching (Hopcroft-Karp)
jonker-volgenant.lisp weighted bipartite matching (Jonker-Volgenant)
gabow-edmonds.lisp maximum non-bipartite matching (Gabow-Edmonds)
bipartite-p.lisp test of bipartiteness
bron-kerbosch.lisp maximum clique
ford-fulkerson.lisp maximum flow (Ford-Fulkerson algorithm)
dinic.lisp maximum flow (Dinic's algorithm)
lca.lisp lowest common anscestor (binary lifting)
binary-lifting LCA and path queries on a static tree or forest with weighted edge or vertex (binary lifting)
ssp.lisp minimum cost flow (SSP)
topological-sort.lisp topological sort on DAG
find-cycle.lisp (explicit) cycle detection
euler-tour.lisp Euler tour of tree
scc.lisp strongly connected component of directed graph (Tarjan's algorithm)
2sat.lisp 2SAT solver
2cc.lisp two-edge connected component of undirected graph
tree-centroid.lisp centroid decomposition of tree
chordal-graph.lisp recognition of graph chordality (maximum cardinality search); perfect elimination order
diameter.lisp diameter of tree
tree-hash.lisp hashing of rooted tree
mo-tree.lisp Mo's algorithm for paths on tree (vertex query)
random-graph.lisp fast generation of random adjacency matrices

Optimization

two-phase-simplex.lisp two-phase (dual-then-primal) simplex method for dense LP
self-dual-simplex.lisp parametric self-dual simplex method for dense LP
incremental-lp.lisp warm-start LP solver for dynamically added constraints, using dual simplex method for dense LP
sparse-simplex.lisp two-phase (dual-then-primal) simplex method and self-dual simplex method for sparse LP
ols.lisp ordinary least squares regression by Gaussian elimination

Euclidean geometry

complex-geometry.lisp some utilities for 2D geometry with complex number
phase.lisp order by amplitude (atan)
circumcenter.lisp circumcenter
welzl.lisp smallest circle problem (Welzl's algorithm)
convex-hull.lisp 2D convex hull (monotone chain algorithm)

String

rolling-hash31.lisp 31-bit rolling hash
rolling-hash62.lisp 62-bit rolling hash
2d-rolling-hash.lisp 2D 32-bit rolling hash
triemap.lisp map structure with trie
trie.lisp multiset structure with trie
z-algorithm.lisp Z-algorithm

I/O

read-line-into.lisp read-line into a given string
buffered-read-line.lisp read-line into a recycled string
read-fixnum.lisp faster read for fixnum
read-bignum.lisp faster read for bignum
write-double-float.lisp write double-float with fixed-point expression

Other utilities

template.lisp template code
mpfr.lisp header to load SB-MPFR
with-cache.lisp memoization of function
dotimes-unroll.lisp loop unrolling
placeholder-syntax.lisp Clojure-style placeholder syntax

Weird things

integer-pack.lisp defstruct-like macro to deal with an integer as a structure of several integer slots
increase-space.lisp This header runs another SBCL as external process and leaves the entire processing to it. (This ugly hack was invented to increase the stack size of SBCL on online judges.)
compile-time-increase-space.lisp analogue of increase-space at compile time

lbrock/cl-competitive