Guessing game

This is my solution to the problem Guessing Game in EGOI 2023, with $K=5$.

In my solution, Anna gives information to Bertil in phases, where the first $n_1$ houses she is led to constitute the first phase, the next $n_2$ houses constitute the second phase, and so on. In each phase, Anna should give all the information that Bertil needs in order to determine exactly which houses she visited in the previous phase. This is important because when Bertil knows which houses were in the previous phase, he can discard them as they are no longer relevant. Finally, when Anna only has a small number of houses left to visit, I used a precomputed bruteforced strategy which allowed Anna to tell Bertil both which houses were part of the previous phase and which two houses Bertil should use as guesses.

In the first phase, Anna just writes $1$ on all the doors she visits. This gives Bertil a great deal of information about which doors were in the first phase, but he can't know for sure if a door with a $1$ on it was part of the first phase or if it was part of a later phase and just happened to get a $1$ anyway. But I designed the strategy so that the vast majority of all 1s would be in the first phase (for example by avoiding writing any 1s in the second phase), which means that only a relatively small amount of information is needed to identify which 1s belonged to the first phase. To send this information to Bertil, Anna uses an error-correcting code and writes numbers in the second phase in accordance with that code. The reason why the code has to be error-correcting is that Anna can't control which houses are in the second phase and which ones are in the third or later phase (these are the errors).

Designing the code is the hardest part of this solution. My solution was to encode whether each house was part of the first phase as either $0$ or $1$, and then hash each prefix of the resulting binary vector, and reduce the hash modulo $K$. Then Bertil could use Viterbi decoding to reconstruct the vector in a streaming manner.

There have been some discussions regarding the solution over at https://codeforces.com/blog/entry/118430