Hououin Kyouma and Xorsack
All submissions for this problem are available.
Hououin Kyouma built a time machine and went to future to a time where P = NP is proved. But, as the world lines are separated, in the new world line, people don't add numbers the way we do. They take bitwise xor to add numbers
In that world, can you solve the subset sum problem ?
Given N numbers and K, find out if there exists a subset of numbers such that their bitwise xor is K.
First line contains N and K.
The second line contains N space-separated integers A1, A2, ..., AN denoting the N numbers.
Output "Yes" if such subset exists, "No" otherwise.(without quotes)
- 1 ≤ N ≤ 200
- 1 ≤ K,Ai ≤ 109
Input: 4 101 1 2 100 1000 Output: Yes
Example case 1. We can take xor of 1 and 100 to get 101
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).
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.