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.