_Muhammad's blog

How to solve D. Two Sets using Gaussian Algorithm??
By _Muhammad, history, 6 years ago, In English

I have learnt Gaussian algorithm recently. I am stacked in 251D - Two Sets.

I have read the editorial of this problem. I can find the max value of X1+X2. But in case of tie. I am not getting how to check is it good to give 0 in i-th bit of X1 when i-th bit of X is 1 and also not understanding how give 0 in i-th bit. I have saw some Ac code but I am not getting what they have done. So please can any one tell me how can I do it.

Thanks in advance. :)

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Represent the number X as sequence of zeroes and ones. Denote by a1 ... am the representation. Let's think that we know X1 + X2 and we want to recover X1. We know that if ai is equal 0 than the i-th bits of X1 and X2 are equal and we know the value. If ai is equal 1 we don't know the i-th bit of X1.

Let's recover bits one by one. We've already recovered the first i - 1 bits and also we recovered the j-th bit if aj is 0. So we want to understand how to recover the i-th bit. If ai is 0 we know the answer, otherwise we want to try to put the i-th bit equal 0. How to check if we can do it? Let's represent our given numbers as vectors v1 ... vk. The length of the vectors is equal to number of known bits, i.e if X1  =  010??1? then we just skip unknown bits and length of the vectors is 7 - 3 = 4. So we want to know whether there exits such numbers alpha1 ... alphak such that v1  *  alphak  +  ... = X1' (X1' is X1 with skipped bits) or not. It can be checked with Gaussian algorithm. We want to find the solution of AX = B, where X = alpha, aij = vji, bi = xi

Hope, my comment will help help. Feel free to ask any questions :D

→ Reply