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. :)

I wanted to ask the same question. Thanks for asking.

Represent the number X as sequence of zeroes and ones. Denote by

a_{1}...a_{m}the representation. Let's think that we knowX1 +X2 and we want to recoverX1. We know that ifa_{i}is equal 0 than the i-th bits ofX1 andX2 are equal and we know the value. Ifa_{i}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 ifa_{j}is 0. So we want to understand how to recover the i-th bit. Ifa_{i}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 vectorsv_{1}...v_{k}. The length of the vectors is equal to number of known bits, i.e ifX1 = 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 numbersalpha_{1}...alpha_{k}such thatv_{1}*alpha_{k}+ ... =X1' (X1' isX1 with skipped bits) or not. It can be checked with Gaussian algorithm. We want to find the solution ofAX=B, where X =alpha,a_{i}_{j}=v_{j}_{i},b_{i}=x_{i}Hope, my comment will help help. Feel free to ask any questions :D

Can you give source code which uses above approach?