XORSUB - Editorial

editorial
, , , ,
21

for i = 1 to N:
for j = 0 to 1023:
dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]
how is this working ?? getting difficulty in understanding this part , can someone explain it to me. plzzz

1 Like
22

Why my solution is not working ? I have commented my algorithm in the code.
My solution

23

I tried greedy approach for this problem and it did not work. Can some one please point out the mistake in my logic/approach. Here is what I did

  1. XOR K with each of the elements in the array. Say the result is a.

  2. I pick the max a and then try to XOR it with the remaining elements(one element at a time) and see if the value of a is increased or not. Let us say the value is b.

  3. If b is greater than a, then i will override a with the value of b. Repeat this process until b > a. Otherwise i will terminate the logic

  4. Return the last value of a if a is greater than K. or else return K

Below is my solution in Java

http://www.codechef.com/viewsolution/5534659

24

@chaitan94 why the C++ STLā€™s unordered_set is not working in place of set ??

25

ā€œif there exists a subset P of A[1ā€¦i - 1] such that FĀ§ = j ^ a[i], then FĀ§ ^ a[i] = j, so there exists a subset Pā€™ of A[1ā€¦i] such that F(Pā€™) = jā€
Can anyone explain the above statement?

26

Can anyone explain why A[0ā€¦i-1] having the value j makes it necessary for A[0ā€¦i] to have value j and also the next condition?Iā€™m not understanding this dp.

27

how did we reach the conclusion that xor of any subset of the numbers less than 1000 will be less than 1023?

28

How do we find out a sub-array having maximum xor value?

34

No, it wasnā€™t there in the beginningā€¦ :frowning:

3 Likes
35

I think that not only you used this approach. It is incorrect, because you have to take k in the resulting subset and not might to take it.

36

Yes.I realised it later that k may or may not be taken into consideration in some cases but the co-incidence is great or maybe the test cases fake! :smiley:

37

Because all numbers less or equal 1000 are written on 9 bits and any bit operation on two numbers which are written on 9 bits results also in a number written o 9 bits. The maximal number which may be written using 9 bits is 1023.

3 Likes
38

Ai <= 1000 was there at least from 9pm GMT of December 5th, when I read the problem.

39

@adijo i tried with the same Gaussian Elimination technique but my code failed for subtask 2ā€¦any suggestions on where i went wrongā€¦CodeChef: Practical coding for everyone

40

So your code can solve it for A < 2^30 for example? I have to check that :wink: I was not able to find the solution for thatā€¦

41

nice effort, nice logic :slight_smile:

42

@betlista I think it should work!

@skysarthak Can you explain your algorithm? I might be able to point out flaws there if any. If not just reimplement the algorithm more carefully

1 Like
43

Thanx @betlista & @adijo for helpā€¦I followed the first answer given here with slight modification that instead of starting with result = 0 i started with result = k where k is from F(p) xor kā€¦and while traversing the echelon form i xor the row with result if and only if the corresponding bit in result is not set while the one in the array is. After each comparison i jump to the next row and next column. If the no. of columns > no. of rows(bit representation of number is long) then the last row is xorā€™ed with the result if need be.

44

gaussian elimination for me too ! :slight_smile: got AC CodeChef: Practical coding for everyone

1 Like
45

@skysarthak Follow the algorithm in the second answer (with 4 upvotes) After you transform the array to the echelon form donā€™t worry about which bit is set etc, just select the value if the XOR increases, like so:

max = k

for value in array:
if max ^ value > max: max = max ^ value

print max