Editorial for Yet Another Contest 3 P4 - Rumour
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
As , we should aim for a solution with approximately
queries.
Subtask 1
At any time, the possible values of form a potential range. When we query a suspect
, we can determine whether
is equal to
, greater than
, or less than
. Hence, we can simply binary search for the value of
, using approximately
queries.
Subtask 2
At any time, the possible values of form a (non-rooted) subtree. Consider querying suspect
such that
is part of the subtree, and rooting the tree of
. Then, our query tells us which (rooted) subtree of the children of
contains
.
Thus, we can root the tree at node . After each query, we simply descend to the left or right subtree of the current node, depending on which subtree the return value of the query lies in.
Subtask 3
We can optimise our subtask solution to work on a general graph. Given a (non-rooted) tree that
could lie in, we need to determine the optimal
to query. Recall that after querying
, if we have not yet found
, then our new tree could be any of the subtrees formed when removing
.
As we are looking for a solution with approximately queries, we should choose a value of
such that the maximum size of any subtree formed when removing
is at most half the size of the current tree. This would allow us to reduce the size of the possible set of values of
by half in each query. To do so, we should choose
to be the centroid of the current tree.
Comments