A depot on a street grid
In a city the streets form a regular grid, west to east and south to north, so a car’s path from point (x1, y1) to point (x2, y2) is |x1 − x2| + |y1 − y2|. A chain of n shops is building a shared depot. Every day wi cars leave the depot for shop i at point (xi, yi). The depot can be placed at any point with integer coordinates, even at the same point as a shop. Find the smallest possible total path of all the cars in a day: Σ wi · (|x − xi| + |y − yi|).
One of the hidden tests is real: 675 settlements of one region from GeoNames data on a grid with a 100 m step, with the number of inhabitants as wi.
Input
The first line holds n (1 ≤ n ≤ 100,000). Then n lines of three integers each: xi, yi (|xi|, |yi| ≤ 106) and wi (1 ≤ wi ≤ 106). Shops may stand at the same point.
Output
One number: the smallest total path.
Examples
Example 1
3 0 0 1 4 0 1 10 6 1
16
Example 2
4 0 0 3 2 1 1 9 9 1 10 10 1
41
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The sum |x − xi| + |y − yi| splits into two: one depends only on x, the other only on y. So it is enough to solve the problem on a line: where to put a point so that the sum of weighted distances to points on the line is smallest?
2Hint 2
Move the depot one unit to the right along the line. How does the sum change? All the cars that drove left will drive one unit more, and all that drove right one unit less.
3The idea
Let the shops to the left of the depot (and at it) have total weight L, and those to the right weight R. A step to the right changes the sum by L − R: while more than half the weight is on the right, going right pays; once at least half has gathered on the left, it no longer does. The optimum is where the weight accumulated from the left first reaches half the total. This is the weighted median, the ordinary median if all weights are equal.
The centre of mass, the weighted mean, does not work here: it minimises the sum of squared distances, not of the distances themselves. One distant shop with a large weight pulls the mean towards itself, but moves the median no further than the neighbouring shop.
4Walkthrough
For each axis separately: sort the points by coordinate, walk left to right with the accumulated weight, and stop at the first point where twice the accumulated weight is at least the total. The coordinate of this point is the optimal coordinate of the depot. If the accumulated weight is exactly half, any point up to the next shop is optimal, since the sum is the same along that whole segment, so the answer does not depend on the choice. It remains to add up the weighted distances.
Sorting is not required. Quickselect finds the weighted median too: partition the points around a pivot, add up the weights of the left part, and go where half the total weight lies, O(n) on average. On 100,000 points there is no visible difference, but on billions of records in analytics medians are found exactly this way, or approximately.
In the first example the three shops have equal weights, and the depot goes to the median on each axis: x = 4, y = 0, the path is 16. The centre of mass (4.67, 2), rounded, would give 19.
4+Solution
5Complexity
Sorting the two axes is O(n log n), with quickselect O(n) on average. The sum reaches 105 · 106 · 4 · 106 = 4 · 1017 and fits in a 64-bit integer; in Python integers are unbounded anyway.
6Common mistakes
- The centre of mass. The most common head-on solution: the weighted mean of the coordinates. It minimises the wrong sum. The test with one distant shop with a million cars shows the difference most vividly.
- A median without weights. The median of the shop coordinates, with each shop counted once, is correct only for equal weights.
- A median by distance to the centre. The grid problem splits by axes; looking for the “central” shop by Euclidean distance is a different problem.