Practice

Contest

Medium

Pre-requisites:

Dynamic Programming

Problem:

Given a sequence of positive integers a[1], a[2], a[3], …, a[N], find how many sequences of nonnegative integers b[1], b[2], b[3], …, b[N] exist such that

1. b[i] <= a[i], and

2. the bitwise xor of the two sequences is equal. That is,

a[1] ^ a[2] ^ … ^ a[N] = b[1] ^ b[2] ^ … ^ b[N].

Explanation:

The most useful thing about the XOR Sum of numbers, is that the different bits behave independently of each other. Thus, whenever we are given a question that asks for a special property of the XOR Sum of numbers, we process the numbers one bit at a time.

Also, in questions where we need to find the number of x[i] <= a[i] satisfying some properties, we start from the largest x[i] and go down. Similarly, here too we will start with the most significant bits of a[i], and then go to the least significant bits.

We first make the following observation:

If a number we are considering (some a[i]) is 2x - 1, then by varying over the values from 0 to 2x - 1, we get all possible values of the xor-sum corresponding to those least significant x bits. Thus, since we have a target of just one particular value, we divide the “total number of such numbers” by 2x.

Let us start from the most significant bit, and try to ensure that that bit in the xorsum is the same as the one we need. Let the number of numbers having the current (say k’th) bit = 1 be M. Denote by c[i], the least k significant bits of a[i]. We need to count the number of numbers we can make b[i] <= c[i], where the xor of the b[i]'s k’th bits = (M % 2) (this is so that it gives the same xor value at this bit). Also, we ensure that atleast one of the i’s whose c[i] value has the k’th bit = 1, has the k’th bit of b[i] set to 0. This is so that the remaining bits can then be chosen arbitrarily, and also because the case where all the bits are counted as 1 will be accounted for in further iterations, where we discard the k’th bit from c[i]'s.

Thus, let us consider the k’th bit as being considered, and let f(i, k, j) = number of ways of choosing numbers b[1], b[2], …, b[i], such that the k’th bit’s xor value of b[1], b[2], …, b[i] = j. Also, we need to keep track of how many numbers of b’s are there such that all the corresponding b[i]'s are set to 1 whenever c[i]'s k’th bit is 1 (call this “one”), and how many numbers of b[i]'s are there when c[i]'s k’th bit is 0 (call this “zero”). This is because we need to exclude such numbers from our final calculation. Finally, we add the quantities (f(N, k, M%2) - one*zero) / 2k to our answer, and carry on (you may like to see this answer for further clarification after reading the below pseudocode).

Pseudocode follows:

``````
// given initially c[i] = a[i]
for k = 29 to 0
F[0][k][0] = 1, F[0][k][1] = 0
one = 1, zero = 1
M = 0
for i = 1 to N
if( (c[i] & (2<sup>k</sup>)) > 0)
M++
c[i] -= 2<sup>k</sup>
one = one * (c[i]+1)
f(i, k, 1) = f(i-1, k, 1) * 2<sup>k</sup> + f(i-1, k, 0) * (c[i]+1)
f(i, k, 0) = f(i-1, k, 0) * 2<sup>k</sup> + f(i-1, k, 1) * (c[i]+1)
//the above two are because of considering the case where we set the k'th bit of b[i] to 0 - which gives us 2<sup>k</sup> numbers, or we set it to 1, which gives us numbers 0 to c[i] (i.e. c[i]+1 numbers in total)
else
zero = zero * (c[i]+1)
f(i, k, 1) = f(i-1, k, 1) * (c[i]+1)
f(i, k, 0) = f(i-1, k, 0) * (c[i]+1)
ans += (f(N, k, M%2) - one * zero)/2<sup>k</sup>
output ans + 1 // the +1 corresponds to the case where all bits of b match all bits of a

``````

NOTE: While dividing by 2k, we should do the division as multiplication by inverse modulo prime 1000000009, as are all the multiplications etc.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

3 Likes

A very similar problem was used as the hard problem in TopCoder SRM 564 Div 1(which took place in December 2012): http://community.topcoder.com/stat?c=problem_statement&pm=12346&rd=15186

That problem asked for the same thing, except that the xor of the b[i] values had to be equal to a given value (and not necessarily to the xor of the a[i] values). Admittedly, n was at most 50 there, so solutions with a worse time complexity could still be accepted. For instance, I had an accepted solution in the practice room, but it was very difficult to adapt it to be accepted during the cook-off.

2 Likes

Thanks for the great editorial! However I am still a bit confused on the solution.

More specifically about the implementation, could you please define precisely the following:

What exactly does it give by having “one * zero”?

Why exactly do we need to divide it by “2^k”?

What exactly does it give by having “(f(N, k, M%2) - one * zero)/2^k” ?

@lxfind, let me explain that bit a little more clearly.

f(N, k, M%2) says, considering all the b[1], b[2], …, b[N] numbers from the least significant k bits, find how many such b[i]'s are possible having the target XOR of the k’th bit = M%2. When we are calculating this, we are accounting for the possibility of all b[i]'s k’th bits being 1. We need to ensure that we exclude these numbers. Why?

Because, if we exclude any one or more of those b[i]'s from taking the value 1 at the k’th bit, then by varying over all numbers for those b’s least significant k bits, we would get all possible values of the least significant k bits. This is easy to count, and further, implies that we are double-counting our target value by exactly 2k. Also, remember that f is counting how many b[i]'s are possible with b[i] <= c[i], and the k’th bit of b[i]'s xor to the required answer: with no constraint on where the remaining bits xor to!!

Also, when we take further iterations of k from 29 to 0, the case of all b[i]'s k’th bit being 1 will be counted later - as we are setting the k’th bit of c[i] to 0 at that stage. You can further think of f(:, k, to be a state of computation where you are counting b[i]'s whose (k+1, k+2, …, 29)'th bits all match that of a[i]'s.

Thus, so far we have established that we need to add a term that looks like (f(N, k, M%2) - something)/2k to our answer. That “something”, is “the number of b[i]'s whose k’th bit matches that of c[i] (or a[i])” - Remember that we are trying to exclude the case where all the b[i]'s k’th bits are 1, and for the others whose value is 0, it is because it is forced to be 0 by c[i], which is in other words, the number of b[i]'s, whose k’th bit matches that of c[i]. ‘one’ is the variable that stores the number of b[i]'s whose k’th bit is 1 and matches that of c[i], while ‘zero’ is the variable that stores the number of b[i]'s whose k’th bit is 0 and matches that of c[i]. The variable names used here were adopted from the setter’s approach, but I see now that I could have just kept a variable “matched” instead that stored it.

@satej, here I should mention that there is no typo at f(N, k, M%2) - one * zero. The Editorial’s pseudocode varies from yours in that f here aggregates over all b[i]'s, including the ones where the corresponding c[i] has 0 as the k’th bit.

As a final sanity check, you might like to check that 2k actually divides f(N, k, M%2) - one * zero. Well, note that for each time the code runs into the “else” (i.e. c[i]'s k’th bit is 0), we are multiplying f(i-1, k, [0|1]) by c[i]+1. We are doing this for the variable “zero” as well. Hence, we can take zero out common from the f(N, k, M%2) - one * zero term. What remains is something that looks like “terms * 2k + terms * (c[i]+1)”. If there is atleast one 2k term in the remaining sum, we are happy; and in fact, the non-2k terms come precisely from the multiplication of f(i-1, k, [1|0]) by c[i]+1. Which is exactly what is stored in the variable “one”.

Finally, we need to output “ans+1” at the end, since the +1 corresponds to the entire b sequence being equal to the a sequence. (This is something I missed out earlier - and will edit now - but I should thank you, because answering your doubts gave me a better understanding of the solution myself :)).

4 Likes

I solved this problem in practice room right before writing this. And I would like to share my understanding. Basically, we can solve the problem by dividing all b[i]'s sequences into disjoint sets which satisfy the constraints. For example, when input sequence is {3, 3}, the number of sequences of b[i] whose xor sum equals to that of input and b[i] <= a[i] will be 4,({0,0}, {1,1}, {2,2}, {3,3})

According to the editorial, we will divide these sequences and count the number of these sequences at each k-bit stages. I will give an example, Because 3 is represented with 2 bits, we will consider only when k=1 and 0 in this example. (Please remember we are using 0-based index and all numbers will be represented in binary form)

1. k=1, we will count (00,00) and (01,01)
In this stage, we first consider all b[i]s which is equal or less than a[i] before considering xor sum and repetition. There are 8 sequences which satisfy the constraint. (I also calculate the xor sum of the numbers in the each sequence after “->”)

(00, 00->“00”), (00, 01->“01”), (01, 00->“01”), (01,01->“00”)

(10, 10->“00”), (10, 11->“01”), (11, 10->“01”), (11,11->“00”)

Second, we will remove one * zero sequences, the sequences (which correspond one * zero) will be these. (We have to remove these sequences for counting without repetition, and we will count the sequences later stage)

(10, 10->“00”), (10, 11->“01”), (11, 10->“01”), (11,11->“00”)

Now, we have these 4 sequences left.

(00, 00->“00”), (00, 01->“01”), (01, 00->“01”), (01,01->“00”)

We have only considered b[i]<=a[i] constraint and not considered xor sum constraint. How to find the sequences among these which satisfy xor sum constraint? It’s not hard, Please read their xor sum. As you know, the number of xor sum “00” is 2 and the numer of xor sum “01” is 2. The numbers are double counted by 2. That’s why we divide by 2^k at each k step. Because in this k=1, we will divide the number of sequences by 2^1 and finally we get the number of sequences 2

1. k=0, we will count {10, 10}
In this stage, we will count the number of sequences by same reason of stage 1. We will only count the sequence (10, 10) here The reason is why all numbers in this sequence start with ‘1’ is because we remove one*zeros numbers in the previous stage.

After completing all stages, the final answer will 2+1+1 = 4 (The last 1 means the sequence a[i] itself)

In summary,

1. For counting without repetition, we removes the one*zero sequences at each kth step.
2. All sequences are double counted by 2^k, that’s why we divide the number by 2^k

Although I did not prove why all sequences are double counted by 2^k, I think We can get the observation easily by trying some other sequences. (Please try (5,5) whose binary representation is (101, 101).

6 Likes

Hi,

I am a beginner on CodeChef and I am trying to improve DP. I have been trying to understand the editorial of this problem since a very long time, but I simply do not understand it.
Are there any other basics required for this that are missing. This editorial is very complex and is simply not suitable for beginners like me. Can someone please explain it to me in easier terms with an example.
What is the approach. Why do we calculate one and zero? I cannot understand almost anything in this post.

this cook-off seemed more like `Lets practice Dynamic Programming`!

2 Likes

Thanks mugurelionut for that topcoder problem.
I remember myself participating that SRM, and tried it with some weird (http://community.topcoder.com/stat?c=problem_solution&rm=315140&rd=15186&pm=12346&cr=8513659) and did not get it.
By the time I was formulating this problem idea, I completely forgot about that problem. Initially this was my SIMPLE problem idea where N is exactly 2.That version had a nice solution of logarithmic complexity. But later got another idea to find that the bound can be extended large enough to expect O(N) solution.

The reason I put the xor to be equal to the initial number just not to break the loop (for k = 29 to 0 in the editorial)earlier.

Sorry for the confusion with the variable naming.
zero is the total number of possibilities for the integers whose current bit is 0.
one is the total number of possibilities for the integers whose current bit is 1 and we select 1 for that.
there is a typo in this line (f(N, k, M%2) - one * zero)/2^k
It should be (f(N, k, M%2) - one)*zero/2^k.
once you subtract one from f(N, k, M%2) it will be a multiplication of 2^k.

I find this problem very smart. I had a rough time understanding editorial though, so I just want to state the key idea: after the first bit where some b[i] is different from a[i], we can assign remaining bits almost arbitrarily, because for any choice of other b’s there is exactly one choice for b[i] and it will not violate b[i] <= a[i] condition. Maybe you could add something like this into “Quick Explanation”.

“In this stage, we first consider all b[i]s which is equal or less than a[i] before considering xor sum and repetition.” Why are only 8 seqences obtained for this case . Shouldn’t it be {0,1,2,3}x{0,1,2,3} since you are considering all possible b[i] and not considering the xor sum at this moment?

I know it is pretty old but can you please clarify this?

@retuor89. only consider those combinations which give correct xor sum at the kth (here k=1) bit. 8 combinations give xor sum 1 at kth(=1) bit which is wrong