In this problem, we are required to transmit a message of up to $$$1024$$$ bits using at most $$$66$$$ packets. Each packet contains $$$16$$$ good bits, resulting in a total of $$$1056$$$ bits. Since the length of the message is unknown, transmitting it requires $$$1025$$$ bits—an extra bit is needed to record the length. This leaves only $$$31$$$ available bits, which happens to match the value of $$$N$$$ (the length of a packet).
The intended solution uses exactly $$$N$$$ bits, which is sufficient to solve the problem. However, even if only $$$N−1$$$ bits are allowed, the problem still has a solution.
In the following discussion, assume that each sent packet is denoted as $$$A$$$, and the state of each bit is $$$C$$$, where $$$C=1$$$ means the bit remains unmodified, and $$$C=0$$$ means it is modified. Note that the definition of $$$C$$$ is opposite to that in the original problem.
It can be observed that if the states of $$$N−1$$$ out of $$$N$$$ bits are already determined, the state of the last bit can be directly deduced.
To determine the state of a bit, we record its state in an inquiry-like manner during packet transmission. Specifically, an inquiry $$$(u,v)$$$ means sending a packet where $$$A_u$$$ records $$$C_v$$$, while the remaining available bits transmit the original message.
If in an inquiry, $$$C_u=1$$$, then the value of $$$C_v$$$ can be determined. This is called a good inquiry. A good inquiry consumes one available bit and determines the state of one bit.
As long as each $$$C_u$$$ is covered by only one good inquiry, all bit states can be reconstructed using no more than $$$N−1$$$ bits.
Examining the problem statement, we notice that the send_packet function has a return value. This means that after sending packet A, we have access to the result received by B and adjust the strategy accordingly. As long as B adjusts its strategy in the same way, both parties can arrive at the same result.
This allows us to perform bad inquiries: if in an inquiry, $$$C_u=0$$$, the value of $$$C_v$$$ cannot be determined, but the result of this inquiry can still be used to adjust the strategy without consuming any bits.
Consider the following strategy:
First, create an empty stack $$$S$$$.
Iterate over $$$i = 0\cdots N−2$$$:
If $$$S$$$ is empty, push $$$i$$$ onto the stack.
Otherwise, take the top element $$$x$$$ and perform the inquiry $$$(x, i)$$$:
If the inquiry result is $$$0$$$, pair $$$(x, i)$$$ and pop $$$x$$$. In this case, at least one of $$$C_x$$$ or $$$C_i$$$ must be $$$0$$$.
Otherwise, push $$$i$$$ onto the stack.
This ensures that in every pair, the number of 0s is no less than the number of 1s, while the initial $$$N−1$$$ bits contain at least as many 1s as 0s. Thus, the remaining stack must have at least as many 1s as 0s.
If the stack is empty, then exactly $$$\frac{N−1}{2}$$$ 1s and $$$\frac{N−1}{2}$$$ 0s are paired, meaning the remaining bit must be $$$1$$$.
Otherwise, the stack must contain at least one $$$1$$$.
The stack cannot contain two consecutive elements $$$x, y$$$ where $$$C_x=1$$$ and $$$C_y=0$$$. Otherwise, when $$$y$$$ was pushed, the inquiry $$$(x, y)$$$ would have returned $$$0$$$, so that they would not remain in the stack.
Therefore, the top element of the stack must be $$$1$$$.
Thus, we have successfully identified a position where $$$C=1$$$. Using this, we can determine the state of any other bit with a single inquiry.
For each inquiry $$$(u, v)$$$ (note that $$$u \lt v$$$ must hold), draw a directed edge from $$$u$$$ to $$$v$$$.
Repeat the following steps until all $$$C_i$$$ are determined:
Find the smallest undetermined $$$x$$$ and use one inquiry to determine it.
For each determined position $$$u$$$:
If $$$C_u=1$$$, use previous inquiries to determine all positions $$$v$$$ that $$$u$$$ points to.
Remove $$$u$$$ and all its outgoing edges.
If $$$C_0\cdots C_{N−2}$$$ are all determined, deduce $$$C_{N−1}$$$.
It can be proven that each bit is determined by only one good inquiry.
In conclusion, we have solved the original problem using only $$$N−1$$$ bits, which means we can transmit messages of up to $$$1025$$$ bits in length.
sample code ($$$N - 1$$$ bits) implemented by lmh_qwq
sample code ($$$N$$$ bits) implemented by wsc2008qwq
