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

# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 205 |

2 | SecondThread | 197 |

3 | Monogon | 195 |

4 | vovuh | 189 |

5 | Um_nik | 185 |

5 | pikmike | 185 |

7 | antontrygubO_o | 184 |

7 | Ashishgup | 184 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/26/2020 10:45:15 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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// 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

^{k})) > 0) M++ c[i] -= 2^{k}one = one * (c[i]+1) f(i, k, 1) = f(i-1, k, 1) * 2^{k}+ f(i-1, k, 0) * (c[i]+1) f(i, k, 0) = f(i-1, k, 0) * 2^{k}+ 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^{k}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^{k}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.

Thanks For Copy and Pasting work. i read the editorial but didn't understood what they wanna to say after some point. hence asked for help so that some one can explain it in easy different way.

What u saying I wrote it myself.

https://discuss.codechef.com/t/amxor-editorial/2069

It is different see it clearly

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

i got 4119 in 2019 :P