Блог пользователя orchidmajumder

SUBSET XOR Dynamic programming
Автор orchidmajumder, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    2n - rank

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, thanks)

      → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Thanks.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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".

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
            ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

            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)

            → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      @Neodym How did you get this result ?

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

        → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 .

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :)

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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;

    }

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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

→ Ответить