XORSUB - Editorial

editorial
, , , ,
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

46

I am doing the same thing here: CodeChef: Practical coding for everyone I just changed the last for loop of my XMAX solution but it gives WA