Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

ajitesh20's blog

By ajitesh20, history, 2 years ago, In English

How to solve this question asked in google online challenge on 16th August 2020

Question

Test Cases

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

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The full brute-force solution works in $$$O((n-1)\cdot (n-3)...\cdot 3\cdot 1)$$$ which should fit in 1 seconds (at least I hope in Google's servers).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks bro!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain your approach.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are N (even) total elements which have to paired up. For each i-th element we can pair it up with a j-th element that has not yet been paired up, and pick the one that results in the maximum (or minimum) value. To represent which elements are already paired up we can use a bitmask of length N. As N <= 20, this is feasible. Notice that the order of picking pairs does not affect the answer. That is, if we pair up {1,2,3,4} as (1,2) first and then (3,4) or (3,4) first and then (1,2), the answer does not change. We can now build a brute force recursion (which we can memo later). Alternatively this can be done with bottom-up DP.

      Let's try for the maximum value that we can obtain, the only difference between this and the minimum one is we will try to pick the pair which minimizes the total value.

      We currently want to pair up position i with some unused position j. In our mask, if j-th bit is 1, then j-th position has been paired up and we cannot pick it. If j-th bit is 0, we can try to pair up our position i with position j.

      We are currently at position 'i' and have a bitmask 'mask'
      solve(i, mask):
          if i == n: // we have reached the end and cannot gain any more value
              return 0
      
          if i-th bit is 1 in our mask: // i-th position has been picked, solve for the next position
              return solve(i + 1, mask)
      
          // Now we will try pairing up the i-th position
          ans = -INF
          for j in [0, n-1] such that i != j and j-th bit is 0 in our mask:
              // pair up i and j
              // value gained is arr[i] ^ arr[j]
              // also need to set i-th and j-th bit to 1
              new_mask = mask | (1 << i) | (1 << j)
             // maximize value gained by pair (i,j) and remaining
              ans = max{ ans, arr[i]^arr[j] + solve(i + 1, new_mask) }
          return ans
      
      Initially, we are at position 0 and have an empty mask. We can call the function with solve(0,0).
      
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is the time complexity of this approach? I though this has a time complexity of (n-1)*(n-3)*...1

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks you

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is one of those questions where I think the recursive approach is better then the iterative as in every transition the number of set bits in the mask will be even. It's most likely be of complexity $$$O(2^{n/2} \times n)$$$.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They asked a question which could have been googled? Or was it added to hackerearth afterwards?

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I googled it but found nothing, so I asked here. Then I came to know that it was already present on HackerEarth

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I think we can solve it using dp[index][masks] and this easy to implement.

Second solution is hard to implement, we can build a weighted graph between index i and all other indexes the weight will be what we will gain from that (+X) or (-X), then find max flow. for minimizing we can reverse the sign of the weight (+ -> -) and vise verse. the find max flow again. i'm not sure if this works well.

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I done it with some bitmask + dp can be said

let represent every index as a bit and initially the mask = 111111..n times

This is decomposed to (n-2 times) with 2 of them processed And so on

We create dp since there are some common point in recursion tree we are not gonna solve repeatedly Check my code here

https://www.hackerearth.com/submission/72546942/