### code_tycoon's blog

By code_tycoon, history, 3 months ago,  Comments (9)
 » 3 months ago, # | ← Rev. 2 →   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 →   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 →   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.