aakarshmadhavan's blog

Help with array greedy problems
By aakarshmadhavan, history, 6 years 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

Comments Comments (5)
| Write comment?
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply