Problem G
Love Letter

Mio and Sara come from two very different families. In Mio’s family, everyone wears hats shaped like rectangles, while in Sara’s family, everyone wears triangular-shaped hats. This difference in taste has led to feuds that have lasted for generations. Despite this, Mio and Sara happened to meet one day and fell in love at first sight.

Since it is difficult for them to meet, they instead send messages to each other to communicate. Because they are very secretive, we do not know exactly how the devices they use to communicate work. However, we do know a few things: when Sara wants to send a message, she types it in as a sequence of ones and zeros into her device, and then it sends the message. Unfortunately, bad weather can cause problems. When the machine sends ones and zeros during bad weather, it sends the exact opposite. For example, if the weather is bad and the machine tries to send a 0, it will send a 1 instead.

Sara has observed that every time she sends a message, there is bad weather exactly once during a contiguous period of time. This means that if she tries to send a particular message, the message that the recipient receives will be incorrect in such a way that, in a specific interval (which can be of size 1 or more, but not zero), all zeros become ones and all ones become zeros. We call this the interval being corrupted.

For example: if Sara sends 11101001, it is possible that the weather causes the following corruption: 11101001 $\Rightarrow $ 11010111.

Let the message Sara wants to send be denoted by $S$ and the message Mio receives be denoted by $M$. Thus, $S$ is never equal to $M$ due to the bad weather. Sara and Mio now want to develop a system to communicate with each other despite the bad weather. It can be shown that if Sara sends exactly $S$, it will be impossible for Mio to use $M$ to find $S$. But maybe it will work if Sara sends a message that is slightly longer than $S$?

Your task is to develop the system for Sara and Mio so that they can communicate flawlessly. You do this by implementing two functions, encode and decode. The function encode will be called with $S$, and it should then return $E$. Sara will then send $E$ through her machine.

Afterward, Mio receives the string $M$ and calls the function decode with $M$, and its job is to use $M$ to find $S$.

To score points on this task, the system must work. Therefore, decode must always be able to find $S$, regardless of how bad weather corrupts $E$. You will get more points if $E$ is short.

Implementation

Your solution to the problem must be written in one of the following languages: C++, Java, Python, or Rust. Below is a description of what the implementation looks like in C++. In most other languages, it works similarly. You can download a reference implementation for your language in the attachments at the bottom of the page.

You must not create a main function. Instead, you should implement the following functions:

• string encode(string S)
  

  • The parameter $S$ is the message Sara wants to send to Mio. $S$ consists only of the characters 0 and 1. In all test cases, $S$ consists of exactly 100 characters.

  • The return value should be $E$, the message Sara sends through the machine. $E$ must contain at least one characters and may only consist of the characters 0 and 1.

• After sending $E$, an interval will be corrupted during transmission.

• string decode(string M)
  

  • The parameter $M$ is the message Mio receives. This will be $E$ after an interval has been corrupted. Therefore, $M$ consists only of the characters 0 and 1.

  • The return value should be $S$, the message that encode was originally called with. If the return value is the same as $S$, you get the correct answer for the test case.

encode and decode can only communicate through the parameters they are called with, $S$ and $M$. Therefore, your program will be restarted between calls to each function. encode and decode must be fast enough to be called 50 times each within the time limit. The judge is also non-adaptive. This means that how it selects $S$ does not depend on what you choose to send as $E$. When choosing which interval to corrupt, it will only look at the number of characters in $E$, not the contents of $E$.

Reference Implementations

All reference implementations in the attachments implement the following protocol: encode sends each letter in $S$ 5 times in a row. decode then takes each group of 5 characters and says that the value of the letter in $S$ is the one in the middle of the group. This protocol does not work, but it shows what the implementation of a protocol might look like.

It is important that your solution does not read or write from standard input/output. If your solution does this, you will likely get a strange error message. For some languages, the filename is important, so do not change it. Also, do not change the names of functions and classes if they exist. Rust requires extra steps to work, which you can read about in the file rust/readme.txt in karleksbrev.zip.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Let $E_{max}$ denote the length of the $E$ with the most characters that encode produces in a particular test case group. To score points for a test case, $E_{max}$ must be small enough.

It is also given that $S$ always consists of exactly 100 characters.

Input Format for the Example Judge

The example judge reads input in the following format:

• A line with the integers $N$ and $K$.

• A line with the bit string $S$.

• A line with the integers $l$ and $r$. This is the interval in $E$ that the judge will corrupt.

Example Interaction

Consider the following input to the judge:

5 25
01011
1 3

When the example program is run, the following happens. Note that the example program does not solve the problem in this case.