Problem analysis: Hidden tree (stage III, XXXIII OI)

In this task, we will encode vertex numbers. For this reason, it will be convenient to assume that the vertex numbers in a tree with \(n\) vertices range from 0 to \(n-1\).

First and second subtasks

In the first subtask, where every tree is a star, we only need to encode the center of the star. In this case, we can include as many ones in the vertex code as its number.

However, to obtain more points, we need a better way to encode vertex numbers.

Third and fourth subtasks

We can represent the code in binary; for numbers smaller than 1000, 10 bits are sufficient. Thus, for each vertex (of large degree), we assign to its consecutive edges the bits corresponding to its binary representation. Since there may be more edges than needed bits, we fill the remaining ones with zeros. For easier implementation, it is convenient to use least significant bit first order.

This approach could fail if two vertices sharing an edge tried to assign different bits. In these subtasks, this was not an issue because vertices of large degree were not adjacent to each other.

A shared edge

If two vertices share an edge, then setting a bit for one of them affects the code of the other. Thus, we have a situation where some bits are forced and cannot be set arbitrarily.

The key observation, however, is that we are working on a tree. If we assign codes to vertices in a suitable order (for example, BFS or DFS), then when processing a vertex, at most one bit is predetermined.

Code with a forced bit

Let us focus on the case where the forced bit contradicts the expected code. In that case, we would need to indicate which bit is negated, which cannot be done using only one additional bit. Therefore, in such a situation, we negate all remaining bits of the code. This way, it suffices to add information about whether the code is normal or negated, which requires only one additional bit.

We therefore define the code format as follows:

  • the first bit indicates whether the code is normal (0) or negated (1),
  • the subsequent bits store the vertex number (either normal or negated).

Thanks to this, regardless of the position of the forced bit, we can always choose one of the two versions (normal or negated) so that the constraints are satisfied.

Thus, if the forced bit is the first one, we keep the code normal or negate it according to the value of the first bit. If the forced bit is at one of the remaining positions, we match the rest of the code to it and set the first bit accordingly.

This solves the task completely and correctly generates codes for all vertices of degree at least 11.

Example

For example, suppose the vertex to be encoded has number 512, which in binary is 1000000000 (one followed by 9 zeros). Since we need to encode this vertex, it has degree at least 11, so we have at least 11 bits available from its edges. One of these bits may be forced by the edge to the parent of the vertex in the considered rooted tree. The vertex can be encoded as 01000000000 (normal) or 10111111111 (negated). These codes have no bits in common, so regardless of which bit is forced and how, it is always possible to choose a matching code for the vertex. The remaining bits of the code are ignored, regardless of whether they are forced to zero or one.

Weaker codes with a forced bit

  • \(L=30\) – each code bit is stored in three copies, and we choose the value that appears most often.
  • \(L=20\) – each code bit is stored using two bits whose XOR gives the correct value.
  • \(L=14-17\) – we provide: the code (10 bits), the position at which the bit is negated (4 bits), and information on whether the bit is negated within the code–in the first 10 bits–or elsewhere (0–3 bits).
  • \(L=12-13\) – the bit indicating whether the code is negated is encoded using 2 or 3 bits to make it robust against being forced. The model solution avoids this by adapting to the first bit.