Power grid districts
A region’s power system is divided into k districts, each with its own substation and its own repair crew. So that a failure in one district does not spread to a neighbouring one, the districts are to be set as far apart as possible: the gap of a division is the smallest distance between two villages from different districts, and it must be as large as possible. Each village is in exactly one district, there are exactly k districts, and none is empty. Find the largest gap and the sizes of the districts in such a division.
Two tests are the real 675 towns and villages of the South Moravian Region from the GeoNames gazetteer on a plane, in metres; one splits the region into 10 districts, the other into 80.
Input
The first line holds n and k (2 ≤ k ≤ n ≤ 1000), the number of villages and districts. Then n lines with the coordinates of the villages x and y, integers with |x|, |y| ≤ 10⁶. All villages are at different points. It is guaranteed that the division with the largest gap is unique.
Output
The first line holds the largest gap with three digits after the point (the answer is accepted with a relative error of 10⁻⁶). The second, the sizes of the k districts of this division separated by spaces, in non-increasing order.
Examples
Example 1
7 3 0 0 3 1 1 4 20 2 24 5 21 9 9 30
17.029 3 3 1
Example 2
5 2 0 0 10 0 21 0 33 0 46 0
13.000 4 1
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 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
Imagine connecting villages one wire at a time, starting from the closest pairs, like Kruskal, and keeping track of the number of pieces. What can be said about the gap when there are exactly k pieces?
2Hint 2
The gap of a division into Kruskal’s pieces is the next wire Kruskal would lay. Why nothing is better: take any other division and two points that are in one piece for Kruskal and in different ones there.
3The idea
Build the minimum spanning tree and cut its k − 1 longest wires. The pieces are the districts, and the gap equals the shortest of the wires cut. This is the best division: any other has two villages that are in one district for us and in different ones there; the path between them along the spanning tree consists of wires no longer than our gap, and somewhere along this path it passes from district to district, so the other division’s gap is no larger.
4Walkthrough
The graph is complete: wires are possible between any two villages, up to half a million of them. Sorting them all is possible, but Prim’s algorithm without a heap is simpler and faster: an array “the shortest wire from the network to a village”, at each step the village with the smallest value, after it a recomputation of the values for the rest. That is O(n²) in all. It is convenient to keep distances squared: the coordinates are integers, so are their squares, comparisons are exact, and the square root is needed once, when printing.
Then sort the n − 1 wires of the spanning tree and merge the ends of all but the last k − 1 in a disjoint-set union. The sizes of the sets are the sizes of the districts. The uniqueness condition means that the shortest wire cut is strictly longer than the longest one kept; otherwise another wire of the same length could be cut, giving other districts with the same gap.
On real Moravia the answer is instructive: the ten “districts” are one huge one, 23 villages near Veselí nad Moravou and eight loners, among them Brno and Břeclav. Single linkage cuts where the gap is, and in this data the large cities have the largest gaps: their city districts are not in the gazetteer.
4+Solution
5Complexity
O(n²) for the spanning tree, O(n log n) for sorting its wires. Kruskal over all pairs is O(n² log n), which also fits but is slower.
6Common mistakes
- The last wire laid instead of the next. If you build with Kruskal down to k pieces and print the length of the last wire taken, you get the longest wire inside a district, not the distance between districts. In the second example that is 12 instead of 13.
- Cutting k wires instead of k − 1. Each cut adds one piece, and we started with one.
- The root in comparisons. Distances can be compared in floating point, but integer squares are more precise and simpler: with equal distances the roots may differ in the last bit.