Contest Algorithms in Rust

A collection of classic data structures and algorithms, emphasizing usability, beauty and clarity over full generality. As such, this should be viewed not as a blackbox library, but as a whitebox cookbook demonstrating the design and implementation of algorithms. I hope it will be useful to students and educators, as well as fans of algorithmic programming contests.

This repository is distributed under the MIT License. Contest submissions need not include the license text. Enjoy!

For Students and Educators

When learning a new algorithm or data structure, it's often helpful to see or play with a concrete implementation. As such, this repository catalogues several classic algorithms in their simplest forms.

In addition, the Rust language has outstanding pedagogical attributes. Its compiler acts as a teacher, enforcing strict discipline while pointing to clearer ways to structure one's logic.

For Programming Contests

The original intent of this project was to build a reference for use in programming contests. As a result, it contains algorithms that are frequently useful to have in one's toolkit, with an emphasis on code that is concise and easy to modify under time pressure.

Most competitive programmers rely on C++ for its fast execution time. However, it's notoriously unsafe, diverting a considerable share of the contestant's time and attention on mistake prevention and debugging. Java is the next most popular choice, offering a little safety at some expense to speed of coding and execution.

To my delight, I found that Rust eliminates entire classes of bugs, while reducing visual clutter to make the rest easier to spot. And, it's fast. There's a learning curve, to be sure. However, a proficient Rust programmer stands to gain a competitive advantage as well as a more pleasant experience!

Some contest sites and online judges that support Rust:

For help in getting started, you may check out some of my past submissions (requires login).

Programming Language Advocacy

My other goal is to appeal to developers who feel limited by ancient (yet still mainstream) programming languages, by demonstrating the power of modern techniques.

Rather than try to persuade you with words, this repository aims to show by example. If you'd like to learn the language, I recommend the official book or Programming Rust.

Contents

Graphs

Graph representations

Integer index-based adjacency list representation
Disjoint set union

Elementary graph algorithms

Euler path and tour
Kruskal's minimum spanning tree
Dijkstra's single-source shortest paths
DFS pre-order traversal

Connected components

Connected components
Strongly connected components
Bridges and 2-edge-connected components
Articulation points and 2-vertex-connected components
Topological sort
2-SAT solver

Network flows

Dinic's blocking maximum flow
Minimum cut
Hopcroft-Karp bipartite matching
Minimum cost maximum flow

Math

Number theory

Greatest common divisor
Canonical solution to Bezout's identity
Miller's primality test

Generic FFT

Fast Fourier transform
Number theoretic transform
Convolution

Arithmetic

Rational numbers
Complex numbers
Linear algebra
Safe modular arithmetic

Ordering and search

Comparator for PartialOrd
Binary search: drop-in replacements for C++ lower_bound()/upper_bound()
Merge and mergesort
Coordinate compression
Online convex hull trick (update and query the upper envelope of a set of lines)

Associative range query

Statically allocated binary indexed ARQ tree (a.k.a. generic segtree with lazy propagation)
Dynamically allocated ARQ tree, optionally sparse and persistent
Mo's algorithm (a.k.a. query square root decomposition)

Scanner

Utility for reading input data ergonomically
File and standard I/O examples

String processing

Generic trie
Knuth-Morris-Pratt single-pattern string matching
Aho-Corasick multi-pattern string matching
Suffix array: O(n log n) construction using counting sort
Longest common prefix
Manacher's linear-time palindrome search