PROBLEM LINK:
Author: Constantine Sokol
Tester: Pavel Sheftelevich
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium-hard
PREREQUISITES:
Sqrt decomposition
PROBLEM:
Let’s define bitTwister(x, y) function using the following code snippet written in Python:
def bitTwister(x, y): x ^= x >> 11 x ^= (x << 7) & 2636928640 x ^= (x <> 18) return (1812433253 * (x ^ (x >> 30)) + y) & 4294967295
You are given a tree T consisting of n nodes.
Let’s define children(v) as a sequence of the children of v placed in the increasing order of their ids.
We define children(v, d) as following.
- children(v, 0) = [v]
- children(v, 1) = children(v)
- children(v, d) = children(children(v)[1], d - 1) + children(children(v)[2], d - 1) + ... + children(children(v)[|children(v)|], d - 1) if d > 1
Let’s define reducedByBitTwister(X_1, X_2, ..., X_k) as following:
reducedByBitTwister(X_1) = X_1
reducedByBitTwister(X_1, ..., X_{k - 1}, X_k) = bitTwister(reducedByBitTwister(X_1, ..., X_{k - 1}), X_k) if k > 1
Your are asked to process Q queries of the following kind: given two integers v and d (1 ≤ v ≤ n), let’s denote children(v, d) as a node sequence V1, V2, …, Vk. Your should calculate reducedByBitTwister(A_{V_1}, ..., A_{V_k}). It’s guaranteed, that children(v, d) is a non-empty sequence for each query.
QUICK EXPLANATION:
For each of the queries, let’s find (l, r) - the leftmost and the rightmost children of v on the d'th level. After that, let’s calculate the answer in \mathcal{O}(|\text{children of v on the d'th level}|) and memoize it - if we’ll get the same pair (l, r) later, we’ll just return the value without calculating it again.
It can be shown, that such the sum of $\mathcal{O}(|\text{children of v on the }d{'th level}|) all over the testcases is no more than \mathcal{O}(n , sqrt , n)$.
The total complexity is \mathcal{O}(q * log n + n * sqrt \, n).
EXPLANATION:
Detailed explanation of the proof of time complexity being \mathcal{O}(n \, sqrt \, n) will be added later. Please have a look at tester’s solution for a very clean implementation of the approach.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
