By aakarshmadhavan, history, 9 months ago, ,

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
•

 » 9 months ago, # |   +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.
•  » » 9 months ago, # ^ |   0 In this case it might be hard to do this because most of the test cases have a lot of optimal permutations.
 » 9 months ago, # | ← 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.
•  » » 9 months ago, # ^ |   +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
•  » » » 9 months ago, # ^ |   +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.
 » 9 months ago, # | ← Rev. 2 →   0 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.