Блог пользователя code_tycoon

can DP be applied in this problem
Автор code_tycoon, история, 3 года назад, По-английски

Here is the Problem Image : Click here

Sample Input output and constraints : CLICK here

Please specify an approach for this problem

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
← 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<c , so this method is wrong

→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← 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 года назад, # ^ |
      ← 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 года назад, # ^ |
      ← 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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why isnt this some greedy over the bits?

→ Ответить