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

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

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
13 лет назад, скрыть # |
← 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?

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

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

→ Ответить
»
13 лет назад, скрыть # |
← 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 .

→ Ответить
  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 :)

    → Ответить
  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -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;

    }

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

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

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

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

→ Ответить