# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

# 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:

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:

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