Top down dp for XORSUB problem

general
, ,
1

Can any one write top down dp solution for this problem and please also explain what are the overlaping sub problems in this problem.

2

Let’s first develop a recursive approach for the problem. The question says, we need to find subsets such the the xor result of elements of the subset and the number k should be maximized. So, basically, we need to find the subset. See, the below code:

void findMaxXor(int idx, int currXor) {
if (idx == n) {
	maxXor = max(maxXor,k^currXor);
	return;
}

// either include idx'th element or don't include
findMaxXor(idx + 1, currXor);
findMaxXor(idx+1, (currXor^a[idx]));

}

Every element has two possibilities, either include that element in the subset or don’t include it. Variable idx is an iterator for the array elements and currXor tells the current xor result. Following is the recursive tree:

           (0,0) // 0'th element and current xor is 0
          /    \
   (exc a[0])   (inc a[0])
     /             \
   (1,0)           (1,(0^a[0])) ; (after including xor becomes currXor^a[0])

… Continue with this tree, and you’ll get overlapping sub-problems which will confirm you that DP is applicable.

We can now memoize the above recursive solution in a very easy manner. Whenever you need to this, make sure the only parameters you pass in recursive calls are the ones changing. Example, I have passed only two variables idx and currXor. All other variables I need like k and n are not passed in recursive calls. This helps us to visualize the DP states, the number of which is equal to the number of changing parameters in the recursive call.
So, for above, we have two DP states. So, our DP table will be dp[i][j] which means the xor result j can be achieved from the subsets of array[0...i]. Thus, dp[i][j] = 1 tells that we can get the xor result j from the subsets of a[0…i] i.e. we find what all xor results we can get from all the subsets of array. So, let’s memoize:

int dp[101][10001];  // initialize this to -1

void findMaxXorDp ( ll idx, ll currXor ) {

if ( idx == n ) {
    dp[n-1][currXor] = 1;
    return;
}

if ( dp[idx][currXor] != -1 )  // if it is not -1, then it means, we have faced this subproblem before also, so we'll not proceed with this.
    return;
    
dp[idx][currXor] = 1;  // mark this as 1 to show that from the subsets of a[0..idx], we can get currXor as the xor result

findMaxXorDp(idx+1,currXor);  // don't include this idx'th element
findMaxXorDp(idx+1, (currXor^a[idx])); // include this idx'th element

}

ll res = 0;
for ( ll i=0; i<=1024; i++ ) {
	if ( dp[n-1][i] != -1 )
	    res = max(res,(i^k));
}

Next, we find the maximum xor result as we have all possible xor results we can get from the subsets of a[0…n].

Hope this clears.
Feel free to ask any doubts.