Problem Statement |
| | The Kingdom of Byteland has a big capital city that is the center of its industry and social life. To connect every city to the capital, the King decided to develop a network of roads. Each city, except for the capital, was responsible for building a single bidirectional road from itself to another city. For each city X, the following algorithm was used to determine the destination of the road built by that city:
- Measure the Euclidean distances from all the cities to the capital, and consider only those which are strictly closer to the capital than city X (include the capital in that list).
- If there is more than 1 city, pick the city which is closest to city X.
- If there are multiple such cities, pick the city among them with the smallest X coordinate.
- If there are still multiple such cities, pick the city among them with the smallest Y coordinate.
After all the roads were built, some people started to complain that they had to go through too many other cities to get to the capital. The King decided to construct teleportCount teleports to solve this problem. Each teleport would provide an instant connection between the city where it is placed and the capital.
Let's define the inconvenience of a city as the minimal number of roads one needs to follow to get from that city to the capital, or to a city with a teleport. For example, the inconvenience of the capital, and of all cities with teleports, is 0. The inconvenience of a city that doesn't have a teleport but is directly connected to the capital or to a city with a teleport is 1, and so on. Note that the shortest route from a city to the capital may involve traveling further away from the capital to reach a teleport.
The inconvenience of the whole Kingdom is the maximum inconvenience among its cities.
You are given int[]s citiesX and citiesY, where (citiesX[i], citiesY[i]) are the coordinates of the i-th city.The 0-th city is the capital. Distribute teleportCount teleports in such a way that minimizes the inconvenience of the Kingdom and return that minimum inconvenience value. |
| |
Definition |
| | | Class: | TeleportsNetwork | | Method: | distribute | | Parameters: | int, int[], int[] | | Returns: | int | | Method signature: | int distribute(int teleportCount, int[] citiesX, int[] citiesY) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The algorithm described in the problem statement guarantees that all the cities will be connected to the capital. |
| |
Constraints |
| - | citiesX will contain between 1 and 50 elements, inclusive. |
| - | teleportCount will be between 0 and 4, inclusive and less than the number of elements in citiesX. |
| - | Each element of citiesX will be between 0 and 1000000, inclusive. |
| - | citiesY will contain the same number of elements as citiesX. |
| - | Each element of citiesY will be between 0 and 1000000, inclusive. |
| - | No two cities will occupy the same point. |
| |
Examples |
| 0) | |
| | 2 | {0,1,1,1,2,2} | {1,0,1,2,0,2} |
| Returns: 1 | The network of roads will look like this:
3--5
|
0--2
|
1--4If we place teleports in cities 1 and 3, no city would have an inconvenience greater than 1. |
|
|
| 1) | |
| | 1 | {0,1,1,1,2,2} | {1,0,1,2,0,2} |
| Returns: 2 | | The cities are located in the same places as in the previous example, but now there is only one teleport. It's best to place it in city 2. |
|
|
| 2) | |
| | 0 | {0,1,1,1,2,3,3,4} | {1,1,2,0,0,0,2,1} |
| Returns: 5 |
2-----6
|
0--1 7
| /
3--4--5Cities 5 and 6 have the same distance to 7 and the same X coordinate, but 5 has a lower Y coordinate and that's why the road was built from 7 to 5. |
|
|
| 3) | |
| | | Returns: 1 | 0--1--2--3--4 The best solution is to place the teleport in city 3. |
|
|
| 4) | |
| | 4 | {64,200,384,294,175,107,303,374,224,220,223,99,442} | {79,161,83,281,344,217,184,336,431,262,75,474,257} |
| Returns: 1 | |
|