aakarshmadhavan's blog

By aakarshmadhavan, history, 5 weeks ago, In English,

I would be very grateful if someone can help me out here:

Given two arrays `A` and `B` of equal length, the advantage of `A` with respect to `B` is the number of indices `i` for which `A[i] > B[i]`.

Return any permutation of `A` that maximizes its advantage with respect to `B`.

Length of `A` can be upto `10000`

Input: `A = [12,24,8,32], B = [13,25,32,11]`
Output: `[24,32,8,12]`

I want to learn how to do problems like this so I am trying to go step-by-step with the Greedy method.

1Q) Find the greedy strategy

1A) I am struggling very deeply here, I am unable to find a greedy strategy that might work. Can anyone give some idea and motivation here?

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

A good starting point is to write a brute force algorithm to permute your array A and compute the max advantage. Once you have tried enough tests, you might be able to observe a pattern from there.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this case it might be hard to do this because most of the test cases have a lot of optimal permutations.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

Firstly, you should order A and B in descending order. Keep two pointers relative to A such that L starts off at the biggest element of A and R at the lowest element of A. After that, iterate over B. If A[L] > B[i], you should pair up these elements in the final permutation. Otherwise, pair up A[R] and B[i]. Don't forget to add 1 to L or subtract 1 from R after each step, depending on which of the elements of A you decided to use.

This will always generate the optimal answer because if the biggest element of A is bigger than the biggest of B, it makes sense to pair these such elements up. However, if no element of A is bigger than the biggest element of B, you should just use your lowest element, so that you won't "waste" your bigger elements.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks!

    Can you explain this part: "However, if no element of A is bigger than the biggest element of B, you should just use your lowest element, so that you won't "waste" your bigger elements." ?

    I don't understand how you came up with this or why its true.

    Thanks

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If the biggest element from B (I'll call it K from now on) is larger or equal to any of the elements in A, no matter what element from A you pair K up with it won't increment to your final answer. Therefore, you should pair K up with the smallest element remaining from A so that you can complete the rest of the array in a more efficient manner.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

From greedy, you might have guessed that you have to use your A[i]'s wisely. What I mean from 'wisely', is that you shouldn't waste your large elements on indexes where it can be managed by a smaller element than that you used it.

So, in my opinion, you should sort the array A, and starting from B[0], you should binary search the suitable element which is just greater than current B[i]. If there is no such element left in A, then put the smallest not used element of A on that position, because, if you use any other element on that place, then there will be the chances that you may get short of that element in a later stage.

Hope you've got that as per my explanation.