### code_tycoon's blog

By code_tycoon, history, 3 months ago,

Please specify an approach for this problem

• -12

 » 3 months ago, # |   0 Auto comment: topic has been updated by code_tycoon (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 I guess dp can be applied , the states are $i$ and $j$ where $i$ is the index till where we have considered the input array and j is the number of elements in the current subset. The transitions are $dp[i+1][j]=std::max(dp[i+1][j],dp[i+1][j])$ (You are not adding the i'th element to the xor subset) and $dp[i+1][j]=std::max( dp[i][j]$ ^ $ar[i] , dp[i+1][j] )$ (meaning you are considering adding the element to the subset )The final answer would be the highest value in the last row and in the first $n/2$ numbers. Edit: won't work because a^b > c^b even if a
•  » » 3 months ago, # ^ | ← Rev. 4 →   +1 apply reverse dp, minimum size subset with xor = j considering i elements transition will be like $dp(i,j) = min(dp(i,j) , dp(i-1,j \oplus a_i) + 1)$ total complexity will be $N * 2^{20}$ I guess this can also be solved using linear basis(gaussian elimination), but i am not sure how, if someone could explain me that would be great.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Don't know about gaussian elimination although there is also another method to solve this problem using vector addition on xor (reference here )It will allow us to solve in around $10^6$ iterations.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 But how will you calculate maximum xor using the size of the subset which you are storing into the DP array ? the problem is to calculate maximum xor possible using atmost n/2 elements from the array not to find the minimum number of elements to form xor of n/2 ... kindly correct me if I am wrong navneet.h
 » 3 months ago, # |   +1 Ya, i think it is some kind of variation of knapsack dp because we can either choose the element or not choose .
 » 3 months ago, # |   0 This problem was already asked here today. And a few more times earlier this week.
 » 3 months ago, # |   0 why isnt this some greedy over the bits?
 » 3 months ago, # |   0 Yes, definitely it is solvable through dp