BINTREEQ - Editorial

PROBLEM LINK:

Practice
Contest

Author: Constantine Sokol
Tester: Pavel Sheftelevich
Editorialist: Praveen Dhinwa

DIFFICULTY:

easy

PREREQUISITES:

knowledge of lca

PROBLEM

We are given an infinite binary tree with each non-leaf node having exactly two children. Root of the tree is numbered 1, for a node k, its children nodes are numbered 2 * k and 2 * k + 1.

For any two nodes u, v, the unique path between them can be represented by a list of moves to do to start from node u and end up at node v without visiting any node more than once. Each move can be one of the following four types.

  • Move to the left son - move from k to 2 * k
  • Move to the right son - move from k to 2 * k + 1
  • Move to the parent as a left son - move from k to \frac{k}{2} if k is an even integer
  • Move to the parent as a right son - move from k to \frac{k - 1}{2} if k is an odd integer

You are an integer n \leq 10^9. You will be asked many queries of following kind

  • Given a pair of nodes (u, v \leq n), find out how many pair of nodes (w, t \leq n) are there such that the list of moves corresponding to path from w to t is same as the path from u to v.

QUICK EXPLANATION:

  • If we fix the LCA (lowest common ancestor) of the pair of nodes, then corresponding vertices w, t will be uniquely defined due to the constraints of move list being same.

  • So, we just need to count number of nodes x representing LCA of (w, t), such that both (w, t) \leq n

  • Let us defined a binary function valid(x) denoting whether the (w, t) corresponding LCA node x are both less than or equal to n or not.

  • Notice that function valid is monotonic function, which allows us to use binary search to find the largest value of x between 1 and n, such that valid(x) is true.

EXPLANATION:

Simply the counting

Let l be the LCA of u, v. We want to count the number of pairs of nodes (w, t) with its path move list being same as path move list for u, v.

Instead of counting a pair of vertices, what if we count just the number of vertices which can be the potential lowest common ancestors.
If we fix the lca L of the pair of nodes, then the corresponding pair of vertices w, t will be unique for this L due to the constraint that of path move list for w, t should be same u, v should be same. Let us see the way of finding w, t for a fix L.

We can find w in the following way.
First find the list of moves for moving from LCA(u, v) to u. For this, we first find the list of moves from u to LCA(u, v) by keep on moving to parent till we reach the LCA(u, v) node. The list of moves for moving from LCA(u, v) to u, will be reverse of this move list.
Now we apply the exact same list of moves starting from vertex L, the vertex at the end will be the vertex w.

Similarly, we can find the vertex t too.

def find(x, u, L)
	list = get_list_of_moves(u, L)
	reverse list
	return apply(x, list);
    
w = find(x, u, L)
t = find(x, v, L) 

Now solve the original problem

Now, we just need to count number of LCA nodes L such that both the corresponding (w, t) \leq n.

Let us defined a binary function valid(L) denoting whether the (w, t) corresponding to this node L are both less than or equal to n.

Notice that if we go over L from 1 to n,

Notice that function valid(x) is a monotonic function. It will be of following kind {T, T, T \dots, F, F, F, \dots}, where T denotes true and F denotes false.

In simple terms, if valid(L) is false, then there won’t exist some L' > L such that valid(L) is true for it, i.e. once valid(L) becomes false, it will always remain false.

def valid(x):
	find w, t as stated before.
	return w <= n and t <= n

This observation enables us to use binary search over L. The range of binary search will be L from 1 to n.

int lo = 1, hi = n, ans = 0;
while (lo <= hi) {
	int mid = (lo + hi) / 2;
	if (valid(x)) {
		ans = mid;
		lo = mid + 1;
	} else {
		hi = mid - 1;
	}
}

Time complexity

Time complexity of the algorithm will be O((log n)^2). One log n for binary searching, other log n for valid function.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like

there is a simpler approach to solve the question without using binary search!!!
COMPLEXITY:LOG(N)
first of all find the lca of the given two nodes(u and v)!!! now there is a very nice property to observe
that is that the we just need to search for the lcas within the given tree… now if after some transformation on lca it transfoms into u(u>=v,u can swap if v>u)…let this transformation be T then we need to basically search for the last node on which if we apply the transformation T , then we will get a value less than the maximum no. of nodes!!! so basically i will reach the nth node and do the same operations on it that i did on u to get the lca of u and v!so if lca of u and v was u/2 then the answer to this problem will be n/2 and n/2 will surely be the last node that will have this property…(basic property to find out is that the lcas are continuous … lcas cant be 1,2,4,6 they have to be 1,2,3,4,5,6… plzz ask if i wasnt able to explain it properly… i will try to give a better explanantion!! thank u …
link to my solution: CodeChef: Practical coding for everyone
My given solution is log(n)^2 as i was short of time in contest. basically i am finding out the lca in logn^2 but it can be found in logn!

9 Likes

I did it in O(log n).
First find LCA. Then i calculated the linear equation required to convert this LCA into max(u, v). Let the linear coefficients of this equation be a and b.

Now we need to find max index i such that
a*i + b <= n
=> i = floor((n-b)/a)
i is the required number.

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

3 Likes

I solved in log^2. Later realized it could have been done in log

@sanyamg123 : I would like to point out the following:

  1. You may have declared an array of size 30 (log(10^9)(base2)) instead of size 100
  2. The nested loop which was used in the code results in time complexity O((logn)^2)

If you feel that I am mistaken please reply. Else, if I am correct, and you know a method that solves it in logn time, please share.

@meetrockstar : Sorry .plz check out the last line that i forgot to mention yesterday! Sorry for inconvenience and yes i took an array of size 100 just in a hurry!!thank you!

3 Likes

I did it in nilesh3105’s way. log(n) is enough. Finding LCA of (u, v) took log(n). We want the largest LCA that holds same path configuration as max(u, v). There exists a linear relation between max(u, v) (let’s assume max(u, v) = w) and LCA (let’s assume LCA = p) is p * e = (w - x), where e = 2^(distance between p and w). e can be determined in log(n) and x can be determined easily from linear relation as now we know p, e, w. Then we try to imagine n as w and find largest lca, which is ans = floor((n - x) / e)

1 Like

Why vaild(L) is a monotonic function , i can’t understand in the context of the explanation !!!

@prince_kumar valid(L) is a monotonic function because, if for a node ‘X’, considering it as an LCA, if we can find a pair of nodes (w,t) for w,t <= n, following same steps as between LCA (u,v) to u and v for w and t respectively , we can say, all the nodes which are less than ‘X’, will surely give a pair of nodes (w,t) for w,t <=n, so we can say that valid(L) is monotonic function.

I am getting runtime error …please help me to get the error…here is my solution CodeChef: Practical coding for everyone

What does (w,t) <= n mean? All the nodes are lesser than n right?

@nilesh3105
i did almost same solution as urs but got WA…can u help point out the error.
https://www.codechef.com/viewsolution/9943692

The binary tree is actually infinite and the query is defined in such a way that we have to consider the portion in which the maximum node number is n.

+1, A very nice and simple idea! By the way, why do you think that there may be a bug in line number 81?

How did you come up with the idea of the existence of a linear relation between the lca and max(u,v)? Intuition?

@snk967: hahaha no thaat was just like that!!! while writing the code for the first time wherever i think there can be an error!!! i write this over there!!!
Well actually there wasnt an error there … that is why it worked!!! thank you and plz upvote!

3 Likes

@sanyamg123: I have already upvoted your answer! “+1” was an indication of that.

1 Like

@snk967: thnxxx

1 Like

had a feeling after working out some cases. thing is, you either do 2n or 2n+1 to go down a level. grandchildren(!) will be 4n, 4n+1, 4n+2, 4n+3. likewise, 8n, 8n+1, … , 8n+7. i hope you got the idea.