XORSUB DEC14

As the editorial of the Questions has been posted
still i am not able to understand the idea used behind the Question XORSUB
i was able to pass the first subtask and 4 task in second subtask but others were giving tle
can anyone please explain me what the below line posted in the editorial means
LINK TO EDITORIAL OF THIS QUESTION

dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]

Even i was not able to understand, I got AC by using gaussian elimination.

First do the gaussian elimination, now traverse through each row. having the value of k, do k xor the first row and if the result is bigger than k, assign the value of the result to k, otherwise donot change k.

Similarly iterate over all the rows

and the final k is the answer

my link to answer :


[1]


  [1]: http://www.codechef.com/viewsolution/5569197

dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]

Here dp[i][j] denotes that there exists a subset in 1…i such that xor of elements of subset is j. For calculating dp[i][j], there are two possibilities: first,dp[i-1][j] which tells the subset in the range[1,i-1] with xor as j. 1…(i-1) is a subset of 1…i. Hence, we add dp[i-1][j]. Second: lets say there was a subset in 1…(i-1) such that its xor was j^a[i]. Now, for the subset of 1…i, choose the subset as 1…(i-1)+ a[i]. Now xor of this subset is j^a[i]^a[i]=j. Thus, it will also be added to dp[i][j]. That is what the above statement means.

2 Likes

So, telling in steps: We calculate the maximum possible xor bit by bit here. Sort all the numbers(we are doing this because we want the maximum xor and the largest number is likely to have the highest possible bit set we find that in lines 29-30 of the ideone code). Now to include this number(let this number has ith bit as its MSB), all other numbers having ith bit set should not contribute as otherwise the result will be the xor of the two i.e. 0. What I mean is let there are two numbers 7 and 6. Both have 3rd bit set, if we include 7, we cannot have 6 simultaneoulsy as otherwise 3rd bit in the answer will then be 0. This is what we are checking in lines 46-50. If any number has that bit set, we zero out its contribution by doing xor. As you can see:

for(ll row=0; msb>=1; msb>>=1)

msb here denotes the next set bit or ith for first iteration or (i-1)th bit for 2nd iteration in example you can say. If no number is found with that msb set, we move on to the next msb(lines 41-42). We check in lines 38-39, which number has that bit set. Once we get that number at index temp,

swap(vec[row],vec[temp]);

The lines just simply stores the result in sorted order and then again we want all other numbers should not have this bit set and thus, lines 46-50. The resultant vector will then have the corresponding bits which result to maximum xor. In the matrix method, you find rank of the matrix. We try reducing it by making rows of the matrix zero by applying operations like addition/subtraction/multiplication. This is exactly what we doing here with operation as xor.

Lets say I have three numbers as 3,10,9. After sorting they become 10(1010), 9(1001), 3(0011). MSB is the fourth bit. We store this number as our first result and xor with all other which have the same msb set. Here, we xor with 9 and vec[1] becomes 3. The vector now contains(10,3,3). Now repeat the same with the next msb. MSB now is 4, and no number has that bit set. Thus, we move to next msb which is 2 and the value of row variable here is 1. Doing similar in this iteration, we get vector as (9,3,3) see in the output of the code.
Write binary representation of some numbers and try manually. Read this.

Hope it clears.

Even Brute Force worked for me as well…
Analyse bits from 0 to n-1 to find all possible subsets.
Store all possible XOR’s in an array and find max(arr[i],k)…
This problem had a similar concept as that of Paying Up.
View this tutorial if you need help.

Thank you soo much for the explanation
i got a little idea what you are saying
it would be really helpfull if you could give me an example so that it is more clear
Thanks :slight_smile:

Thank you for your help
and providing your code to the solution :slight_smile:

can you please provide me anything to study gaussian elimination and how to use this
i have never known this method and cant find anything good when i searched it
if you could suggest me anything from where i could work on this technique
it would be really helpful
thanks :slight_smile:

Refer first answer on this post http://math.stackexchange.com/questions/48682/maximization-with-xor-operator and this code simultaneously: http://ideone.com/9vY2Ci

Lets say there was a subset Ai in the range [1,4] with xor as 3. Now I want to find dp[5][3](subsets in the range [1,5]). Now, Ai is also a subset of [1,5], this is what we mean by dp[i-1][j]. Now lets say there was a subset Bi in [1,4] with xor as 7 and a[i] was 4. j^a[i] is 7^4 which is 3 and hence dp[5][3] includes this subset Bi whose xor is 7 because on inclusion of a[i], xor comes out to be the number desired. Hope it clears :slight_smile: Chalk out for some more examples yourself. Happy to help.

It’d be easier to understand if you have studied that in your Mathematics class, I did in my first year. Try recalling, that will give you the real hint :stuck_out_tongue:

Ya i did studied it
but i am not able to relate it in sense of this question and i dont have any idea how to code it
btw thank you so much for the help.Really appreciate that we are having such a wonderful community

Then it’s too long as a comment. I’ll put it up as the answer here :slight_smile:
Happy to help

You sir, are really nice
great example
i finally got it :slight_smile: thanks to you
will work on some examples to make it more clear :slight_smile:

I am not sir :stuck_out_tongue: and you can mark it as accepted or upvote in case you liked. :smiley:

1 Like

Sorry ma’am :stuck_out_tongue:
You are doing a great job
thanks for everything :slight_smile:

Great explanation
thank you so much :slight_smile:

@ravidelcj Thanks, I thought you didn’t see after that cuz I wrote such long on our demand. :stuck_out_tongue: I had no way to check though!!

No no actually i saw it but as i am having my exams i dint really read it
so yesterday i read it
you are a great teacher :slight_smile:

@king_of_hacker can you please explain me your gauss elimination approach .

Are you using bitmasking to find all possible subset ?