PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
CAKEWALK
PRE-REQUISITES:
GREEDY, SORTING
PROBLEM:
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?
EXPLANATION:
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.
Proof:
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.