Editorialist: Akash Sharma
Prerequisite:
Basic Logical Math
Problem Description:
You are given 2 arrays representing the distance of N people from 2 camps namely X and Y. You have to minimize the distance travelled by N people altogether. Following some restrictions on the number of persons the 2 camps, X and Y can accommodate.
Explanation:
As we have to minimize the distance travelled by all N people. We will send every person according to the difference of the distances between 2 camps.
Remember every problem can be done in many ways one such way is described below:
Approach Explained:
We have to choose a camp between X and Y for every person. Let us suppose that the distance from X is less than the distance from Y. If we go to Y, then we are travelling an extra distance of
(Distance from Y - Distance from X). the more this expression is the more extra distance we travell (If the distance of Y is < distance of X).
If the case would be the distance of Y is > distance of X, then the value of
(Distance from X - Distance from Y) will give us the extra distance travelled.
So we have to minimize these expressions.
Summation of extra distance for all N persons.
ExtraDistance={ (Distance from X - Distance from Y), if(Distance from Y<Distance from X)
(Distance from Y - Distance from X), if(Distance from Y>Distance from X)
}
We have to minimize the summation of this expression.
So it would be logical if we choose the person incurring maximum extra distance and then assigning that person to the camp with smaller distance (if possible means limit of the camp is not reached).
This last step should be repeated for all persons.
Steps:
Calculate the array of difference
Difference =Adist [ ] - Bdist [ ]
Now choose the maximum absolute number from the difference array. Consider the meaning of Absolute as a number without its sign(+/-).
If there are many choose anyone.
Example if |3|=|-3|=3 choose any one of them.
Now if the chosen number is negative ( means Bdist > Adist ),
Then the person should go to X, if X is already full then It will go to Y.
Now if the chosen number is positive ( means Bdist < Adist ),
Then the person should go to Y, if Y is already full then It will go to X.
Add the distance of the corresponding camp in the answer.
Repeat step 3 until all N people are assigned to some camp.
Explained Example:
N = 4, X = 2, Y = 2
Adist=[10, 23, 15, 5]
Bdist=[12, 20, 8, 20]
The initial state of difference array
Difference array = [-2, 3, 7, -15]
Location array = [., ., ., .]
(Here: location array maps the person to its preferred camp).
state of difference array
Difference array = [-2, 3, 7, -15]
Location array = [., ., ., X]
Answer=5
(Here: maximum is 15 and it is negative so it should go to X).
(Bold represents assigned person).
state of difference array
Difference array = [-2, 3, 7, -15]
Location array = [., ., Y, X]
Answer=5+8
(Here: maximum is 7 and it is positive so it should go to Y).
state of difference array
Difference array = [-2, 3, 7, -15]
Location array = [., Y, Y, X]
Answer=5+8+20
(Here: maximum is 3 and it is positive so it should go to Y).
(Here: limit of Y is reached now all people will be assigned to X).
state of difference array
Difference array = [-2, 3, 7, -15]
Location array = [X, Y, Y, X]
Answer=5+8+20+10
(Here: limit of Y is reached now all people will be assigned to X).
Answer = 5+8+20+10 = 43.