“The first observation is that F§ can be at most 1023 since any input number is at most 1000”.
How can we conclude that ?
I used Gaussian elimination to transform the input array A into the lower echelon form which is an equivalent representation of the above array (in which the array of bits [1101, 1001, 1010, 111, 11, 1] for example gets transformed to something like [1111,101, 1] – decreasing order of bits) Now it is easy to maximize the XOR value greedily. Start iterating with max = k from the left, and include the element only if the XOR value increases, else move on. Output max at the end of the iteration.
3 Likes
I tried doing this in the problem. This is the link:: discrete mathematics - Maximization with xor operator - Mathematics Stack Exchange
This is same as what @adijo said, I believe. But, the main idea behind this approach is setting one bit of each number one and then xoring with the numbers below in the series if they have that specific bit set, just to ensure no 2 numbers have the same MSB (most significant bit) as 1.
If this is to follow, then since we were given a k, and it also had an MSB, so shouldn’t we have xored k with every element in the series which had its bit corresponding to the MSB as 1.
But, it gave me a wrong answer. 
1 Like
I made a recursive function for solving this.
Considering that the biggest number we can make is 1023 and in any case, we can always use an empty set to get the answer as K^0 = K, the biggest number that can be attained is 1023, and the smallest (to be checked) is K.
So the answer lies in the range from K to 1023.
To take the initial input, I made an array with size 1001, using which I could directly set array[i]=1 if i was present in the input, else the value of array[i] would be 0.
One more thing I did was to go through this array and make a new array which only holds all the elements in descending order.
Now we basically need to check for each number from 1023 to K+1, whether that number can somehow be made with the other numbers present in the set.
The most obvious(and ultimately required) case would be if the number is directly present in the set.
The basic idea is that if some number r is required, and isn’t directly present in the set, take a number say p from the set, and again call the function for finding r^p in the remaining set. This forms the basic recursion.
But that would give a TLE, so I needed some constraints.
I was using the array in decreasing order, so the first number would be the greatest, from this, one simple constraint I was able to make was that if the required number’s Most significant bit(MSB) is greater than the currently largest number’s MSB, then there is no way to make the required number.
Using all this I was able to get AC with time 0.00 in all but 1 case, which was giving TLE.
For further refinement I used the concept that, considering a certain subset of a larger set, if a certain required number could not be made using the larger set, then it can definitely not be made using this smaller subset.
With this I was finally able to get AC that one case too, with a time 0.02
Here is my solution:
http://www.codechef.com/viewsolution/5597629
4 Likes
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 .
Which is better for large inputs - Gaussian elimination or dp?
Can anyone explain me this plz
dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]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/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[]
4 Likes
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
1 Like
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?