PROBLEM LINK:
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.