PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ray Bai
Developer: Roman Bilyi
Editorialist: Anton Trygub
DIFFICULTY:
3145
There are many different approaches that achieve various bounds. We will describe the solutions which work for n = 500 in 10 queries, and in 9 queries.
10 queries: Suppose that r is the root. First, let’s ask a query about all leaves. Their LCA has to be r (if r is a leaf, it’s clear; otherwise, there is a leaf in each of the subtrees of r). So, we can determine if r is a leaf with this query.
Now if r is not a leaf, let’s ask queries for sets, which contain all leaves. We will get YES
iff we have included r into the set. So, we can do binary search on the non-leaf nodes, discarding roughly half at each time. This way, we will need at most 9 queries.
Suppose now that r is a leaf. If we ask a question about some subset of the leaves of size \ge 2, the answer will be YES
if and only if r is in the chosen set. So, we can once again do binary search on the leaves, until we get at most 2 candidates r_1, r_2. At that point, we can ask a query for nodes r_2, r_3, where r_3 is any other leaf, to determine if r_2 is the root. This way, we will also need at most 9 queries.
Adding the initial query about all leaves, we are done in 10 queries.
9 queries: Our algorithm loses one query at the first step: it might be the case that the number of remaining candidates is n - some small number (when the root is a leaf, and almost all nodes are leaves, for example). Let’s try to solve this issue.
Let’s arrange our nodes in the following fashion: first all leaves, then all non-leaves. What happens if we ask a query about the some prefix of this order of length at least 2? Let’s consider two cases.
-
Our prefix contains all the leaves, and, maybe, some other nodes. Then their LCA is r, and we will get
YES
if and only if r is in that prefix. -
Our prefix is some subset of the leaves. Then, if r is among them, we will get
YES
, otherwise their LCA would be some node different from any of them, so we will getNO
. Once again, we will getYES
if and only if r is in that prefix.
So, we can do binary search on this order of nodes! The only exception is when we end up with a prefix of length 2. Then, as in previous subtask, we should ask one of these leaves with one of other leaves.
This solves the problem in 9 queries.