XORSUB - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

SIMPLE

PREREQUISITES:

DP, bits

PROBLEM:

You are given an array A of N integers and an integer K. Your task is to return the maximum possible value of F(P) xor K, where P is a subset of A and F(P) is defined as a xor of all values in P. If P is empty, then F(P) = 0.

QUICK EXPLANATION:

Since each element of A has a value of at most 1000, we can use dynamic programming dp[i][j] := 1 if and only if there exists a subset P of A[1…i] such that F(P) = j. In order to get the result, we return max 1 <= j <= 1023 { dp[n][j] * (j ^ k) }

EXPLANATION:

Let dp[i][j] := 1 if and only if there exists a subset P of A[1…i] such that F(P) = j, otherwise 0

The first observation is that F(P) can be at most 1023 since any input number is at most 1000.

Initially we set all dp[i][j] := 0.

Next, we set dp[0][0] := 1, since a xor of the empty set is 0.

We iterate over all elements of A from left to right. For each A[i], we iterate over all possible values of the xor function i.e. a range from 0 to 1023 inclusive and update these values as follows:

for i = 1 to N:
    for j = 0 to 1023:
        dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]

The reason for this is that if there exists a subset P of A[1…i - 1] such that F(P) = j then there exists also a subset of A[1…i] such that F(P) = j or if there exists a subset P of A[1…i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j, so there exists a subset P’ of A[1…i] such that F(P’) = j

At the end we have dp[n][j] for all 0 <= j <= 1023, and we can return a maximum value of dp[n][j] * (j ^ k) for all j.

Time Complexity:

The time complexity per one testcase is O(N * 1023);

AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

9 Likes
2

I have a quick question. Information that A is at most 1000 was written in problem statement from the beginning? I wrote a comment about this during the contest but it was not approved. I assumed, that A is up to 2^30, so I solved this problem almost as the last one (when I finally checked the problem statement again)…

3 Likes
3

I’ve managed to solve the problem without DP. I’ve used C++ STL’s set and maintained all possible xors in it. Since all numbers are in [0, 1000], any xor of them will lie in [0, 1023]. So, set can have at max of 1024 elements at any point of time. So the complexity should be little less than O(n * 1024 + 1024 * log(1024)) where second term is for the inserts in the worst case.

Here’s my solution: http://www.codechef.com/viewsolution/5592821

I’ve also solved this using Guassian Elimination, you can view my code here: http://www.codechef.com/viewsolution/5616381

Also, the problem does not even need a 2 Dimensional DP, it can be made simpler.
Here’s my DP solution: http://www.codechef.com/viewsolution/5616433

19 Likes
4

No, it wasn’t there in the beginning… :frowning:

3 Likes
5

I just inserted k in the array and used the solution of the problem XMAX on SPOJ which is quite similar.
Obviously that’s the wrong logic I assumed in the beginning but I got AC in all the subtasks except 4 in subtask 2.

1 Like
6

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.

7

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:

8

I thought something similar to the XMAX solution as mentioned above by @h1ashdr@gon . What i did was: divided the whole array in two subarrays, the first that doesn’t have any of the bits set as of k and the other that have atleast one bit set. In my maximum, xor of all elements in the first set has a fair chance of giving me the maximum. My task was reduced to finding the maximum of ((xor of set1^k), (xor of set2^k), (set1^set2^k). But then I got stuck in finding the maximum for set2 which is nothing but one of the subproblem of the original question(I tired many approaches though). So, it was just DP i should have thought about or any other way out in this approach??

9

“The first observation is that F§ can be at most 1023 since any input number is at most 1000”.
How can we conclude that ?

10

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.

2 Likes
11

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

12

I used Gaussian elimination to transform the input array A into the lower echelon form which is an equivalent representation of the above array (in which the array of bits [1101, 1001, 1010, 111, 11, 1] for example gets transformed to something like [1111,101, 1] – decreasing order of bits) Now it is easy to maximize the XOR value greedily. Start iterating with max = k from the left, and include the element only if the XOR value increases, else move on. Output max at the end of the iteration.

3 Likes
13

I tried doing this in the problem. This is the link:: http://math.stackexchange.com/questions/48682/maximization-with-xor-operator

This is same as what @adijo said, I believe. But, the main idea behind this approach is setting one bit of each number one and then xoring with the numbers below in the series if they have that specific bit set, just to ensure no 2 numbers have the same MSB (most significant bit) as 1.

If this is to follow, then since we were given a k, and it also had an MSB, so shouldn’t we have xored k with every element in the series which had its bit corresponding to the MSB as 1.

But, it gave me a wrong answer. :confused:

1 Like
14

@adijo i tried with the same Gaussian Elimination technique but my code failed for subtask 2…any suggestions on where i went wrong…http://www.codechef.com/viewsolution/5549953

15

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…

16

I made a recursive function for solving this.
Considering that the biggest number we can make is 1023 and in any case, we can always use an empty set to get the answer as K^0 = K, the biggest number that can be attained is 1023, and the smallest (to be checked) is K.
So the answer lies in the range from K to 1023.

To take the initial input, I made an array with size 1001, using which I could directly set array[i]=1 if i was present in the input, else the value of array[i] would be 0.
One more thing I did was to go through this array and make a new array which only holds all the elements in descending order.

Now we basically need to check for each number from 1023 to K+1, whether that number can somehow be made with the other numbers present in the set.
The most obvious(and ultimately required) case would be if the number is directly present in the set.

The basic idea is that if some number r is required, and isn’t directly present in the set, take a number say p from the set, and again call the function for finding r^p in the remaining set. This forms the basic recursion.

But that would give a TLE, so I needed some constraints.
I was using the array in decreasing order, so the first number would be the greatest, from this, one simple constraint I was able to make was that if the required number’s Most significant bit(MSB) is greater than the currently largest number’s MSB, then there is no way to make the required number.

Using all this I was able to get AC with time 0.00 in all but 1 case, which was giving TLE.
For further refinement I used the concept that, considering a certain subset of a larger set, if a certain required number could not be made using the larger set, then it can definitely not be made using this smaller subset.

With this I was finally able to get AC that one case too, with a time 0.02

Here is my solution:
http://www.codechef.com/viewsolution/5597629

2 Likes
17

nice effort, nice logic :slight_smile:

18

@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
19

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§ 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.

20

gaussian elimination for me too ! :slight_smile: got AC http://www.codechef.com/viewsolution/5505732

1 Like