JEEADVANCED's blog

By JEEADVANCED, history, 5 weeks ago, In English

can someone explain the solution of problem in easier way. Problem Link -: https://www.codechef.com/problems/AMXOR

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

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 3 for further clarification after reading the below pseudocode).

Pseudocode follows:

Spoiler

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was your JEE Advanced Rank and in which year, Mr. JEEADVANCED :P