Valentine Magic - DP, why sort the array?

#1

Why are we sorting the arrays ? Please explain in detail

#2

Hi. I’ll try my best to explain this to you.
So 1st lets consider a brute force solution.There are M girls with g1,g2…,gm candies and n boys with b1,b2…,bn chocolates. We can simply check all possible assignments of boys to girls. The 1st boy has m girls available, 2nd boy has m-1 girls available and last boy has m - n + 1 girls available. So the total possible assignments are X = m*(m-1)(m-2)…(m-n+1). so whichever of these X assignments has the minimum sum of abs(bi - gj) is our answer.

Now consider the best possible assignment of all boys to N girls will have the following N girls :
gi1, gi2, gi3, … gin. now think to minimize the absolute differences of candies and chocolates of a couple. Which boy will you assign to the girl with the largest amount of candies?

Take an example :
boys : 10, 5, 8, 6, 12
girls : 1, 8, 5, 12, 9, 16, 13
Now let us say I randomly pick 5 girls out of the above 7 girls to pair with 5 boys and they are:
1, 5, 9, 16, 13
Now you have 5 girls and 5 boys. All we need is an assignment that gives minimum sum of abs arrangements for these 5 selected girls.
which boy would you like to pair the girl with 16 candies to? To me it feels intuitive that I will pair her with the boy having 12 candies as abs(16 - 12) = 4 which will lead to a better ans than if I had paired her with someone else. So out of all 5! possible arrangements, the best arrangement will the one in which girl with most candies is paired with boy with most chocolates and so on.

This is just exactly what sorting does in the DP solution.
we first sort the candies and chocolates. if the boy with most candies is assigned to the kth girl(in sorted order) then all other boys will be assigned to girls in the range 1 to k - 1th.

Short explanation : if you had n boys and n girls you will always assign them in order of increasing candies and chocolates otherwise answer will not be minimum. The image below tries to prove this for 2 boys and 2 girls in which boy with lesser chocolate is assigned to girl with lesser candies which leads to an optimal solution. If you understand this it will be easy to prove for n boys and n girls as well.

15%20AM
15%20AM960×1280 110 KB

I hope you find this helpful :slight_smile:

2 Likes
#3

Thank you so much…!

1 Like
#4

Will there is any test case where "we have to reject lot of girls and no girls is availiable for the boys

if(j==m)
{
return INT_MAX;
}

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

how can i choose n girls out of m