BITTWIST - Editorial

PROBLEM LINK:

Practice
Contest

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}(| ext{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}(| ext{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.

2 Likes

When do you plan to publish the full explanation? Thanks!

6 Likes

Waiting for full explanation

2 Likes

Still waiting :slight_smile:

2 Likes

Still Waiting :slight_smile:

2 Likes

Still waiting :slight_smile:

2 Likes

Still waiting :slight_smile:

1 Like

still waiting

2 Likes

Still waiting :slight_smile:

1 Like

still waiting :slight_smile:

When will the full explanation be published?

1 Like