javacoder1's blog

NEED HELP ON THIS DP PROBLEM
By javacoder1, history, 8 years ago, In English

Given N numbers and K, find out if there exists a subset of numbers such that their bitwise xor is K.

Input

First line contains N and K. The second line contains N space-separated integers A1, A2, ..., AN denoting the N numbers.

Output

Output "Yes" if such subset exists, "No" otherwise.(without quotes) Constraints

1 ≤ N ≤ 200

1 ≤ K,Ai ≤ 10^9

Example

Input: 4 101

1 2 100 1000

Output: Yes

Explanation

Example case 1. We can take xor of 1 and 100 to get 101 Note

Bitwise xor of a subset A1, A2, .., AN is equal to (..(A1 xor A2) xor A3).. AN).Each bit of bitwise xor of two numbers is calculated separately. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. For example, bitwise xor of 1(01) and 3(11) is 2 (10).

link for problem: https://www.codechef.com/problems/XORSACK

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

int dp[201][109*2+1]; // maximum value of xors is max(a[i])*2-1 dp[i][j]=1 if we can build number j with using first i numbers else 0 answere is dp[n][k]

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

    maximum value is 10^9 so the number of columns become of order of 10^9 using normal subset problem how dp[n][109*2+1] is working. could you elaborate.

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

I think it's 10^9 not 109 ! plz edit it earlier!

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

    but then it would get TLE with a time limit of 1sec. Also it would consume a lot of memory.

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

Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

MY BAD GAVE 109 INSTEAD OF 10^9. How can now the problem be solved?

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

I have a solution for a[i],k < 10^6 (it looks like knapsack problem) you can solve it like this: for (int i = 0; i < n; i++) for (int j = 0; j^a[i] < k; j++) dp[j^a[i]] = (dp[j] == true) ? true : dp[j^a[i]];

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

    with 10^6 as the maximum value of sum the array size would still be order of the order of 200*10^6 which is huge.I think there is some other approach other than the traditional one.

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

      we need only array of size [2][10^6] because dp[i][j] only updates from [i-1][k].

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

        ya space optimisation would do as the answer only depends on the previous state only.

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

      I will only use bitset <1e6> dp and it's only 125KB

      → Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

it is a better question when we swap xor operation with plus: see it

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

Let's come back to the original question.I think we have to do something with the bitwise representation of the number k as maximum value of 10^9 implies 30 bits to take care of. There would be some reason of having small value of n.

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

Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).

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

aliasadiiii said that it is solvable with gauss elimination algorithm in O(N)!! this problem is similar to your
problem.

→ Reply