spoj:xmax(Gaussian Elimination)

general
1

http://www.quora.com/What-are-solutions-to-the-SPOJ-XMAX-problem.Here i read how to solve this problem but i cant understand how gaussian elimination find the maximum xor subset any one please help… thanks :slight_smile:

2

Hello.
Suppose you have n numbers.
You can first divide the numbers in different groups, based on number of bits used to represent that numbers.
64 is the maximum possible.

Numbers which have same bit length should be in same group.
then you need to iterate over the all possible groups(1 to 64).
Everytime u choose any one number from a group, say x.(push the x in a vector)
Each remaining element should be xor’ed with that choosen element and the resultant one should be pushed to the group of appropriate length.

see this code.

#include<bits/stdc++.h>
 using namespace std;
  
 #define ull unsigned long long
 int length(ull n)
{
int cnt = 0;
while(n)
{
    cnt++;
    n>>=1;
}
return cnt;

}

int main()
{

    int n;
    cin>>n;


    ull a[n];
    for(int i=0; i<n; i++)
        cin>>a[i];


    int lengths[n];
    for(int i=0; i<n; i++)
        lengths[i] = length(a[i]);


    vector<ull> gauss_bucks[65];
    for(int i=0; i<n; i++)
        gauss_bucks[lengths[i]].push_back(a[i]);


    ull final[100], m_index = 0;

    for(int i=64; i>0; i--)
    {
        if(gauss_bucks[i].size())
        {

            final[m_index++]=gauss_bucks[i][0];


            for(int j=1; j<gauss_bucks[i].size(); j++)
            {
                ull temp = gauss_bucks[i][0] ^ gauss_bucks[i][j];
                int len = length(temp);
                gauss_bucks[len].push_back(temp);
            }
        }
    }


    ull ans = 0;
    for(int i=0; i<m_index; i++)
        if(ans < (ans ^ final[i]))
            ans = (ans ^ final[i]);


    cout<<ans<<endl;

return 0;

}

1 Like