code_tycoon's blog

can DP be applied in this problem
By code_tycoon, history, 3 years ago, In English

Here is the Problem Image : Click here

Sample Input output and constraints : CLICK here

Please specify an approach for this problem

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by code_tycoon (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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<c , so this method is wrong

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Ya, i think it is some kind of variation of knapsack dp because we can either choose the element or not choose .

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem was already asked here today. And a few more times earlier this week.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why isnt this some greedy over the bits?

→ Reply