Skip to content

Introduction to Space Optimization

Space optimization techniques are not very common in algorithm competitions, but they are still worth discussing.

Information Entropy

Information entropy describes the lower bound of space required to store data. If the actual available space is below this lower bound, information loss is inevitable.

Definition

For a random variable \(X\), define its information entropy as

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

The base of the logarithm in the definition is \(2\) because each bit of information stored in a computer can only take \(2\) values: \(0\) and \(1\).

For example, let \(X\) follow a uniform distribution over \(\{1,2,\dots,n\}\). Then 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 integers from \(1\) to \(n\).

Example Problem

[WC2022] Guess the Word

Interactive problem. You need to guess a 5-letter word within a limited number of attempts. Each guess must be a word from the dictionary. If you guess correctly, the game ends. After each incorrect guess, the interactor returns which letters are in the correct position and which letters appear in the target word but are in the wrong position.

Solution

Refer to Solving Wordle with Information Theory - 3Blue1Brown.

Consider computing information entropy. Clearly, choosing words with high information entropy for each guess minimizes the expected number of guesses.

Since the problem provides the first letter of the answer before guessing, we can precompute the optimal guess for each possible first letter.

Additionally, if very few candidate words remain, we can prioritize outputting words that could be the answer to reduce the number of attempts.

Common Techniques

Avoid Storing Unnecessary Data

For example:

  • In persistent segment trees, since each modification only creates \(O(\log n)\) new nodes, we do not need to store the entire segment tree for each version. It suffices to record only the new nodes.
  • Consider graph storage. For sparse graphs, using an adjacency matrix would store many useless \(0\)s. Therefore, adjacency lists are generally used for sparse graphs.
  • Each element of a bool array occupies one byte of space. When necessary, use std::vector<bool> (where each element occupies only one bit) or bitset instead.
  • In knapsack DP, for the 0/1 knapsack problem, each DP value computation only uses data from the previous computation. Thus, we can optimize space with a rolling array, only needing to record the current DP values.

Exploit Data Characteristics

Consider the union-find set (disjoint set union) with path compression and union by size. The traditional approach requires two arrays: one to record parent node indices and another to record subtree sizes.

Note that:

  1. After applying path compression, for a tree in the union-find set, we only need to record the subtree size of the root node.
  2. The parent of a root node is always itself.

We can exploit the properties of signed integers: use negative numbers to represent root nodes and positive numbers to represent non-root nodes. Thus, we only need one array to implement a union-find set with path compression and union by size.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdint>
#include <vector>
using i32 = int32_t;
using u32 = uint32_t;

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

 public:
  // Node indices 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);  // Heuristic merge
    p[x] += p[y], p[y] = (i32)x;
    return true;
  }
};

Exercises

References and Further Reading

  1. Chen Zhixuan. "A Brief Discussion on Space Optimization in Informatics Competitions." 2022 National Team Paper.
  2. Information theory - Wikipedia
  3. A Brief Introduction to Information Theory - Luogu Column
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用