Explain your logic step by step or write well commented solution at least.
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[]
2 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
This man is a genius.
3 Likes
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
@chaitan94
About your Gaussian Elimination soulution: http://www.codechef.com/viewsolution/5616381
The logic is correct. But there is small flaw in implementation. The above code will give wrong output for following test case
1
3 1
12 10 8
This is because of how STL set works. For correct result, just swap these two statements
s.erase(t);
s.insert(t^m);
Where else can we use gaussian elimination technique other than this example and the traditional example of solving linear equation?
Where else can we use gaussian elimination technique other than this example and the traditional example of solving linear equation?
“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?
Numbers up to 1000 have powers of 2 up to 9 in their binary representation (2^9 = 512).
Hence, the xor of these numbers is at most “1111111111”, i.e. 2^0 + 2^1 + … + 2^9 = 1023.
How do we find out a sub-array having maximum xor value?
sorry, I’m forget to add the word efficiently.
This informative article was very inspiring visitors
I hope there will certainly be content to teach the next content
Please also visit my web site at Garden Statue
This article was very inspiring visitors
I hope there will be content to instruct the next content
You should also visit my web site at Bali Buddha Statue
the pc is usually a software that we are able to use to lift websites cooperating with search engine optimization techniques. for those of you who would like to learn web optimization please visit our website Jasa SEO
the pc is a instrument that we uses to improve websites working with search engine optimization methods. for those of you who wish to learn assist in please visit internet site