Message
Each packet has 31 bits. Cleopatra controls exactly 15 positions (known to Aisha), while the other 16 positions are always transmitted correctly. Aisha must send a bit string M of length at most 1024, and Basma must r...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Each packet has 31 bits. Cleopatra controls exactly 15 positions (known to Aisha), while the other 16 positions are always transmitted correctly. Aisha must send a bit string $M$ of length at most $1024$, and Basma must recover it without knowing which 16 positions are safe.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Safe Positions Form a Cycle
Let the safe positions in cyclic order be \[ a_1 < a_2 < \cdots < a_{16}, \] and define \[ d_i = (a_{i+1} - a_i) \bmod 31, \] where $a_{17} = a_1$. Because there are 16 safe positions and 15 controlled ones, \[ 1 \le d_i \le 16 \qquad\text{and}\qquad \sum_{i=1}^{16} d_i = 31. \]
Encoding the Safe Positions
For each safe position $a_i$, Aisha writes a single marker bit:
position $a_i$ is set to $1$ in packet number $d_i - 1$;
in earlier packets, that safe position stays $0$.
So Basma can read, for every column, the index of the first packet containing a $1$. For a safe column this value is exactly $d_i$.
Now define a directed graph on positions $0,\dots,30$ by \[ b \to (b + \text{nxt}[b]) \bmod 31, \] where
nxt[b]is the first packet index containing a $1$ in column $b$, plus one. The 16 safe positions form the unique directed cycle of length 16, so Basma can recover all safe columns from the first 16 packets.
Sending the Message
After the marker packet for column $a_i$, every later packet can use that safe bit for payload. Hence, with $Q$ packets the number of reliable payload bits is \[ 16Q - \sum d_i = 16Q - 31. \] Append one terminal bit $1$ after the message and then pad with zeros. With \[ Q = \max\!\left(16, \left\lceil \frac{|M|}{16} \right\rceil + 2\right), \] we have $16Q - 31 \ge |M| + 1$. In particular, for $|M| \le 1024$, this gives $Q \le 66$, which is the full-score bound.
Complexity
Encoding and decoding both take $O(31Q)$ time.
Memory usage is $O(31Q)$.
The number of packets is at most $66$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
vector<bool> send_packet(vector<bool> A);
namespace {
constexpr int kPacketBits = 31;
constexpr int kSafeBits = 16;
} // namespace
void send_message(vector<bool> M, vector<bool> C) {
int packet_count = max(kSafeBits, static_cast<int>((M.size() + 15) / 16) + 2);
vector<vector<bool>> packets(packet_count, vector<bool>(kPacketBits, false));
vector<int> nxt(kPacketBits, 1);
for (int bit = 0; bit < kPacketBits; ++bit) {
if (C[bit]) {
continue;
}
while (C[(bit + nxt[bit]) % kPacketBits]) {
++nxt[bit];
}
packets[nxt[bit] - 1][bit] = true;
}
int pos = 0;
for (int packet = 0; packet < packet_count; ++packet) {
for (int bit = 0; bit < kPacketBits; ++bit) {
if (C[bit] || nxt[bit] > packet) {
continue;
}
packets[packet][bit] = (pos < static_cast<int>(M.size()) ? M[pos]
: pos == static_cast<int>(M.size()));
++pos;
}
}
for (const auto& packet : packets) {
send_packet(packet);
}
}
vector<bool> receive_message(vector<vector<bool>> R) {
vector<int> nxt(kPacketBits, 0);
int prefix_packets = min(static_cast<int>(R.size()), kSafeBits);
for (int bit = 0; bit < kPacketBits; ++bit) {
for (int packet = 0; packet < prefix_packets; ++packet) {
if (R[packet][bit]) {
nxt[bit] = packet + 1;
break;
}
}
}
vector<bool> controlled(kPacketBits, true);
for (int start = 0; start < kPacketBits; ++start) {
int cycle_len = 0;
vector<bool> in_cycle(kPacketBits, false);
for (int bit = (start + nxt[start]) % kPacketBits; !in_cycle[bit];
bit = (bit + nxt[bit]) % kPacketBits) {
in_cycle[bit] = true;
++cycle_len;
}
if (cycle_len == kSafeBits) {
for (int bit = 0; bit < kPacketBits; ++bit) {
controlled[bit] = !in_cycle[bit];
}
break;
}
}
vector<bool> M;
for (int packet = 0; packet < static_cast<int>(R.size()); ++packet) {
for (int bit = 0; bit < kPacketBits; ++bit) {
if (!controlled[bit] && nxt[bit] <= packet) {
M.push_back(R[packet][bit]);
}
}
}
while (!M.empty() && !M.back()) {
M.pop_back();
}
if (!M.empty()) {
M.pop_back();
}
return M;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.