I came up with this solution to the problem and noticed the best solution at the competition was with M <= 12, so I decided to post about it. This solution is quite complicated (I also have a simpler scheme with 12), so it is understandable that no one had time for it (and I imagine M <= 8 is even harder and/or cleverer).
Here is a link to the problem: https://drive.google.com/file/d/1jMpszX2nPZ79jrK8yzDFIZXNb0CG_efi/view
First notice that we can keep a state of which two nodes are opposite ends of some diameter. Then on a given node, either both ends stay the same or one end moves to the new node and the other end remains.
We will solve the problem by splitting the $$$N$$$ nodes into some number of chunks. Each chunk will have a size $$$K_i$$$ and will allow up to $$$M_i$$$ messages. We want $$$\sum_i K_i = N$$$ and to minimize $$$M_i$$$.
The core idea is that each chunk will encode the updates to the state (which 2 nodes are ends of diameters) up to the end of the previous chunk (say of size $$$K$$$). Updates can be of the form: 1. No update: 1 option. 2. Overwrite one end: $$$2 K$$$ options (we partition basedon whether we overwrite smaller or larger (by index) end). 3. Overwrite both ends: $$$K (K - 1) / 2$$$ options.
Therefore the total number of updates for a "generic" chunk is $$$F(K) = 1 + 2K + K(K-1)/2$$$. We actually need only case 3 for the first chunk, since both ends must be in it (though this turns out not to be needed for my solution, since the linear term is quite small for the first chunk, which is very large).
A given "generic" chunk can encode $$$E(K, M) = $$$\sum_{0 <= j <= M_i} (K_i choose M_i) * 4^j$ options about the previous chunk. Therefore, we just want to maintain $$$E(K_{i + 1}, M_{i + 1}) \gt = F(K_i)$$$ for all $$$i$$$.
However, we still have to deal with one issue -- no one encodes for the final chunk, so it has to encode for itself as well as the penultimate chunk, i.e. it needs a custom scheme.
We have such a custom scheme for K=3, M=3, which will encode for itself and a previous chunk of size 4. There is one helpful observation: if both ends lie in the last two chunks, we can skip encoding (part of) the state after the penultimate chunk.
Therefore, we just have the chunks (K_i, M_i) in reverse order like so: 1. (3, 3): described a chustom scheme for itself and the previous chunk. 2. (4, 3): E(4, 3) = 369 >= F(5) = 351. 3. (25, 5): E(25, 5) = 57795621 >= F(9968) = 49695465. 4. (9968, 0): we are done.
Finally, let us describe the custom scheme for the final chunk. Let the 3 final nodes be A, B, C. and the previous 4 be X, Y, Z, W.
- At A: i. If A is an end: a. If 0 of X, Y, Z, W are still ends: send 0. b. If 1 of X, Y, Z, W is still an end: send 1. ii. If A is not an end: a. If 0 of X, Y, Z, W are ends: send 2. b. If 1 of X, Y, Z, W is an end: send 3. c. If 2 of X, Y, Z, W are ends: send 4.
- At B: i. A sent 0: a. B is an end: I. Together with A: send 0. II. Overwrites A which overwrote the smaller end: send 1. III. Overwrites A which overwrote the larger end: send 2. b. B is not an end: I. A overwrote the smaller end: send 3. II. A overwrote the larger end: send 4. We know the full state in this case. ii. A sent 1: a. B is an end together with A: send 0. We know the full state in this case. b. B is not an end or B overwrites A: send 1-4 to encode which of X, Y, Z, W is an end. iii. A sent 2: a. B is not an end: send 0. b. B overwrites the smaller end: send 1. c. B overwrites the larger end: send 2. We know the full state in this case. iv. A sent 3: a. B overwrites the X, Y, Z, W end: send 0. b. B is not an end or B is an end together with the X, Y, Z, W end: send 1-4 to encode which of X, Y, Z, W is an end. v. A sent 4: a. B is an end: I. With X or Y: send 0. II. With Z or W: send 1. b. B is not an end: I. The ends are X-Y or X-W: send 2. II. The ends are Y-Z or Y-W: send 3. III. The ends are X-Z or Z-W: send 4.
- At C: i. If we know the full state: a. C is not an end: send 0. b. C overwrites the smaller end: send 1. c. C overwrites the larger end: send 2. ii. A sent 1 and B sent 1-4: a. C is an end with the X, Y, Z, W end: send 0. b. B is an end with the X, Y, Z, W end: send 1. c. A is an end with the X, Y, Z, W end: send 2. d. C is an end with B: send 2. e. C is an end with A: send 3. iii. A sent 3 and B sent 0: a. C is an end: I. C is an end B: send 0. II. C overwrites B which overwrote the smaller end: send 1. III. C overwrites B which overwrote the larger end: send 2. b. C is not an end: I. B overwrote the smaller end: send 3. II. B overwrote the smaller end: send 4. iii. A sent 3 and B sent 1-4: a. C is an end with the X, Y, Z, W end: send 0. b. B is an end with the X, Y, Z, W end: send 1. c. C is an end with B: send 2. d. C and B are not ends: I. The X, Y, Z, W end overwrote the smaller end: send 3. II. The X, Y, Z, W end overwrote the smaller end: send 4. iv. A sent 4 and B sent 0-1: a. C is an end with B: send 0. b. C is not an end: I. The other end is X or Z: send 1. II. The other end is Y or W: send 2. c. C is an end and B is not: I. The other end is X or Z: send 3. II. The other end is Y or W: send 4. iv. A sent 4 and B sent 2-4: a. C is not an end: Each case for what B sent has 2 options for the ends -- encode which by sending 0 or 1. b. C is an end: Each case for what B sent has 3 possible nodes as ends -- encode which of those is an end with C by sending 2, 3 or 4.
