Parrots
Encode a message of N 64 bytes into a multiset of integers in [0,255]. The decoder receives the integers in arbitrary order and must reconstruct the original message exactly.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Encode a message of $N \le 64$ bytes into a multiset of integers in $[0,255]$. The decoder receives the integers in arbitrary order and must reconstruct the original message exactly.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Messages as Ranks
Interpret the byte array as a base-$256$ integer \[ V = \sum_{i=0}^{N-1} M_i \cdot 256^i . \] There are exactly $256^N$ possible messages.
Encoded Multisets as Weak Compositions
Fix a length bound $T$. Any encoded multiset of length at most $T$ can be written as counts \[ c_0, c_1, \ldots, c_{255}, c_{256}, \] where $c_x$ is the number of occurrences of value $x$, and $c_{256}$ is a ``blank'' count so that \[ \sum_{x=0}^{256} c_x = T. \] Thus the number of possible encodings is the number of weak compositions of $T$ into $257$ parts: \[ \binom{T + 256}{256}. \] Choose the smallest $T$ such that $\binom{T + 256}{256} \ge 256^N$. For $N = 64$, this gives $T = 261$, which is the optimal full-score bound.
Ranking and Unranking
We map each message rank $V$ to the $V$-th weak composition in lexicographic order.
Suppose we still have $R$ slots to distribute and we are deciding the count of the current value. If we set it to $t$, then the number of completions is \[ \binom{(R - t) + K - 2}{K - 2}, \] where $K$ is the number of categories still available (current value, larger values, and blanks).
This gives:
an unranking procedure for the encoder, which converts $V$ into counts $c_x$;
a ranking procedure for the decoder, which reconstructs $V$ from the received counts.
Why the Order Does Not Matter
The sent data is only the multiset: value $x$ is transmitted exactly $c_x$ times. Since the decoder only needs the multiplicities, permutation of the transmitted numbers is harmless.
Complexity
Precomputation of binomial coefficients: $O(256 \cdot T)$ states.
Encoding and decoding: $O(256 \cdot T)$ big-integer operations.
Memory: $O(256 \cdot T)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
void send(int value);
void output(int value);
namespace {
constexpr int kAlphabet = 257; // 0..255 plus one blank symbol.
constexpr int kMaxMessageBytes = 64;
constexpr int kMaxEncodedLength = 261;
constexpr int kMaxChooseN = 256 + kMaxEncodedLength;
constexpr int kLimbs = 10;
struct BigInt {
array<uint64_t, kLimbs> limb{};
BigInt(uint64_t value = 0) {
limb.fill(0);
limb[0] = value;
}
bool operator<(const BigInt& other) const {
for (int i = kLimbs - 1; i >= 0; --i) {
if (limb[i] != other.limb[i]) {
return limb[i] < other.limb[i];
}
}
return false;
}
BigInt& operator+=(const BigInt& other) {
unsigned __int128 carry = 0;
for (int i = 0; i < kLimbs; ++i) {
unsigned __int128 sum = static_cast<unsigned __int128>(limb[i]) +
other.limb[i] + carry;
limb[i] = static_cast<uint64_t>(sum);
carry = sum >> 64;
}
return *this;
}
BigInt& operator-=(const BigInt& other) {
uint64_t borrow = 0;
for (int i = 0; i < kLimbs; ++i) {
uint64_t old = limb[i];
uint64_t sub = other.limb[i] + borrow;
limb[i] = old - sub;
borrow = (old < sub) || (borrow && sub == 0);
}
return *this;
}
void add_small(uint64_t value) {
unsigned __int128 carry = value;
for (int i = 0; i < kLimbs && carry > 0; ++i) {
unsigned __int128 sum = static_cast<unsigned __int128>(limb[i]) + carry;
limb[i] = static_cast<uint64_t>(sum);
carry = sum >> 64;
}
}
void shift_left_8() {
uint64_t carry = 0;
for (int i = 0; i < kLimbs; ++i) {
uint64_t next = limb[i] >> 56;
limb[i] = (limb[i] << 8) | carry;
carry = next;
}
}
void shift_right_8() {
uint64_t carry = 0;
for (int i = kLimbs - 1; i >= 0; --i) {
uint64_t next = limb[i] << 56;
limb[i] = (limb[i] >> 8) | carry;
carry = next;
}
}
int low_byte() const {
return static_cast<int>(limb[0] & 255);
}
};
bool initialized = false;
vector<vector<BigInt>> binom;
array<int, kMaxMessageBytes + 1> best_length{};
void init_tables() {
if (initialized) {
return;
}
initialized = true;
binom.assign(kMaxChooseN + 1, vector<BigInt>(257, BigInt(0)));
binom[0][0] = 1;
for (int n = 1; n <= kMaxChooseN; ++n) {
binom[n][0] = 1;
for (int k = 1; k <= min(n, 256); ++k) {
binom[n][k] = binom[n - 1][k - 1];
binom[n][k] += binom[n - 1][k];
}
}
best_length[0] = 0;
BigInt states = 1;
int length = 0;
for (int n = 1; n <= kMaxMessageBytes; ++n) {
states.shift_left_8();
while (binom[length + 256][256] < states) {
++length;
}
best_length[n] = length;
}
}
BigInt message_to_rank(int N, const int M[]) {
BigInt value = 0;
for (int i = N - 1; i >= 0; --i) {
value.shift_left_8();
value.add_small(M[i]);
}
return value;
}
vector<int> unrank_counts(int total, BigInt rank) {
vector<int> counts(kAlphabet, 0);
int remaining = total;
for (int symbol = 0; symbol + 1 < kAlphabet; ++symbol) {
int tail = kAlphabet - symbol - 2;
for (int cnt = 0; cnt <= remaining; ++cnt) {
const BigInt& ways = binom[remaining - cnt + tail][tail];
if (rank < ways) {
counts[symbol] = cnt;
remaining -= cnt;
break;
}
rank -= ways;
}
}
counts.back() = remaining;
return counts;
}
BigInt rank_counts(const vector<int>& counts) {
BigInt rank = 0;
int remaining = accumulate(counts.begin(), counts.end(), 0);
for (int symbol = 0; symbol + 1 < kAlphabet; ++symbol) {
int tail = kAlphabet - symbol - 2;
for (int cnt = 0; cnt < counts[symbol]; ++cnt) {
rank += binom[remaining - cnt + tail][tail];
}
remaining -= counts[symbol];
}
return rank;
}
} // namespace
void encode(int N, int M[]) {
init_tables();
int total = best_length[N];
BigInt rank = message_to_rank(N, M);
vector<int> counts = unrank_counts(total, rank);
for (int value = 0; value < 256; ++value) {
for (int rep = 0; rep < counts[value]; ++rep) {
send(value);
}
}
}
void decode(int N, int L, int X[]) {
init_tables();
int total = best_length[N];
vector<int> counts(kAlphabet, 0);
for (int i = 0; i < L; ++i) {
++counts[X[i]];
}
counts.back() = total - L;
BigInt rank = rank_counts(counts);
for (int i = 0; i < N; ++i) {
output(rank.low_byte());
rank.shift_right_8();
}
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.