I have gone through the editorials and one discussion but I am still unable to understand the DP based solution for this question. I would like to know how we have arrived at the solution and what is underlying thought process. I realize that this has been asked before, but after going through those threads I am unable to find a suitable explanation that explains DP based solution.
Thank You.
1 Like
Consider what happens when we get a new element. If we have no elements. The only choice we have is 0. Let’s add an element. For each possible value we could get with the previous elements, we can either choose to not xor it, or xor it.
Notice that the set never decreases with more elements.
So the set of values that can be created by the first i elements is
S_i=S_{i-1} \cup \{x\bigoplus A_i \forall x\in S_{i-1} \}
Base case S_0=\{0\}
Maintain all the possible values you can get and find which is the largest when xored with k later.
Implementation
We can use an array of size 2^{10}, as there is no element with the 11th bit set in the input, so nor will there be any in the possible xor values.
So dp[i][j]=1 means that j\in S_i.
Therefore dp[i][j]=dp[i-1][j]\ OR\ dp[i-1][j\bigoplus A_i]
Code
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
void solve(){
int n,k;
cin>>n>>k;
vector<vector<bool>> dp(n+1,vector<bool>((1<<10),0));
dp[0][0]=1;
for(int i=1;i<=n;i++){
int a;
cin>>a;
for(int j=0;j<(1<<10);j++){
dp[i][j]=dp[i-1][j]|dp[i-1][j^a];
}
}
int ans=-1;
for(int i=0;i<(1<<10);i++){
if(dp[n][i]){
ans=max(ans,(i^k));
}
}
cout<<ans<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
solve();
}
}
4 Likes
I am still having some difficulties understanding. If it would be convenient for you, please help me out with an example. I know it would help me a great deal!
For example - Lets assume A is - [1, 2, 3, 4]
Then P can be -
Taken NONE at a time - {0},
Taken ONE at a time - {1}, {2}, {3}, {4},
Taken TWO at a time - {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4},
Taken THREE at a time - {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4},
Taken ALL at a time - {1,2,3,4}.
Then how would you go about with your explanation.
Also, if the set was {0} and now is {1} after adding an element. How do we have a choice to xor it or not xor it ?
4 Likes
Oh, I think I see your misunderstanding. We don’t care about how many are taken at
a time.
We start with
A=[1,2,3,4]
S_0=\{0\}
S_1=\{0\} \cup\{0\bigoplus1\}=\{0,1\}
S_2=\{0,1\} \cup \{0 \bigoplus 2, 1 \bigoplus 2\}=\{0,1,2,3\}
S_3=\{0,1,2,3\}\cup\{0\bigoplus3,1\bigoplus3,2\bigoplus3,3\bigoplus3\}=\{0,1,2,3\}
S_4=\{0,1,2,3\}\cup\{0\bigoplus4,1\bigoplus4,2\bigoplus4,3\bigoplus4\}=\{0,1,2,3,4,5,6,7\}
Now answer is max(k\bigoplus x) \forall x\in S_4.
8 Likes
Yeah. I just figured it out. Your explanation and solution is really satisfying. Thank You so much.
can you guys tell me how you got this thing:-
" dp[i][j]=dp[i-1][j]|dp[i-1][j^a] "