orchidmajumder's blog

SUBSET XOR Dynamic programming
By orchidmajumder, 11 years ago, In English

Hi,

I want to know is there any dynamic programming or any other approach to find if there is any subset with a given xor(just like we have dynamic programming approach to find if there is any subset with a given sum) ?

UPD: I have solved this problem with a similar approach to subset sum dynamic programming.

problem link on SPOJ

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
11 years ago, # |
  Vote: I like it -18 Vote: I do not like it

I know how to solve it, if your set contains only one number

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can solve this problem by solving system of linear equations(Gauss method) modulo 2.
x[i][j] = 1 if (a[i] & (1 << j) > 0) else 0.
BTW. Who know how calculate number of subsets with given xor?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    2n - rank

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, thanks)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi Neodym,can you please explain a bit more or give some resource from where I can read this??

      Thanks.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You should make linear transformations with your matrix(system of linear equations) — one string -> this string minus another string. Of course, all transformations modulo 2. Your goal is to get matrix with no more than one nonzero element in every column. So, some variables will depend on other variables (like x1 = x4 + x5) and some variables will independent. Number of this independent variables is a rank of matrix. Key words for search: "Gauss method", "matrixes", "system of linear equations".

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hi Neodym,

          So,if I solve the system of linear equations where left hand side is the matrix which represents all bits from each a[i] per row and right side the value (i.e the given xor) and if we can find the rank of that system of linear equation matrix by gaussian elimination,then no of subsets with the given xor will be 2^(n-rank) ?? Is my understanding correct??

          Thanks a lot,by the way!!! :) you have really explained it nice. :) I just want to verify my understanding.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            Assume each element in the set is of length m bits and there are n elements in the set. The linear system of equation represents AX = B. Now we have n rows and m columns in the left hand side matrix, A.

            What does the vector X represent which has m rows? What is the right hand side vector which has n rows?

            Can you please explain!

            Update: Everything is clear for me now! A contains the elements in matrix form m x n (one column for each element in the set) B vector contains the given xor value m x 1 (one bit per entry) X vector contains the bool value if each element of set is present in subset or not (one entry per element in set)

            → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @Neodym How did you get this result ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I've been asked this question lots of times, and now I tried to give as most correct answer as I could.

        Unfortunetely, codeforces latex redactor does not support all opportunities of tex, so I've shared a document on OneDrive.com: http://1drv.ms/1muktg0

        Feel free to ask on it, maybe I'll update this document.

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also look at the editorial for XorCards problem. It has a nice explanation there.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi sping128,Thanks a lot. Topcoder tutorials always explain it very nicely.Thanks again :) Though I have solved this particular one in SPOJ without gauss-jordan,but I really want to learn how to use gauss-jordan to solve such problems.

    Similar problem: SPOJ-XMAX

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

this can be solved very easily using just recursion + memoization. no need of Gauss method or any such thing.

if u assume that i is the current index and mask is the XOR of all elements currently in the set, the recursive function will look like int solve (int i, int mask). all u need to do is add solve(i+1, mask^a[i]) (no of subsets if we add the current element to the set) and solve(i+1, mask) (no of subsets if we don't add it).

ofcourse u need to memoize this to reduce the time complexity from to .

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got AC this way only.But I think mostly xor related problems are to be done with gaussian elimination,so it'll be better to learn that :)

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    i have applied this idea but getting wrong ans on judge at 5 test case can you help

    include<bits/stdc++.h>

    using namespace std;

    define LL long long

    LL MIN = -1;

    LL arr[100009]; LL val[100009];

    int n;

    LL dp(int i){ if(i==n){return 0LL;} if(val[i] != MIN){return val[i];}

    val[i] = max(arr[i] ^ dp(i+1),dp(i+1));
visited[i]=true;
return val[i];

    }

    int main(){ #ifndef ONLINE_JUDGE freopen("input.in","r",stdin); freopen("output.out","w",stdout); #endif

    cin>>n;

for(int i=0;i<n;i++)
    cin>>arr[i];
memset(val,MIN,sizeof(val));
cout<<dp(0)<<endl;
return 0;

    }

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be nice if someone shares their code using gaussian elimination as it would serve a great reference.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

This problem(find a subset with given xor) can be solved in log^2 maxA using linear basis.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u send some reference for that. Thanks in advance

    → Reply