Hi everyone!

I recently solved the IOI 2024 Message and realized that my solution went in a completely different direction than the intended solution, so I decided to write this blog. This is my first blog on Codeforces, so please forgive any imperfections.

Basically, my solution is an improvement from $$$Q=70$$$ partial solution, which finds a safe bit using 4 packets. For convenience, I will denote Cleopatra as "C", Aisha as "A", Basma as "B". Also note that we need to send $$$1025$$$-bit information.

Recall: $$$Q=70$$$ solution

Here we use 4 packets to tell B one of the safe bits. Indeed, define $$$S_i$$$ be a set of some indices, where $$$0\le i\le 4$$$. Let $$$S_0={ 0,1,2,...,30 }$$$. Then, it is clear that $$$S_0$$$ contains exactly $$$16$$$ safe bits. Now, for each $$$1\le i\le 4$$$ A marks exactly half of safe bits to $$$0$$$, and other half to $$$1$$$ in $$$S_{i-1}$$$, and send it to B(For safe bits which are not in $$$S_{i-1}$$$, color it anyway.). Then looking the sent packet, there would be a color which appears less than the other one, in $$$S_{i-1}$$$. Put them in $$$S_i$$$.

Now, we know that using this procedure, the size of $$$S_i$$$ decreases at least half, and $$$S_4$$$ has exactly one safe bit, and B can trace this procedure too. Now B knows one safe bit, so A can send the information about whether other bits are safe or not, using 30 bits. Since we can send the information about message using other safe bits while the only safe bit B knows is trying to send information about other bits, you can send $$$30\times 15+36\times 16=1026$$$, which is enough to send everything.

Here, there are a plenty of defects, which can be optimized.

Optimization 1

First, for the first 4 packets, the indices that are not in $$$S_i$$$ can be used. We will anyway know the exact indices of safe bit in future, so we can just use indices that are not in $$$S_i$$$ to send the message.

Since $$$S_i$$$s size would decrease at least half in each step, using this optimization would allows us additional $$$2^{8+12+14}=2^{34}$$$ bits for sending message. Just using this optimization, it's sufficient to use only 68 packets, since $$$34+30\times 15+34\times 16=1028$$$.

Optimization 2

In addition, for the first 4 packets, for each $$$S_{i-1}$$$, we can select what to color as 0, or 1. After knowing all safe indices, the choice of A for this, can be sort of information for B. Thus, A can send additional information, by selecting half of safe indices from $$$S_{i-1}$$$, which has $$$\binom{16}{8}\times \binom{8}{4}\times \binom{4}{2}\times \binom{2}{1}$$$ possibilities.

Using this optimization, A can send $$$\log _2(\binom{16}{8}\times \binom{8}{4}\times \binom{4}{2}\times \binom{2}{1})\approx 23.xx\to 23$$$ bits to B.

So here, only 67 packets are sufficient, since $$$23+37+30\times 15+33\times 16=1035$$$.

Optimization 3

This would be the most straightforward optimization, I think.

A sent $$$30$$$ bits to B for indicating which indices are safe, but you might noticed that it is supersaturated. Actually, there are only $$$15$$$ safe bits among $$$30$$$ bits, so there would be total $$$\binom{30}{15}$$$ possibilities, which is smaller than $$$2^{28}$$$.

Unfortunately, this is not sufficient to reduce the required number of packets. The final Optimization is similar to this, which slightly reduces the required bits for sending the information about safe bits.

Optimization 4

For each steps for first 4 packets, we know that for $$$1\le i\le 4$$$, there are exactly $$$2^{4-i}$$$ safe indices in $$$S_{i-1}-S_i$$$, which means exactly half of safe indices are discarded, and they would be in $$$S_{i-1}-S_i$$$.

Recall that B can calculate $$$S_i$$$ in same way as A. If we let $$$T_i=S_{i-1}-S_i$$$, then B only requires information of amount $$$\binom{|T_1|}{8}\times \binom{|T_2|}{4}\times \binom{|T_3|}{2}\times \binom{|T_4|}{1}$$$. Then, it is natural to come up with following question:

What is the maximum value of $$$\binom{x}{8}\times \binom{y}{4}\times \binom{z}{2}\times \binom{w}{1}$$$ for $$$x+y+z+w=30$$$?

Well, here you can just implement a code that calculates the maximum value of this, but there is more intuitive way to prove that it is maximum at $$$x=16,y=8,z=4,w=2$$$.

Anyway, and surprisingly, we only need 66 packets using this optimization! Indeed, recall that $$$\log(\binom{16}{8}\times \binom{8}{4}\times \binom{4}{2}\times \binom{2}{1})\approx 23.xx\to 24$$$. So A can send 24 bits to B in order to give the information about safe bits.

Now, lets compute the efficiency. Using 66 packets, A can send total of $$$57+24\times 15+38\times 16=1025$$$ bits, which is exactly same as the amount of information we want to send.

For implementation, refer this(although my coding style is not so good, and there would be some messy things...): https://qoj.ac/submission/1041847.

In conclusion, if we carefully observe the defects and refinements for this intuitive solution, it is possible to receive $$$100$$$ points in this problem. Since the intended solution is very non-intuitive(at least for me), I believe that this could be some intuitive solution(which requires a bit messy observations, and implementations...) for this problem.