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

Автор aakarshmadhavan, история, 6 лет назад, По-английски

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?

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

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

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.

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

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

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

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.