KGP14A - Editorial

PROBLEM LINK:

Practice
Contest

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.

SOLUTIONS:

Editorialist’s solution