Authors: Daniel Posdărăscu
Lucian Bicsi
Solved by:
First to solve: N/A
We'll start by handling the easy case of one treasure (the condition for this case is when there is some for which dist_i = 0, where dist_i is the distance shown by the detector on the -th island.
Let's consider an arbitrary subset of treasures . How would the distance array look in this particular case? Well, it turns out that only two treasures matter in this case: the most distant two in . This can be seen by analyzing the case with treasures: suppose there are treasures, and the subtree induced by them is formed of chains which meet in some middle island. Let's suppose the length of the "legs" are a \leq b \leq c. Then, the treasure at distance from the middle island will never be the farthest treasure for any of the islands.
Therefore, one may see that the distances array looks as if only two treasures are present. More specifically, by analyzing the islands for which d_i is minimum (let's call such islands centers), there are two cases:
There is one center island;
There are two neighbouring center islands.
In both cases, we can notice that, in order for the distance array to be valid, two conditions have to be fulfilled (considering d = \min (dist)):
All treasure islands are at distance at most from the central island(s);
There are at least two treasures at distance from the central island(s) in different subtrees.
Now that we know the constraints that the distance array imposes on the structure of the treasure islands, the rest is some counting/probability. Naturally, vertices with higher probability correspond to vertices which appear in many configurations. Indeed, Bayes' rule states that:
Here means "is proportional to". Note that the latter term in the right hand side is always , so it can be ignored.
However, for an island at depth greater than the probability is always zero, and for islands at depth less than , it is equal to , and is always (strictly) smaller than the probability for any island at depth (every valid subset containing the treasure at depth smaller than can be transformed into one having the treasure at depth , but not vice-versa). The only thing that remains to calculate is how two different treasures at depth compare to each other.
However, the number of configurations having some treasure at depth can be calculated as 2^{M-1} - 2^{I+S}, where is the number of islands at depth at most , is the number of islands at depth less than , and is the number of islands at depth in the same center's subtree as the treasure in question. But and are the same for all islands, so comparing two such islands reduces to comparing (in other words, an island has a greater probability than an island if and only if the number of vertices at depth in the same subtree as is smaller than in ).
Now, the solution is simple. First, assign as being:
The number of treasures at depth under the same center's subtree as , if is at depth ;
, if is at depth smaller than ;
n+1, if is at depth greater than .
Then, just sort the islands by the pair (\text{label}(v), v). Complexity is O(n \log n).