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

Currently I don't introduce any name spaces (packages) in each file. This is due to the circumstance unique to the competitive programming: one-file-per-submission. It is somewhat troublesome to manage many packages on a single file (especially when modifying inserted code). This style may change in the future, however.

On portability: I try not to abuse non-portable code though I sometimes resort to SBCL's extension and behaviour: e.g. declaration as assertion, bivalent stream, extensible sequence, sb-kernel:%vector-raw-bits and sb-c:define-source-transform. To my knowledge, every competition site adopts SBCL.

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

Test environment

SBCL 1.5.5 (x64, linux) — yukicoder's version
SBCL 1.3.13 (x64, linux) — CodeChef's version
SBCL 1.3.3 (x64, linux) — CS Academy's version
SBCL 1.2.4 (x64, linux) — the oldest intallable SBCL

Note that the version of SBCL is 1.1.14 on AtCoder.

General data structures

queue.lisp queue by singly-linked list
deque.lisp double-ended queue by ring buffer
abstract-heap binary heap for static order function
heap.lisp binary heap for dynamic order function
pairing-heap.lisp meldable heap (pairing heap)
abstract-bit.lisp binary indexed tree (aka Fenwick tree) on arbitrary commutative monoid
binary-indexed-tree.lisp binary indexed tree (specialized for ordinary +)
2d-bit.lisp 2D binary indexed tree
disjoint-set.lisp disjoint set by Union-Find algorithm
persistent-disjoint-set.lisp partially persistent disjoint set by Union-Find algorithm
ref-able-treap.lisp ordered set by treap; analogue of std::set or java.util.TreeSet
explicit-treap.lisp ordered map by treap; analogue of std::map or java.util.TreeMap
implicit-treap.lisp treap with implicit key
disjoint-sparse-table.lisp disjoint sparse table on arbitrary semigroup
range-tree.lisp 2D range tree on 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
wavelet-matrix.lisp wavelet matrix (with compact bit vector)
dice.lisp six-sided dice

General algorithms

bisect.lisp analogue of std::lower_bound and std::upper_bound
trisect.lisp maximum (minimum) of unimodal function
binsort.lisp bin sort; counting sort
map-permutations.lisp permutation and combination
mo.lisp Mo's algorithm
make-inverse-table.lisp inverse lookup table of vector
adjacent-duplicates.lisp deletion of adjacent duplicates
map-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
sliding-window.lisp sliding window minimum (or maximum)
order-statistic.lisp expected O(n) algorithm for k-th order statistic of sequence
cyclic-permutation.lisp decomposition to cyclic permutations
fkm.lisp Fredricksen, Kessler, and Maiorana algorithm

Arithmetic and algebra

modular-arithmetic.lisp extended Euclidean algorithm; Bezout equation; modular inverse; discrete logarithm; Gaussian elimination
power-mod.lisp modular exponentiation
power.lisp exponentiation on arbitrary monoid
binomial-coefficient-mod.lisp binomial coefficient with fixed modulus; building tables of inverses, factorials, and inverses of factorials in O(n)
binomial-coefficient.lisp binomial coefficient by direct bignum arithmetic
partition-number.lisp partition number
bounded-partition-number.lisp partition number with upper-bound
dynamic-mod-operations.lisp addition/multiplication with dynamic modulus
mod-operations.lisp addition/multiplication with static modulus
eratosthenes.lisp enumeration of primes; prime factorization
ext-eratosthenes.lisp faster prime factorization than naive trial division
divisor.lisp enumeration of divisors
enum-quotients.lisp enumeration of truncated quotients
gemm.lisp matrix multiplication over semiring
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 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 64-times faster 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)
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)
min-cost-flow.lisp minimum cost flow (SSP)
prim.lisp minimum spanning tree (Prim's algorithm)
topological-sort.lisp topological sort on DAG
dfs-order.lisp Euler tour of tree
condensation.lisp strongly connected component of directed graph; 2-SAT
block-cut-tree.lisp biconnected component of undirected graph; block-cut tree
tree-centroid.lisp centroid decomposition of tree
random-graph.lisp fast generation of random adjacency matrices

Geometry

complex-geometry.lisp some utilities for 2D geometry with complex number; smallest circle problem (Welzl's algorithm)
convex-hull.lisp 2D convex hull (monotone chain algorithm)

Pattern matching

rolling-hash.lisp 32-bit rolling hash
rolling-hash62.lisp 62-bit rolling hash
2d-rolling-hash.lisp 2D 32-bit rolling hash
triemap.lisp map structure by Trie
trie.lisp multiset structure by 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
with-buffered-stdout.lisp buffering macro for *standard-output*

Other utilities

template.lisp template code
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 bundle of some slots
increase-stack-size.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 contest sites.)
self-compile.lisp self-rewriting compilation

Symbolics/cl-competitive