KGP14A - Editorial



Editorialist: Lalit Kundu






K (<100) students(each with height A[i]) to be assigned a total of K(each pencil of height B[i]) pencils. Each student is to be assigned one pencil. You want to give a pencil to each kid in a way such that the sum of the absolute differences of the height of a kid and the length of the pencil assigned to him/her is minimized. What is the minimum sum of absolute differences that can be achieved?


Greedily, we think like which pencil should we give to the kid with smallest height: intuitively the pencil with smallest height. We can do this continuously until we have assigned pencils to all the kids.

What we have done above is equivalent to:

Sort both the arrays A and B. Now, assign pencil with height B[i] to the kid with height A[i] ie. add to answer abs(A[i]-B[i]) for each i=1 to N.


Let’s say we have an arbitrary arrangement:
kid1 → pencilp1
kid2 → pencilp2
kidN → pencilpN.

Here, kids are in increasing order, but pencils are not. So, to improve this arrangement we need to decrease the number of inversions in p1,p2 … pN.

For example if kid_7 → pencil_6 and kid_11 → pencil_4, then this is an inversion, since 7 < 11 and 6 > 4. We will change this to kid_7 → pencil_4 and kid_11 → pencil_6.

Say a1 = |kid_7 - pencil_6| + |kid_11 - pencil_4| and b1 = |kid_7 - pencil_4| + |kid_11 - pencil_6|. Prove yourselves that b1 ≤ a1. Hence, decreasing the number of inversions helps us in decreasing the answer. So, the array with 0 inversions will give optimal answer.


Editorialist’s solution