AIOJ

Space optimization techniques are not particularly common in algorithm contests, but they are still worth discussing．

Entropy

Information entropy describes the lower bound on the space needed to store data. If the actually available space is below this bound, information must be lost．

Definition

For a random variable $X$ , information entropy is defined as

H(X)=-\sum_{x}P(X=x)\log_2 P(X=x).

The logarithm has base $2$ because the information stored in a computer has only $2$ possible values per bit: $0$ and $1$ ．

For example, suppose $X$ follows the uniform distribution on $\{1,2,\dots,n\}$ . Its information entropy is

H(X)=-\sum_{i=1}^n\frac{1}{n}\log_2\frac{1}{n}=\log_2 n,

so we need at least $\log_2 n$ bits to store the integers from $1$ through $n$ ．

Example Problem

[WC2022] Guess the Word

This is an interactive problem. Within a limited number of attempts, you must guess a five-letter word. Each guess must be a word in the word bank. If you guess correctly, the game ends. After each incorrect guess, the judge tells you which letters are in the correct positions and which letters occur in the target word but are in the wrong positions．

Solution

See Solving Wordle with information theory - 3Blue1Brown．

Consider the information entropy. Clearly, choosing a word with high information entropy for each guess minimizes the expected number of guesses．

Because this problem gives the first letter of the answer before guessing, we can preprocess the optimal guess for each possible initial letter．

If only a few words remain, we can also prioritize outputting words that could be the answer, thereby reducing the number of guesses．

Common Techniques

Avoid Storing Unnecessary Data

For example:

In a persistent segment tree, each modification creates only $O(\log n)$ new nodes, so we do not need to store the complete segment tree for every version; recording only the new nodes is enough．
Consider graph storage. For a sparse graph, an adjacency matrix stores a large number of useless $0$ s, so an adjacency list is generally used instead．
Each element of a bool array occupies one byte of space. When necessary, it can be replaced by std::vector<bool>, where each element occupies only one bit, or by a bitset．
In knapsack DP, each 0-1 knapsack DP value uses only the data from the previous computation, so a rolling array can optimize space and only the current DP values need to be stored．

Taking Advantage of Data Properties

Consider the disjoint-set union with path compression and union by size. The traditional approach requires two arrays, recording the parent node number and subtree size separately．

Observe that:

After path compression is applied, for a tree in the disjoint-set union, we only need to record the subtree size corresponding to its root．
The parent of a root is always itself．

We can use the properties of signed integers: negative values represent root nodes, and positive values represent non-root nodes. Thus, a disjoint-set union supporting path compression and union by size can be implemented with only one array．

Implementation

#include <cstdint>
#include <vector>
using i32 = int32_t;
using u32 = uint32_t;

class dsu {
  // When p[i] < 0, i is a root and its subtree size is -p[i]
  // When p[i] >= 0, i is not a root and its parent node number is p[i]
  std::vector<i32> p;

 public:
  // Node numbers range from 0 to sz-1
  explicit dsu(u32 sz) : p(sz, -1) {}

  i32 find(u32 x) { return p[x] < 0 ? (i32)x : p[x] = find((u32)p[x]); }

  u32 size(u32 x) { return (u32)-p[(u32)find(x)]; }

  bool same_root(u32 x, u32 y) { return find(x) == find(y); }

  bool merge(u32 x, u32 y) {
    if ((x = (u32)find(x)) == (y = (u32)find(y))) return false;
    if (p[x] > p[y]) std::swap(x, y);  // Union by size
    p[x] += p[y], p[y] = (i32)x;
    return true;
  }
};

Exercises

References and Further Reading

Chen Zhixuan．《A Brief Discussion of Space Optimization in Informatics Competitions》．2022 National Training Team Paper
Information theory - Wikipedia
A Brief Discussion of Information Theory - Luogu Column