LCAINTERACT - Editorial

editorial
, , , ,
1

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 getYES, otherwise their LCA would be some node different from any of them, so we will get NO. Once again, we will get YES 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.