WALKBT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Denis
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah

PROBLEM

Given a full binary tree with height n, any binary number made up of n bits corresponds to a path in this tree (leading zeros are added if necessary). You start at the root and take each bit a 0 corresponds to left move, and a 1 corresponds to a right move. So each number represents a path that visits a chain of nodes. At the beginning you will have a starting given number X.

You will be asked queries of 2 types:

The first type is to increase the value of X by a given value V.

For queries of the second type, you must report that for all values that X was set to during our queries (consider the corresponding path to each single X of them), how many nodes in our binary tree was visited at least once (modulo 109+7)

DIFFICULTY

hard

EXPLANATION

An easier version of this problem would be by providing input data such that at no time the number representing our path is equal to or bigger than 2n (no modulo). According to this constraint, all numbers would be given in increasing order (because each one of them is a result of adding an integer value to the previous one and numbers are less than 2n). If our previous number was X and it turned to Y after performing the last query; Well, we have visited n-LCP(X,Y) new nodes. LCP(X,Y) is the longest common prefix of the binary representations of X and Y. (It’s easy to prove by yourself).

The idea behind solving this problem is really tricky. Actually, you would think for the first while that storing all integer numbers we have processed while reading the input is impossible (due to huge constraints). Well, think again.

Well, let’s check what happens to a number when we add 2x to this number. (Assume that bits are ordered from left to right, the most significant bit is the leftmost). We would look to the closest zero to the left of the xth bit (including itself) and flip all bits between (including these 2 bits). If there’s no zero to the left (then we just flip all ones starting from the leftmost bit and finishing at the xth, and the modulo cancels the leading one that should appear).

Let’s tell how can we store such all of these numbers, let’s build a segment tree for our first number (which is given in the input). Now flipping a consecutive segment of bits in this number can be done using a segment tree, so how can we store our new number without consuming a linear block of memory. Well, we need a persistent data structure, all information about persistence can be found in this blog. So each number consumes only (log N) memory. Our segment tree must support lazy propagation so that each flip query runs in O(log N).

So we will keep our numbers into a balanced BST (C++ STL set would just do the job). After inserting a new number into an ordered set, calculating the new answer is not that hard.

Consider that our number is denoted by X

The strictly larger number is denoted by nxt

The strictly smaller number is denoted by prev

Our current answer is denoted by A

NewAnswer = A + (n-LCP(prev,X)) + (n-LCP(X,nxt)) - (n-LCP(prev,nxt))

We have subtracted the last term because (prev,nxt) are no longer successive numbers in our set.

The last part of our problem is implementing the LCP function, which is nearly the same as implementing the operator < which our set sorts numbers according to. We have concluded that each number needs only additional log N memory to be stored (and we can have full feedback about this number and perform queries on its sub-segments). Comparing 2 numbers is not that hard, each node in the segment tree of any of them is responsible for storing specific data about the bits covered by this node. Maintaining a hash value for each sub-segment of our numbers (my hash was to store the sum of values of bits in each interval modulo 2 big primes instead of normal hashing and worked fine). So when we compare 2 numbers, we are kind of doing a binary search for the first mismatch between these two numbers. At the first step while we are processing both roots of our segment trees, we would either step to the right child to find the first mismatch and adding the whole left part as a part of the LCP (if both left children hashes were identical) or look for the mismatch in the left part (so after the first step eliminating half of the bits), continuing using the same approach by going left or right according to the position of the mismatch (similar to binary search in a binary tree) would end us with the first mismatched position in log n steps. Turning the LCP to an operator is quite easy, just look for the first mismatched bit between our numbers and report according to which is smaller than the other.

The most important detail we should take care of while implementing is that persistence means creating new nodes whenever we update a node. For lazy propagation, we are postponing some updates to parts of the tree so we can do them later while going down, well pushing old updates to deeper nodes in our tree obligates us to create new versions (the same situation holds when we use comparator/operator or the LCP function). Anyway, this problem is a really cool exercise if you haven’t tried lazy propagation with persistent data structure before.

Solution runs in O(Q*log^2 (n))

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: Can be found here
TESTER/EDITORIALIST’s solution: Can be found here

5 Likes

My approach to this question was different.

I represented the number by an array. Now for each time we have to flip numbers , let the change in the array is coming from index a to b. (b-a) averaged over all the case will be constant. Now the new array is same as the previous array except from indices a to b. Now I created a linked list in which each node has

  1. Number of nodes pointed by that particular node ( maximum 2 )
  2. Address of nodes pointed by it
  3. Value at that node (either 0 or 1).

Now since the updated array is same as previous array from index 0 to a-1 , I checked at which index greater than a-1 we can’t move ahead in the linked list (let this index be i) So we will add n-i to the answer and forming b-i new nodes connecting it to i to b+1 ( So it will be kind of new path between i to b .)
From b+1 onward the array is same as previous so there is no necessity of making new nodes for them. I always stored addresses of nodes which are representing current array in a separate array for implementation.

Now I am not exactly sure why i was always less than b.

I was failing some test cases when I was connecting it to b+1 but it passed when I connected it to b+200.

My Code

can someone please explain the calculation of LCP part…i cannot understand it…

I would like to introduce a simple and direct solution:) First, we build a trie as we do for N <= 2000. We hope to solve the problem with some improvement. With some observations, we can find that as N becomes big, there are so many nodes with only one child, which means the trie contains a lot of straight links. Why not shrink the link into a node to speed up the solution? So I improve the trie:

  1. a node is no longer storing only one bit but many bits.

  2. a node has two children or no child because if it has only one child, it can be shrunk.

  3. When we add the value, we may need to split a node.

  4. We still cannot store all bits on every node with a int, so we need to compress the bits. In my solution, I compass 30 bits into a int

Please see details in my solution:


[1]

I don't know the exact complexity of my solution, but it indeed passed. I am afraid it will be hacked by some extreme data. Welcome any comments or questions about my solution, please:)


  [1]: https://www.codechef.com/viewsolution/14974736
1 Like

So to solve this problem I need to implement a cool persistent segment tree that supports lazy propagation… or just use Python? :stuck_out_tongue:

5 Likes

I solved this question using boost/multiprecision/cpp_int.hpp. My solution is indeed hacky (but interesting) and passed after multiple attempts.

Link to my code