Given an array of 100 integers(64bit signed). Task is to pick a subset for which the xor of the elements of the subset is maximized.
Example : 1= 01 3= 11 2= 10
if we pick 1,2 then their xor is maximum (01 ^ 10 = 11). also we can pick only 3 but the maximum result is 3 anyhow.
The original problem is described in the following link: http://www.lightoj.com/volume_showproblem.php?problem=1272
This problem is included in Gaussian Elimination section but I can't find how GE can be applied to this problem.
Can anybody give me any hints? It would be helpful. Thanks in advance.
This problem is an easy version of 251D - Two Sets. You can read the Editorial for this that problem for get some ideas. If you need some implementation details check my solution 3466112. I hope this can help you.
Hey, I am new to Gaussian elimination. I tried to understand your code but could no figure out how gaussian elimination is checking if there exists at least one partition which satisfies the current condition together with all conditions we've already set up.
Can you please explain how add_const is doing that. Also resource to understand gaussian elimination.
You can read the background of this problem http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1050
Over the next 9 days many people will need help with this topic.
@abplus
Although it is nothing to do with that problem . That is rather simple .. :D
Oh really?
did you mean codechef
A similar problem is http://www.spoj.com/problems/XMAX/
I tried this Problem using Gaussian elimination. Here is my solution — http://ideone.com/kPsoAm But, it's giving the wrong answer while submitting to https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2683. Do pls, help a bit. Test case, where it may fail will be appreciated or if possible, error in the code too.
Notice that the problem asks for continuous arrays
1 6 2 2 4 4 8 8