XORSUB - Editorial

Gaussian Elimination can easily handle larger inputs. It solves the problem in N*(log(max(A_i)))^2

I tried what is mentioned in editorial but couldnā€™t pass all test caseā€¦just a few bigger ones
Hereā€™s mysubmission

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

Explanation for the above logic:
XOR has this property to toggle
Lets say,
encoded = 5 ^ 6
then, encoded ^ 5 = 6 and encoded ^ 6 = 5

In other words, we are encoding the difference of two numbers using XOR. When we XOR with one number used for encoding we get another number that was used.

We want to know if F(P) ^ a[i] = j  , where F(P) is the XOR of subset P of A[1..i - 1]
or written in reverse j = F(p) ^ a[i] 
which is of the form encoded = 5 ^ 6
To get F(p) using encoded value j and a[i], we do j ^ a[i]
3 Likes

what dp*[j] := 1 stands for in this editorial can any one answer me asap

Consider, K is 16 (10000 in binary) and there are three array elements 12, 14 and 3 (01100, 01110 and 00011). So what your program would do is select 14 as it gives the maximum xor with 16 (16^14 = 30). Picking more element(s) from the array will reduce the xor value and thus your program will terminate.

But a better answer can be achieved if you choose 12 & 3. The xor value with K (16) is 31. So this problem doesnā€™t have a greedy approach.

Hope this helps :slight_smile:

Whatā€™s the meaning of * in dp*, array* etcā€¦

brilliant

Hey!
I am having trouble with this particular type of DP. Could you please share some problems with similar DP pattern so that I can get a better view of this approach.
One of such problem I recently came across is this
Thanks

I struggled a lot in order to understand this solutionā€¦
so i am explaining , what i have gotā€¦
First we have to know some xor properties likeā€¦
if a^b=c then a^c=b and c^b=a :
bcoz it toggles 1ā€™s which are present in both (a^a^b=b)
this for understanding this line FĀ§ = j ^ a[i], then FĀ§ ^ a[i] = j;

Now If we talk about aforementioned solution then,
we are creating a two dimensional array of appropriate size then having either 0 or 1 depending upon whether the possible_xor is present or not (Note columns of matrix represent possible xor values which in this question cannot be greater than 1024)
Now we iterate every possible xor for every element A[i]
we make a dp[ i ][ j ]=1 if:
1: ( dp[ i-1 ][ j ]==1) means without taking A[ i ] into consideration the possible xor is 1 ( the xor is already possible without including A[i] in subset. )
2: if we do Xor of A[i] and current_possible_xor ( j ) and this new xor is already present{ dp[i-1] [ j^A[ i ] ]==1 }
Now to understand this properly two cases:
if the assumed xor contains A[i] ( which we donā€™t know) then by taking Xor of j with A[i] removes the element from the subset having this xor .Now if new xor is already present then this xor is also possible.
if the assumed xor not contains A[i] ( which we donā€™t know) then by taking Xor of j with A[i] adds the element to the subset having this xor .Now if new xor is already present then this xor is also possible.
3: Both 1 and 2.

1 Like

Hello Coders,

I am new to competitive programming and I am trying to learn DP and I came across this question. I have read the editorial but I am not able to get it.

Can anyone please let me know what are the prerequisites to this question and from where can I learn them.

Thanks in advance!!

Hey guys, just wanted to know why canā€™t I use only bit masking approach to solve this question.
Hereā€™s a link to my code,I guess constraint might be the issue. but still help would be appreciated.
https://www.codechef.com/viewsolution/34667877
Thanks in advanced.

you can refer to codencode youtube channel ,it has decent dp tutorials.

	FastScanner sc = new FastScanner();
	int t = sc.nextInt();
	first: while (t-- != 0) {

		int n = sc.nextInt(),k = sc.nextInt();
		int arr[] = sc.readArray(n);
		int dp[][] = new int[n+1][1024];
		
		dp[0][0] = 1;
		for(int i=1; i<=n; i++) {
			for(int j=0; j<1024; j++) {
				dp[i][j] = dp[i-1][j] | dp[i - 1][j ^ arr[i-1]];
			}
		}
		int max = Integer.MIN_VALUE;
		for(int j=0; j<1024; j++) {
    //				System.out.println(dp[n][j]);
			max = max(max,dp[n][j]*(j^k));
		}
		      System.out.println(max);

	}

Thanks, this was helpful.