SECRETREE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Tree

PROBLEM:

You are given an integer N. There exists a hidden tree with N nodes. Determine the edges of this tree by asking atmost N^2 queries of the following format - “Is the sequence of nodes a_1, a_2,\dots,a_k a subsequence of any simple path of this tree?”

EXPLANATION:

Hint 1

Can you devise a method to find one direct edge in the hidden tree?

Solution

Select any two nodes of the tree, say a and b. For each valid x\ (x\ne a,b), query if the node x lies on the simple path from a\to b, and set a := x if true.

It can be easily shown that, at the end of the above operations, a direct edge between (the final value of) a and b exists.

Hint 2

Say we deduced nodes a and b have an edge between them. Visualize deleting it from the hidden tree. You’re then left with two disjoint subtrees (containing the nodes a and b respectively).

Now, if only we determine the set of nodes comprising each subtree, we could recursively apply the above method to determine the edges in each subtree.
How would you accomplish this?

Solution

For each valid node x\ (x\ne a,b) in the tree, node x lies in the subtree containing node a if (and only if) a lies on the simple path from x\to b. Otherwise, x lies in the subtree containing node b.

Solution (summarized)

Let S be the set of nodes of the hidden (sub)tree.

  • Find any one direct edge between the nodes of S, using the method specified in “Hint 1”. This requires exactly |S|-2 queries.
  • Calculate the two set of nodes (call them A and B) comprising the subtrees formed on deleting this edge from the tree. This is also accomplished using |S|-2 queries.
  • Do the above operations recursively for S=A and S=B.

It can be shown mathematically that the above method uses at most N^2 queries overall.

Proof

We prove by induction.

Let f(x) represent the maximum queries required by the above method, to determine all direct edges of a graph consisting of x nodes.

Let’s assume f(x) \le x^2 for all 1\le x\le k.
When x=k+1, the above method uses 2\cdot(k-1) queries to split the tree into two subtrees. Let the size of the formed subtrees be a and b respectively (where a+b=k+1).
Then, the maximum total number of queries required is:

f(k+1) = 2\cdot(k-1)+f(a)+f(b) \\ \le 2\cdot(k-1)+a^2+b^2 \\ \le a^2 + 2\cdot ab + b^2 \\ \le (a+b)^2 = (k+1)^2 \\ \ \\ \implies f(k+1) \le (k+1)^2

The base case, with x=1 has f(x)=0.
Thus proved.

TIME COMPLEXITY:

Determining each edge of the hidden tree takes \approx O(2\cdot N). The total time complexity is therefore:

O((N-1)\cdot(2\cdot N)) \approx O(N^2)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

1 Like
2

Does anyone have edge cases where a solution might fail? I seem to have implemented the solution in the editorial, but still fails with WA - CodeChef: Practical coding for everyone

3

Alternate approach:

  • assume tree rooted at 1

  • ? 3 1 i j for(all i, j)

  • if its one that means j is in subtree of i. do size[i]++, ancestor[j][i] = 1;

  • Recursively pick any node having size[node]=0, set topo[node] = current_time, do size[i]-- where ancestor[node][i] = 1

  • basically we are doing toposort and tracking level/time of each node in the toposort.

  • for each i the parent[i] is that ancestor which have least topo time. i.e ancestor[j][i]=1 and topo[j] is least among them

TC O(n * n) Query - Exactly (n-1) *( n-1)
Code: Drkog7 - Online C++0x Compiler & Debugging Tool - Ideone.com

10 Likes
4

Can some one help me whats wrong in my approach, Mine is similar to assuming the tree rooted at one and querying for every subtree. CodeChef: Practical coding for everyone.

A test case that fails will be more helpful.
Thanks in advance.

6

How is did this
2.(k-1)+a^2+b^2
got reduced to:
a^2+2ab+b^2 ???

7

Hey, 2*(k-1)+a^2+b^2 didn’t actually got reduced to a^2+2ab+b^2. But we are saying that 2*(k-1)+a^2+b^2 will definitely be less than or equal to a^2+2ab+b^2.

To prove this, if we remove a^2 + b^2 from both side.

We need to prove 2.(k-1) \leq 2ab or simply dividing both side by 2, we can say (k-1) \leq ab.

Now, given that a+b=k+1, it is easy to see that there are no cases where (k-1) can be greater that a*b

2 Likes