Editorial for Yet Another Contest 3 P4 - Rumour

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

As $2^{17} \approx 100\,000$ ~2^{17} \approx 100\,000~, we should aim for a solution with approximately $\log_2 N$ ~\log_2 N~ queries.

Subtask 1

At any time, the possible values of $X$ ~X~ form a potential range. When we query a suspect $Y$ ~Y~, we can determine whether $X$ ~X~ is equal to $Y$ ~Y~, greater than $Y$ ~Y~, or less than $Y$ ~Y~. Hence, we can simply binary search for the value of $X$ ~X~, using approximately $\log_2 N$ ~\log_2 N~ queries.

Subtask 2

At any time, the possible values of $X$ ~X~ form a (non-rooted) subtree. Consider querying suspect $Y$ ~Y~ such that $Y$ ~Y~ is part of the subtree, and rooting the tree of $Y$ ~Y~. Then, our query tells us which (rooted) subtree of the children of $Y$ ~Y~ contains $X$ ~X~.

Thus, we can root the tree at node $1$ ~1~. 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 $2$ ~2~ solution to work on a general graph. Given a (non-rooted) tree that $X$ ~X~ could lie in, we need to determine the optimal $Y$ ~Y~ to query. Recall that after querying $Y$ ~Y~, if we have not yet found $X$ ~X~, then our new tree could be any of the subtrees formed when removing $Y$ ~Y~.

As we are looking for a solution with approximately $\log_2 N$ ~\log_2 N~ queries, we should choose a value of $Y$ ~Y~ such that the maximum size of any subtree formed when removing $Y$ ~Y~ 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 $X$ ~X~ by half in each query. To do so, we should choose $Y$ ~Y~ to be the centroid of the current tree.

Comments

There are no comments at the moment.