Editorial for Yet Another Contest 8 P5 - Hidden Tree


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

The main idea is to root the tree arbitrarily. For each node, we should encode both its parent and depth; for example, we could store the integer depth \times 100 + parent. When answering a query, we can simply output the parent of whichever node is deeper, since this node is guaranteed to be on the path. If both nodes are equally deep, either node can be used. As there up to 100 \times 100 = 10000 unique states, this is only sufficient for 25\% of the points. However, we can make the following optimizations:

Optimization 1a

Since queried nodes are not adjacent, their depths must either be equal or differ by at least 2. It suffices to store \lfloor \frac{depth}{2} \rfloor for each node, halving the number of unique states.

Optimization 1b

Set the parent of the root as 1. It actually suffices to store \lfloor \frac{\max(0, depth - 1)}{2} \rfloor for each node; this means that nodes at depth 0, 1, and 2 are mapped to the same value. This works because two nodes at these depths still have the property that the node with the larger stored integer is at least as deep as the other.

Optimization 2a

We can root the tree at the centre, to minimise the depth. In the worst case, the deepest node is at distance 50 away from the centre, so there are up to 51 unique depths that need to be represented. The reduces the number of unique states by 49\%.

Optimization 2b

In Optimization 2a, there will be 51 unique distances only in the case of a line graph. We can essentially root the tree at both central nodes. That is, instead of storing the depth of a node, we can store the minimum distance to either of the two central nodes. The parents for the central nodes do not matter.

For 75\% of the points, it is sufficient to combine either Optimizations 1a and 2b, or Optimizations 1b and 2a. Note that Optimization 1b doesn't actually improve on Optimization 1a unless Optimization 2a is also used.

Optimization 3

Observe that a descending chain of nodes can have the same depth value if their parent values are increasing. Although this doesn't immediately help, we can use randomness to remap parent values, which decreases the expected maximum depth value.

For full points, combine the ideas from all three optimisations. In the context of Optimization 3, Optimization 1 allows adjacent nodes with the same depth value to violate the monotonicity property. Optimization 2 instructs that we should try all nodes as the root, not necessarily just the centre. The cutoff for full at D = 20 is very generous, due to the nature of randomness leading to a range of possible values of D.


Comments

There are no comments at the moment.