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
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.
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.
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,
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 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.
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 for your help
and providing your code to the solution
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
Lets say there was a subset Ai in the range [1,4] with xor as 3. Now I want to find dp(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 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 Chalk out for some more examples yourself. Happy to help.
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