Binary Ancestor

3.9

17 votes
Binary search algorithm, Hash function, Hiring, Easy-Medium, Ready, Approved
Problem

For a given sequence of integers, they get arranged into a complete binary tree. Given two numbers (a,b) from sequence, print which ancestor is first to second.(It is assured that the integers do not repeat).

A node is 0-ancestor to its own. A parent is 1-ancestor to its child. A node(X) is 2-ancestor to a node(Y), if node(X) is parent of 1-ancestor of node(Y) and so on.

A node cannot be an ancestor in any other case.

Input Format:
First line is an integer T representing number of test cases.
First line of each test case has two integers N(number of nodes), Q(number of queries).
Second line of test case has an array of N elements, values of nodes in order.
Next Q lines has two numbers each representing a query between a,b.

Output Format:
If a is kth ancestor of b, print out "k-ancestor", else print out "not an ancestor" (without quotes).
Output for each test case should be in an individual line.

Constraints:
1 ≤ T ≤ 25
1 ≤ N ≤ 105
1 ≤ Q ≤ 103
1 ≤ Ai ≤ 108

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

enter image description here

For given test case, it arranges into the tree as shown in above figure.
Explaining the figure : 1 is 1-ancestor of {2,4}, 2 is 1-ancestor of {6,8}.
1 is 2-ancestor of {6,8} since 1 is parent of 1-ancestor of {6,8}. Only these relations are possible for given case.

Qurey 1: "1 8", 1 is 2-ancestor of 8.
Query 2: "4 8", 4 is not an ancestor of 8 as we have discussed above.

Editor Image

?