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