ConnectingCars SRM 645 div 2 500
Problem statement :
Janusz works in roller
coaster maintenance. The station of the roller coaster is a long straight
segment of railroad tracks. There are some cars on those tracks. The cars are
currently not attached to each other, and there may be gaps between some of
them. Janusz has to push them all together and connect them into a train.
You are given the int[]s
positions and lengths. For each valid i, there is a car that is lengths[i]
meters long and starts positions[i] meters from the beginning of the station.
(In other words, the coordinates currently occupied by this car are in the
interval from positions[i] to positions[i]+lengths[i].)
Moving a single car one
meter in either direction costs Janusz one unit of energy. Compute the smallest
total amount of energy sufficient to push all cars together. In the final
configuration the cars must be located one after another with no gaps between
them.
(Note that there is no
restriction on the movement of cars or on the final position of the train.
Janusz may push the cars in any order, and he may even push some cars by a
non-integer number of meters if he wants to.)
0)
{1, 3, 10, 20}
{2, 2, 5, 3}
Returns: 15
There are four cars. The
intervals currently occupied by the cars are (1,3), (3,5), (10,15), and (20,23).
In one optimal solution Janusz would move each of the first two cars three
meters to the right, the third car two meters to the left, and the fourth car
seven meters to the left. At the end, the cars occupy the intervals (4,6),
(6,8), (8,13), and (13,16). Total energy spent: 3+3+2+7 = 15.
Solution :
See the ranges of
position and lengths of cars are very large .
It is intuitive to sort
the cars based on their position in increasing order.
Initially I was looking
to find the first point which will be the starting point for the train of cars
and find the cost to push all cars to meet the train starting at this point.
But as one can guess there can be upto 10^9 such positions, so its a bad idea.
When I saw a few passed
solutions they had the following strategy :
If we keep position of a car fixed, what will be the cost
incurred to push the cars before it and after it such that no gap is left
between any two cars. Our answer will be the minimum of all the cost of each
car.
Below is my code to do this:
import java.util.*;import java.math.*;
import static java.lang.Math.*;
public class ConnectingCars {
public long minimizeCost(int[] pos, int[] len)
{ int l=pos.length;
for(int i=0;i<l;i++)for(int j=i+1;j<l;j++)if(pos[i]>pos[j])
{ swap(i,j,pos); swap(i,j,len); }
long ans=1L<<55;
for(int i=0;i<l;i++) {
long lt=pos[i],rt=pos[i]+(long)len[i],temp=0;
for(int j=i-1;j>=0;lt-=len[j],j--)temp+=lt-(pos[j]+len[j]);
for(int j=i+1;j<l;rt+=len[j],j++)temp+=pos[j]-rt;
ans=min(ans,temp);
}
return ans;
}
long get(long mid,int pos[],long sum[])
{ long temp=abs(pos[0]-mid);
for(int i=1;i<pos.length;i++)temp+=abs(pos[i]-(mid+sum[i-1]));
return temp;
}
void swap(int i,int j,int a[])
{
int t=a[i]; a[i]=a[j]; a[j]=t;
}
}
Now why is this solution
correct . I just tried to see what happens if out fixed point is between two
cars instead of position of a car. See the figure below
In the above figure there are 5 cars numbered 1,2,3,4, and 5 respectively.
distance between 1 and 2 = a
distance between 2 and 3 = b
distance between 3 and 4 = c
distance between 4 and 5 = d
now our cost if we fix car 3 will be :
a+b ( for car 1) + b (for car 2) + 0 (for car 3) + c (for car 4) + c+d ( for car 5)
total --> a+2b+2c+d
Now what if we fix a point at a distance dx from left of car 3 :
Out cost in this case will be :
a+b -dx( for car 1) + b-dx (for car 2) + dx (for car 3) + c +dx (for car 4) + c+dx+d ( for car 5)
total --> a+2d+2c+d+dx
so we see that in this case our total increases by dx for this configuration.
