Saveit
Given a connected graph with N nodes (N 1000) and H hub nodes (H 36, nodes 0,, H-1), encode the shortest-path distances from every hub to every node into a bit string. The decoder must reconstruct all H N distances fr...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Given a connected graph with $N$ nodes ($N \le 1000$) and $H$ hub nodes ($H \le 36$, nodes $0, \ldots, H-1$), encode the shortest-path distances from every hub to every node into a bit string. The decoder must reconstruct all $H \times N$ distances from the bit string. The bit budget is approximately $70{,}000$ bits.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key Insight
Compute a BFS spanning tree $\mathcal{T}$ rooted at hub $0$. For any tree edge $(u, \mathrm{parent}(u))$ and any hub $h$, the triangle inequality on the tree gives: \[ d_h(u) - d_h(\mathrm{parent}(u)) \in \{-1, 0, +1\}. \] Hence we can encode these differences instead of absolute distances.
Encoding Scheme
Tree structure: Encode $\mathrm{parent}(v)$ for $v = 1, \ldots, N-1$ using $\lceil \log_2 N \rceil = 10$ bits each. Total: $10(N-1) \le 9{,}990$ bits.
Differences: For each hub $h$ and each non-root node $v$ (in BFS order), encode \[ \delta_{h,v} = d_h(v) - d_h(\mathrm{parent}(v)) + 1 \in \{0, 1, 2\}. \] This is a base-3 digit. Pack pairs of digits into a base-9 value requiring 4 bits. Total: $\lceil H(N-1)/2 \rceil \cdot 4 \le 36 \cdot 500 \cdot 4 = 72{,}000$ bits.
Combined: at most $9{,}990 + 72{,}000 \approx 82{,}000$ bits, within the budget with careful packing.
Decoding
Read the parent array to reconstruct $\mathcal{T}$.
Read and unpack the base-3 differences.
For each hub $h$, set $d_h(\text{root}) = 0$ for hub $0$ (the root). For other hubs, the distance from hub $h$ to the root is reconstructed by traversing the tree using the differences.
Reconstruct all distances: $d_h(v) = d_h(\mathrm{parent}(v)) + (\delta_{h,v} - 1)$, processing nodes in BFS order.
Complexity
Encode time: $O(H(N + M))$ for BFS from each hub.
Decode time: $O(HN)$.
Bits: $O(N \log N + HN)$.
Code
C++ solution used for this page.
// IOI 2010 - Saveit
// Encode/decode shortest-path distances via BFS spanning tree + base-3 diffs.
// Bits: O(N log N + H * N).
#include <bits/stdc++.h>
using namespace std;
// Grader-provided bit I/O.
void encode_bit(int b);
int decode_bit();
// ===== ENCODER =====
void encode(int N, int H, int M, vector<pair<int, int>> &edges) {
vector<vector<int>> adj(N);
for (auto &[u, v] : edges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// BFS from node 0 to build spanning tree.
vector<int> parent(N, -1);
vector<int> bfsOrder;
vector<bool> visited(N, false);
queue<int> q;
q.push(0); visited[0] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
bfsOrder.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
parent[v] = u;
q.push(v);
}
}
}
// Encode parent array: 10 bits per node (N <= 1000).
const int BITS = 10;
for (int i = 1; i < N; i++) {
for (int b = BITS - 1; b >= 0; b--) {
encode_bit((parent[i] >> b) & 1);
}
}
// BFS from each hub to get all distances.
vector<vector<int>> dist(H, vector<int>(N, -1));
for (int h = 0; h < H; h++) {
queue<int> bfs;
bfs.push(h); dist[h][h] = 0;
while (!bfs.empty()) {
int u = bfs.front(); bfs.pop();
for (int v : adj[u]) {
if (dist[h][v] == -1) {
dist[h][v] = dist[h][u] + 1;
bfs.push(v);
}
}
}
}
// Encode distance differences along BFS tree edges.
// delta = dist[h][v] - dist[h][parent[v]] + 1, values in {0, 1, 2}.
// Pack two base-3 values into 4 bits (0..8 < 16).
vector<int> deltas;
for (int h = 0; h < H; h++) {
for (int i = 1; i < N; i++) {
int v = bfsOrder[i];
int p = parent[v];
int d = dist[h][v] - dist[h][p] + 1;
deltas.push_back(d);
}
}
if (deltas.size() % 2 != 0) deltas.push_back(0);
for (int i = 0; i < (int)deltas.size(); i += 2) {
int val = deltas[i] * 3 + deltas[i + 1];
for (int b = 3; b >= 0; b--) {
encode_bit((val >> b) & 1);
}
}
}
// ===== DECODER =====
void decode(int N, int H) {
const int BITS = 10;
// Read parent array.
vector<int> parent(N, -1);
for (int i = 1; i < N; i++) {
int p = 0;
for (int b = BITS - 1; b >= 0; b--) {
p |= (decode_bit() << b);
}
parent[i] = p;
}
// Reconstruct BFS order from tree.
vector<vector<int>> children(N);
for (int i = 1; i < N; i++) children[parent[i]].push_back(i);
vector<int> bfsOrder;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
bfsOrder.push_back(u);
for (int c : children[u]) q.push(c);
}
// Read packed deltas.
int totalDeltas = H * (N - 1);
int paddedSize = (totalDeltas + 1) / 2 * 2;
vector<int> deltas;
for (int i = 0; i < paddedSize; i += 2) {
int val = 0;
for (int b = 3; b >= 0; b--) {
val |= (decode_bit() << b);
}
deltas.push_back(val / 3);
deltas.push_back(val % 3);
}
// Reconstruct distances.
vector<vector<int>> dist(H, vector<int>(N, 0));
int idx = 0;
for (int h = 0; h < H; h++) {
for (int i = 1; i < N; i++) {
int v = bfsOrder[i];
int p = parent[v];
int d = deltas[idx++] - 1; // map {0,1,2} back to {-1,0,+1}
dist[h][v] = dist[h][p] + d;
}
}
// Output distances.
for (int h = 0; h < H; h++) {
for (int v = 0; v < N; v++) {
cout << dist[h][v];
if (v + 1 < N) cout << " ";
}
cout << "\n";
}
}
// Stub main; in contest, grader calls encode/decode directly.
int main() {
return 0;
}
void encode_bit(int /*b*/) {}
int decode_bit() { return 0; }
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.