ConnectingCars
SRM 645 · 2014-12-30 · by w10d
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
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.)
Notes
- You may assume that the optimal answer is always an integer that fits into a signed 64-bit integer data type.
Constraints
- lengths and positions will have the same number of elements.
- lengths will have between 2 and 50 elements, inclusive.
- Each element of lengths and positions will be between 1 and 10^9, inclusive.
- The segments occupied by the cars may touch but they will not overlap.
{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.
{100, 50, 1}
{10, 2, 1}
Returns: 96
There are three cars. The gaps between consecutive cars have 48 meters each. The best solution is to keep the middle car in place and to push the other two towards it. This requires 48+48 = 96 units of energy.
{4, 10, 100, 13, 80}
{5, 3, 42, 40, 9}
Returns: 66
{5606451, 63581020, 81615191, 190991272, 352848147, 413795385, 468408016, 615921162, 760622952, 791438427}
{42643329, 9909484, 58137134, 99547272, 39849232, 15146704, 144630245, 604149, 15591965, 107856540}
Returns: 1009957100
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,1000000000}
{1,1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000000000}
Returns: 999999980
killing brute force
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,900000001,900000002,900000003,900000004,900000005, 900000006, 900000007, 900000008, 900000009, 900000010, 900000011, 900000012, 900000013, 900000014, 900000015, 900000016, 900000017, 900000018, 900000019, 900000020, 900000021, 900000022, 900000023, 900000024, 900000025}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1000000000}
Returns: 21599999424
requires long type
Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConnectingCars with a public method long long minimizeCost(vector<int> positions, vector<int> lengths) · 67 test cases · 2 s / 256 MB per case