XORSUB - Editorial

I tried couple of times.Task# 8-15 passed for Subtask 2. Subtask 1 completely failed. I am still wondering what did i miss in my solution. Here is my solution http://www.codechef.com/viewsolution/5532642

any insight will be a great help.

Thank you.

I have tried this problem and 9 testcases are not passed . This is my solution link :
http://www.codechef.com/viewsolution/5518114

Could anyone help me out .

@skysarthak Follow the algorithm in the second answer (with 4 upvotes) After you transform the array to the echelon form don’t worry about which bit is set etc, just select the value if the XOR increases, like so:

max = k

for value in array:
if max ^ value > max: max = max ^ value

print max

Which is better for large inputs - Gaussian elimination or dp?

I am doing the same thing here: http://www.codechef.com/viewsolution/5608801 I just changed the last for loop of my XMAX solution but it gives WA

Also, what is then wrong with the following approach http://www.codechef.com/viewsolution/5527772 , it’s doing the same thing by just dividing the input set in two different sets as explained in my answer below.

@damn_me,upvote my comment!!!

U are correct,Your logics are absolutly correct.
Just scratch your mind on your codes once again :frowning: :frowning:

You are pushing everything into vector.How can it be possible??!!!

vec.clear()!!!

1 Like

Can anyone tell me how this solution works? I think it doesn’t cover all possibilities?

@rudra_sarraf Thanks a lot, seems u needed an upvote :smiley: But what is then wrong with this: http://www.codechef.com/viewsolution/5609487

Can anyone explain me this plz

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

@damn_me,What I said was Just scratch your mind on your codes once again :frowning: :frowning:

But u didn’t!!!

Declaring a variable twice gives error.(ll row=0)(Always try to write clean codes.)

This time no more bullshit neither I need more upvotes than I deserve!!so,

http://www.codechef.com/viewsolution/5609023

If you find clear proof of analogy of gauss elimination method=>Then kindly comment the link (other than mathematics stack exchange=>maximization of xor operator!!).

At last but not the least=>actually (2 upvotes>1upvote)!!!

@rudra_sarraf I have already got AC on this logic. First open the code or link I have mentioned in my comment carefully and then say!! I think discussion forums are for help people want to do themselves and no one is forcing you to see someone’s problems or errors. So better not use any more harsh words here!!! And also, I was just joking for that upvote thing.

1 Like

can any one explain why gaussian method work.?? i mean after take echleon form of the matrix what happend that it is giving me sum of each subset from the given set…

I got AC by using gaussian elimination.

A simple explanation :

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

@king of hacker…

i know … i am asking as to why this method worked?

Instead of using 2-d array solution can be easily solved using 1-D array. I found that solution from submission list. Really nice logic.

http://www.codechef.com/viewplaintext/5531874

Can anyone please explain how Gaussian Elimination is applied on this problem. I saw the stack exchange link but couldn’t make out anything from that.

Once again=>Declaring a variable twice gives error.( you have declared ll row=0 twice!!)

Is that harsh??? OOPS!!

And do you really think that I was taking your joke seriously!!!(just go on thinking blah blah…)

Just skip it…(Otherwise you may complain to admin!!!)

2 Likes

did it using gaussian elimination but dp also seems really cool trick here…

loved the editorial (thnx codechef)

Don’t take anything about k into consideration and apply the algorithm as stated by llmari Karonen on stackexchange.

The only difference to be made is in maximum finding algorithm is to initialize max to k instead of 0.

Check your solution link! Its bytelandian gold coin problem.

//