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/5569197Instead 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.
did it using gaussian elimination but dp also seems really cool trick here…
loved the editorial (thnx codechef)
I would like to explain the Gaussian Elimination method which I have used and got AC in 0.00 
The link to my solution. (sorry for some dubugging statements in it).
The idea here is to choose a no. which has MSB with maximum value. With a little thinking, we will get the max(array) will have this feature. Say, maximum of array is a k-bit no. and that no. is M. Now, there can be multiple no.s which are k-bit no.s and have the same highest-value bit as ‘1’. So in that case we will EX-OR each of them with the M and put them again input array (ideally, we can choose any one of those k-bit no.s as M and put others in array after ex-oring with it).
At the same time we will keep the no. M in some other array say x[].
We will keep doing step 1 until we get 0 as maximum in the array i.e. this loop will run for iterations = no. of bit the maximum of array is.
Now will have a x[] array which will be of size = no. of bit the maximum of array is
Now we will initialize the answer variable to given K and loop for each value in array x[], if value of answer variable is going to increase with the inclusion of ith element, we will update the answer variable with the new value as answer^x[i], else we will keep it as is.
Finally returning the value of answer solves our problem.
About my solution:
Bucket[i] contains all i-bit no.s
the M chosen is first element of bucket i.e. Bucket[i][0]
x[] is modified_array[]
for i = 1 to N:
for j = 0 to 1023:
dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]
how is this working ?? getting difficulty in understanding this part , can someone explain it to me. plzzz
I tried greedy approach for this problem and it did not work. Can some one please point out the mistake in my logic/approach. Here is what I did
XOR K with each of the elements in the array. Say the result is a.
I pick the max a and then try to XOR it with the remaining elements(one element at a time) and see if the value of a is increased or not. Let us say the value is b.
If b is greater than a, then i will override a with the value of b. Repeat this process until b > a. Otherwise i will terminate the logic
Return the last value of a if a is greater than K. or else return K
Below is my solution in Java
“if there exists a subset P of A[1…i - 1] such that F§ = j ^ a[i], then F§ ^ a[i] = j, so there exists a subset P’ of A[1…i] such that F(P’) = j”
Can anyone explain the above statement?
Can anyone explain why A[0…i-1] having the value j makes it necessary for A[0…i] to have value j and also the next condition?I’m not understanding this dp.
how did we reach the conclusion that xor of any subset of the numbers less than 1000 will be less than 1023?
How do we find out a sub-array having maximum xor value?
No, it wasn’t there in the beginning… 
I think that not only you used this approach. It is incorrect, because you have to take k in the resulting subset and not might to take it.
Yes.I realised it later that k may or may not be taken into consideration in some cases but the co-incidence is great or maybe the test cases fake! 
Because all numbers less or equal 1000 are written on 9 bits and any bit operation on two numbers which are written on 9 bits results also in a number written o 9 bits. The maximal number which may be written using 9 bits is 1023.
Ai <= 1000 was there at least from 9pm GMT of December 5th, when I read the problem.
@adijo i tried with the same Gaussian Elimination technique but my code failed for subtask 2…any suggestions on where i went wrong…CodeChef: Practical coding for everyone
So your code can solve it for A < 2^30 for example? I have to check that 
I was not able to find the solution for that…