# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Satyam

Tester: Abhinav Sharma, Manan Grover

Editorialist: Lavish Gupta

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

You should be familiar with the concepts of Binary Search and Graph Traversal algorithms like Breadth First Search and Depth First Search

# PROBLEM:

*This problem is similar to the problem “INTREECTIVE2”. The only difference between them is the number of queries allowed — in this problem, up to 21 queries can be made. In Div. 1 and Div. 2 this problem is worth 40 points and “INTREECTIVE2” is worth 60. In Div. 3 this problem is non-scorable.*

**This is an interactive task**

You are given a tree consisting of N nodes, numbered from 1 to N. Chef selected an arbitrary node and marked it.

Chef gave you a judge to play with, using which you can ask queries about the given tree.

In each query, you give the judge a non-empty set S of nodes. The judge returns 1 if there exists u and v (**not** necessarily distinct) such that u,v \in S and the marked node lies on the shortest path from u to v, or 0 otherwise.

You have to find the marked node.

For each test case, you can use at most **21 queries**.

# QUICK EXPLANATION

Because we have 1000 nodes, we can do one complete Binary Search on the nodes in 10 queries. We have 21 queries, so we can do 2 Binary Searches.

Also, let us consider Node 1 as the root node.

**Solution 1**

- Let us consider the set of leaf nodes \{L_1, L_2 \ldots L_K \}. With the first Binary Search, we can find the leaf node L_i such that the node in the shortest path from 1 to L_i.
- After finding this lead node, we can do one more Binary Search on the nodes that lie in the shortest path from 1 to L_i.

**Solution 2**

- Let’s find the height of all the nodes using BFS. Now, first we can do a Binary Search on the height of the Node - say H.
- Once we know the height of the marked node, we can do the Binary Search on the nodes which have their height as H to find out the marked node.

# EXPLANATION:

*Detailed explanation will be added soon*

# TIME COMPLEXITY:

O(N) for each test case.