IP over Avian Carriers: Redundancy Encoding and Decoding

In remote areas such as the deep woods of Finland, internet connections can be extremely unreliable. This is especially detrimental during online programming competitions. To improve connection reliability, on April 1, 1990 the Internet Engineering Task Force released a standard called IP over Avian Carriers, which describes how to use birds to transport internet traffic. Birds are immune to issues like cable cuts or power outages, making them a viable backup option; however, when several birds carry data, the packets may arrive out‐of-order or some may be lost.

Your task is to implement two functions to add redundancy to this avian transmission protocol: an encoder and a decoder.

Encoder

You need to implement the function vector<string> encode(int C, int K, int N, string X). The encoder receives a bit string X of length $C\cdot N$ (i.e. a string composed solely of characters 0 and 1, with $N>1$), and must produce a vector of K strings $S_0, S_1, \dots, S_{K-1}$, where each string is of length $N$ and consists only of 0 and 1.

Decoder

The decoder must implement the function string decode(int C, int K, int N, vector<string> Y, vector<int> I). It will be given the integers C, K, N along with a subset of C strings Y selected from the encoder's output. The vector I of length C contains the 0-indexed positions such that for every valid index i, Y[i] = S_[I[i]]. Your decoder must reconstruct and output the original bit string X of length $C\cdot N$.

Implementation Notes

• You are not allowed to use standard input or output (i.e. do not read from or write to the console).
• Before the decoder is run, the program is restarted, so any global state is cleared.
• You should submit one of the following files: avian.cpp, avian.java, avian.py or avian.cs.

Hint: It is acceptable to implement a simple systematic encoding as long as the decoder is able to recover the original string X from any subset of C strings of the encoder’s output. For the purpose of the provided test cases, you may assume that the indices in I are chosen so that they include exactly one copy of each original segment.

inputFormat

Encoder: The function encode receives four parameters:

• int C — the number of original segments.
• int K — the total number of transmitted strings.
• int N — the length of each string.
• string X — a bit string of length $C\cdot N$, containing only characters 0 and 1.

Decoder: The function decode receives the parameters int C, int K, int N, along with:

• vector<string> Y — a vector of C strings selected from the encoder's output.
• vector<int> I — a vector of indices (0-indexed) indicating which strings were selected, such that for every valid index i, Y[i] = S_[I[i]].

outputFormat

Encoder: Returns a vector of K strings, each of length N, consisting solely of 0 and 1.

Decoder: Returns the original bit string X of length $C\cdot N$.

sample

Encoder:
C = 2, K = 3, N = 3
X = "101110"

Decoder:
Y = ["101", "110"]
I = [0, 1]

101110