Recover an Erased Transmission
National Olympiad — National round (2019 season)
Submission name: transmission.cpp
Problem summary
Design an encoder and decoder for N random unbiased data bits when exactly D transmitted bits are deleted, possibly in adjacent bursts. Maximize the number of correctly reconstructed source bits relative to the transmitted length. This is a scored optimization problem, so reliable reconstruction and low redundancy compete.
Source clarification. This is a scored communication task. The one-deletion branch guarantees exact reconstruction. The general branch supplies a full-domain probabilistic protocol, with a model-dependent expected-error justification and measured burst results; it does not guarantee maximum judge points or exact reconstruction.
Input
Implement std::vector<bool> transmit(const std::vector<bool>& data, int d) in transmit.cpp and std::vector<bool> receive(const std::vector<bool>& message, int n, int d) in receive.cpp. Include transmission.h. The grader calls each function once in separate processes. The receiver sees only the subsequence remaining after exactly d deletions, plus n and d.
Output
transmit returns at most 100000 bits. receive returns exactly n reconstructed bits. With c correct bits and M transmitted bits, raw score=(2c−N)/max(M−D,N). A test earns positive points only when c>N/2; its points are scaled by min(yourScore/authorScore,1).
Constraints
N=10000; 1≤D≤1000; M≤100000. Source bits are independent unbiased random bits. Deletion positions are generated independently of the meaningful message content, in random adjacent groups of length K; K is not given to either function.
Worked example
The official communication is an illustration of the supplied naive functions, not a required output sequence for this encoder. The local test harness invokes the authentic APIs in different processes; it is not a replacement judge protocol.
Input
Official demonstration: transmit({0,0,1,0,1,0},2), then receive({0,1,1,0},6,2).Output
The supplied naive encoder returns {0,0,1,0,1,0}; its naive decoder returns six zeroes. Four bits are correct, so raw score is 1/3.Solution analysis
- For one deletion, use a systematic Varshamov–Tenengolts checksum. Choose encoded length L so the non-power-of-two positions hold exactly N payload bits. Reserve positions 1,2,4,… for checks, and choose them so the weighted sum of all one positions is zero modulo L+1. The binary expansion of the required residue assigns these check bits directly. For N=10000, L=10014. Every possible single deletion can be corrected exactly, giving raw score 10000/10013, approximately 0.998702.
- After one deletion, let w be the number of received ones and δ the missing weighted checksum modulo L+1. Inserting a zero at position p adds the number of received ones at or after p. Inserting a one additionally adds p. Thus δ≤w identifies a deleted zero; δ>w identifies a deleted one. Scan positions until the checksum equation holds, insert the bit, and remove the check positions. For example, payload 001 occupies positions 3,5,6 of the six-bit codeword 100001. Deleting its last one leaves 10000; δ=6>w=1, so the decoder inserts one at position 6 and extracts 001.
- For D>1, use a deterministic synchronization skeleton. Insert C=ceil(2sqrt(ND)) known pseudorandom check bits at nearly equal intervals among the N unknown payload positions. Both functions regenerate the same pattern from n,d and a fixed 32-bit generator seed. This requires no shared process state. The redundancy rule is a design choice, rather than a proven optimal parameter. The transmitted length is at most 16325 for the official domain.
- The receiver considers all subsequence alignments. State (i,e) means that e of the first i transmitted positions were deleted, so the next received position is i−e. A deletion moves to (i+1,e+1); a surviving bit moves to (i+1,e). A known check must match, whereas a surviving unbiased payload bit has likelihood 1/2. Use forward and backward probabilities to sum the weight of every alignment, then reconstruct each payload bit by its posterior majority. Deleted payload bits contribute probability 1/2 to either value. Multiplying deletion transitions by q=D/M and survivor transitions by 1−q keeps the arithmetic stable; every complete alignment contains exactly D deletions, so this factor cancels between alignments. Normalize each row to prevent the products from underflowing.
- This posterior calculation is justified by an independent uniformly chosen set of D deletion positions and unbiased source bits. It minimizes expected bit errors for that model, up to floating-point rounding. The official burst model can differ, and no worst-case reconstruction fraction or maximum judge score is claimed for D>1. The local process-separated tests report empirical raw scores for both isolated deletions and bursts, without treating those measurements as guarantees.
Why it works
For D=1, deleting a bit changes the weighted checksum by suffixOnes+p·deletedBit. For a deleted zero this is in [0,w]; for a deleted one it is w+1+the number of preceding zeroes, in [w+1,L]. The two ranges are disjoint, and the scan finds an insertion yielding the original word; alternative insertion positions inside equal-bit runs produce the same word. Power-of-two check positions represent every residue 0…L, so the encoder always creates a valid checksum word. For D>1, every alignment corresponds to exactly one path in the acyclic (i,e) graph. Forward and backward recurrences sum its matching likelihood, and their product supplies the relative weight of paths through each transition. Summing these weights yields the posterior probability of each payload bit. Choosing the larger of its two posterior probabilities minimizes expected error for the stated inference model. Independently of that model, the encoder length bound and decoder output length hold for every valid official call.
Watch out. Deleted positions are not supplied to receive. The processes cannot share a stored copy of the data. Keep the two real function signatures and omit main(). Do not report probabilistic burst performance as exact recovery or maximum score. Never omit the erased-bit uncertainty when computing payload posteriors.
Commented C++17 solution
The visible listing contains both functions and two compile-time guards for inspection. The accompanying 1138-transmit.cpp and 1138-receive.cpp are the actual self-contained submission units: rename them transmit.cpp and receive.cpp, respectively, and compile with the supplied transmission.h/grader. Their guards select only the appropriate function, so they work in separate processes without shared state.
#include"transmission.h"
#include<algorithm>
#include<cmath>
#include<cstdint>
#include<vector>
using namespace std;
namespace{
vector<int>skeleton(int n,int d){
int checks=static_cast<int>(ceil(2.0*sqrt(static_cast<double>(n)*d)));
int length=n+checks;
vector<int>pattern(length,-1);
uint32_t state=0x6d2b79f5U;
for(int k=0;k<checks;++k){
state^=state<<13;
state^=state>>17;
state^=state<<5;
int position=static_cast<int>((2LL*k+1)*length/(2LL*checks));
pattern[position]=static_cast<int>(state&1U);
}
return pattern;
}
bool checkPosition(int position){
return (position&(position-1))==0;
}
} // namespace
#ifndef TRANSMISSION_RECEIVE_ONLY
vector<bool>transmit(const vector<bool>&data,int d){
int n=static_cast<int>(data.size());
if(d==1){
int length=n;
while(true){
int checks=0;
for(int position=1;position<=length;position*=2){
++checks;
}
if(length-checks>=n){
break;
}
++length;
}
vector<bool>result(length,false);
long long sum=0;
int index=0;
for(int position=1;position<=length;++position){
if(!checkPosition(position)&&index<n){
result[position-1]=data[index++];
if(result[position-1]){
sum+=position;
}
}
}
// Power-of-two check positions can represent every required syndrome.
int syndrome=static_cast<int>((length+1-sum%(length+1))%(length+1));
for(int position=1;position<=length;position*=2){
result[position-1]=(syndrome&position)!=0;
}
return result;
}
vector<int>pattern=skeleton(n,d);
vector<bool>result;
int index=0;
for(int bit:pattern){
result.push_back(bit==-1?data[index++]:bit!=0);
}
return result;
}
#endif
#ifndef TRANSMISSION_TRANSMIT_ONLY
vector<bool>receive(const vector<bool>&message,int n,int d){
if(d==1){
int length=static_cast<int>(message.size())+1;
int ones=0;
long long sum=0;
for(int i=0;i<length-1;++i){
if(message[i]){
++ones;
sum+=i+1;
}
}
int syndrome=static_cast<int>((length+1-sum%(length+1))%(length+1));
bool missing=syndrome>ones;
int suffix=ones;
int insertion=0;
for(int position=1;position<=length;++position){
if(suffix+(missing?position:0)==syndrome){
insertion=position-1;
break;
}
if(position<length&&message[position-1]){
--suffix;
}
}
vector<bool>full=message;
full.insert(full.begin()+insertion,missing);
vector<bool>result;
for(int position=1;position<=length&&static_cast<int>(result.size())<n;++position){
if(!checkPosition(position)){
result.push_back(full[position-1]);
}
}
return result;
}
vector<int>pattern=skeleton(n,d);
int length=static_cast<int>(pattern.size());
int received=static_cast<int>(message.size());
int width=d+1;
double deletionChance=static_cast<double>(d)/length;
// Row i describes how many of the first i transmitted positions were deleted.
vector<float>forward(static_cast<size_t>(length+1)*width,0.0F);
forward[0]=1.0F;
for(int i=0;i<length;++i){
float*current=&forward[static_cast<size_t>(i)*width];
float*next=current+width;
for(int deleted=0;deleted<=d;++deleted){
int j=i-deleted;
if(j<0||j>received){
continue;
}
double value=current[deleted];
if(deleted<d){
next[deleted+1]+=static_cast<float>(value*deletionChance);
}
if(j<received){
double likelihood=pattern[i]==-1?0.5:(pattern[i]==message[j]?1.0:0.0);
next[deleted]+=static_cast<float>(value*likelihood*(1.0-deletionChance));
}
}
double scale=0.0;
for(int deleted=0;deleted<=d;++deleted){
scale+=next[deleted];
}
if(scale>0.0){
for(int deleted=0;deleted<=d;++deleted){
next[deleted]=static_cast<float>(next[deleted]/scale);
}
}
}
vector<double>backward(width,0.0),previous(width,0.0);
backward[d]=1.0;
vector<bool>result(n,false);
int index=n;
for(int i=length-1;i>=0;--i){
fill(previous.begin(),previous.end(),0.0);
double total=0.0;
double trueWeight=0.0;
const float*row=&forward[static_cast<size_t>(i)*width];
for(int deleted=0;deleted<=d;++deleted){
int j=i-deleted;
if(j<0||j>received){
continue;
}
double erased=deleted<d?deletionChance*backward[deleted+1]:0.0;
double survives=0.0;
if(j<received){
double likelihood=pattern[i]==-1?0.5:(pattern[i]==message[j]?1.0:0.0);
survives=(1.0-deletionChance)*likelihood*backward[deleted];
}
previous[deleted]=erased+survives;
total+=row[deleted]*(erased+survives);
trueWeight+=row[deleted]*(0.5*erased+(j<received&&message[j]?survives:0.0));
}
if(pattern[i]==-1){
result[--index]=trueWeight>0.5*total;
}
double scale=0.0;
for(double value:previous){
scale+=value;
}
if(scale>0.0){
for(double&value:previous){
value/=scale;
}
}
backward.swap(previous);
}
return result;
}
#endif