Compression and Run-Length

Compression is rarely the goal in competitive programming, but its ideas — run-length encoding, dictionary references, entropy coding — appear constantly as problem structure.

Run-length encoding (RLE)

Replace runs of identical characters with (character, count) pairs.

vector<pair<char,int>> rle(const string& s) {
    vector<pair<char,int>> r;
    for (size_t i = 0; i < s.size(); ) {
        size_t j = i;
        while (j < s.size() && s[j] == s[i]) j++;
        r.push_back({s[i], (int)(j - i)});
        i = j;
    }
    return r;
}

Where it matters in problems:

The input has $n \leq 1 0^{9}$ characters but only $1 0^{5}$ runs — solve on the RLE, not the string.
Operations that act on whole runs (flip a range, sort a range) — an interval map in a std::map is RLE with updates, and is the “Chtholly tree” technique.
Counting: “number of maximal blocks”, “longest run”, “minimum changes to make all runs length $\geq k$ ”.
Grid problems where rows repeat.

Lempel-Ziv

LZ77 replaces a substring by a reference to an earlier occurrence: a triple (distance, length, next character). LZ78 / LZW builds a dictionary of phrases instead.

The LZ factorisation (also called the s-factorisation) — the greedy decomposition of $s$ into the longest factors each of which occurred earlier — is a genuinely useful string-theory object:

computable in $O (n)$ from a suffix array + LCP, or from a suffix automaton;
the number of factors $z$ is a measure of the string’s repetitiveness;
it is the basis of the $O (n)$ runs algorithm and of several repetition-detection results;
$z \leq r$ where $r$ is the number of BWT runs, and both are $O (n / lo g n)$ for compressible strings.

Contest appearances are rare but real: “compress this string optimally with back-references” is an LZ factorisation, and greedy is provably optimal for the factor count.

Huffman coding

Optimal prefix-free coding by symbol frequency: repeatedly merge the two least frequent symbols. $O (n lo g n)$ with a heap. See Huffman Coding.

The competitive-programming form is usually disguised: “merge $n$ piles, cost = sum of the two merged, minimise the total” — identical problem, and the answer is the Huffman tree’s weighted path length.

When the leaf order is fixed, greedy fails and you need Hu-Tucker or an $O (n^{2})$ Knuth-optimised interval DP.

Burrows-Wheeler transform

Sort all rotations of $s$$ and take the last column. The result clusters equal characters together, which makes it highly compressible by RLE + move-to-front.

Computable in $O (n)$ from the suffix array: $BWT [i] = s [sa [i] - 1]$ .
Invertible via the LF-mapping, in $O (n)$ .
The basis of bzip2 and, with a rank structure (wavelet tree), of the FM-index used by DNA aligners.

Entropy — the theoretical floor

Shannon’s source coding theorem: no lossless code can beat the entropy

$H = - \sum_{i} p_{i} lo g_{2} p_{i} bits per symbol on average.$

Huffman is within 1 bit per symbol of $H$ ; arithmetic coding gets arbitrarily close.

Useful as a lower-bound argument: “any comparison sort needs $lo g_{2} (n!) = Ω (n lo g n)$ comparisons” is the same counting argument, and information-theoretic bounds of this shape are a standard way to prove a problem cannot be solved faster.

The techniques worth carrying

Work on the RLE, not the raw string, when runs are few.
Interval maps (std::map of maximal constant intervals) for range-assign operations.
Counting arguments — entropy and $lo g_{2} (number of outcomes)$ give lower bounds.
Back-reference structure — the LZ factorisation is the right formalism for “how repetitive is this string”.

See also: Huffman Coding · Suffix Array · Complexity Theory

whoashish's cp notes

Directory