INTREECTIVE - Editorial

editorial
, , , , ,
1

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.

2

I tried this one using diameter approach. find the diameter of current tree and divide it in two trees from center and discard one half on the basis of query. this solution didn’t passed 2-3 test cases.
can anybody tell where am i going wrong ??

4

Consider the set of edges with N = 6:

1 2
2 3
1 4
4 5
1 6

Take marked node = node 6. Then ig, your approach will fail.

1 Like
5

nope its working fine in this case, but i got it where i am going wrong , this solution will take more than 21 queries in some cases
example:-
1
30
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
5 15
15 16
16 17
17 18
5 11
11 12
12 13
13 14
4 21
21 20
20 19
4 22
22 23
23 24
3 27
27 28
3 25
25 26
2 29
2 30

in this kind of structure it will fail

6

Can someone please help me what is wrong with my code… it gives no verdict :frowning:

Code link: CodeChef: Practical coding for everyone

7

When will you add detailed explanation?

9

https://www.codechef.com/viewsolution/59566329

this is a working solution based on approach 1 in editorial. It it helps

10

Can you check what is wrong with my solution?
I implemented the same thing as yours
Solution

11

Hey man can you explain your solution a bit ? I find it interesting

12

Sure!
So first I took the input and populated the adjacency list. After that in one dfs call, I populated par and leaf arrays.
now, I use two binary searches, one for finding out the leaf node such that the marked node lies in the path from root to that leaf node. For that I just keep asking queries from the leaf array until only one element is remaining.

Now, we have a leaf node and we know marked node lies in the path from this leaf node to root node. So we determine all elements in the path from that leaf to root using par array, and again apply binary search on that path until only one element is remaining. This element is the marked node.

Think about the binary search how it works, you’ll get it.

13

[Request For Help With Solution]

Hi,

I tried up-solving this question using the same thought process, as discussed in Editorial.
I am getting AC on 50% Test Cases on Submission.
I tried on many sample test cases in my local, it works fine for all.
Can anybody please help me figure out where am I going wrong/missing out on any edge case?

Here is my Solution Link (With Full Comments/documentation) : My Solution Link

Thanks a lot, in advance!!

14

It was a Judge Error. Verdict isn’t shown in the IDE (not then and there) but we can check it in “My submission”. I see you have already ACed it.

1 Like
15

Yeah I came to know I was going a little wrong in my earlier approach. :smile:

16

Hi, why we can’t find marked node in one complete binary search in 10 queries without making the tree

17

Hey @lokeshjangra :wave:
We cannot able to do that because in the first binary search we are only able to find that the marked node is present in path from 1 to the leaf node and to find the exact location we have to do the 2nd binary search.

18

Hi sir, my confusion is that we are asked to find value of marked node which is from 1 to n . This can be done with the help of one complete binary search from 1 to n.
Please tell me if I have understood the question wrong way.

19

In case of tree (1->3,1->4,1->5,3->2) and we mark the node 3 so according to binary search on query (1,2,3) judge will return 1 and on (1,2) also return 1 and will terminate returning answer 2 but it is wrong.

20

Yes ! Thank You very much Sir