RandomFlights | Topcoder Archive

Problem Statement

There are N airports numbered 0 through N-1. Airport 0 is called the central airport. The coordinates of the airport i is (x[i], y[i]). You are given a String[] flight. If the j-th (0-based) character of the i-th element of flight is '1', there is a direct flight between the airport i and the airport j. Otherwise there is no direct flight between the airport i and the airport j. Note that direct flights are bidirectional (in other words, flight is symmetric). There are no flights that start and end at the same airport.

We say that airport Y is reachable from airport X if there is a sequence of zero or more consecutive flights that gets us from X to Y. Notably, any airport is always reachable from itself. Currently, some airports may be unreachable from the central airport. Cat Snuke decided to fix this by performing the following process:

If all airports are reachable from the central airport, end the process.
Choose an airport that is reachable from the central airport uniformly at random. Let's call this airport A.
Choose an airport that is not reachable from the central airport uniformly at random. Let's call this airport B.
Add a bidirectional direct flight between A and B, and go to step 1.

After the process ends, Cat Snuke computes the length of the shortest path between airports 0 and 1. The length of a path is defined as the sum of lengths of all direct flights used in the path. The length of a direct flight is defined as the Euclidean distance between the two airports it connects. Return the expected length of the shortest path between airports 0 and 1.

Definition

Class:: RandomFlights
Method:: expectedDistance
Parameters:: int[], int[], String[]
Returns:: double
Method signature:: double expectedDistance(int[] x, int[] y, String[] flight)
(be sure your method is public)

Constraints

N will be between 2 and 18, inclusive.
x and y will contain exactly N elements each.
Each element of x and y will be between 0 and 1000, inclusive.
No two airports are at exactly the same position.
flight will contain exactly N elements.
Each element of flight will contain exactly N characters.
Each character in flight will be either '0' or '1'.
flight will be symmetric according to the main diagonal.
For each valid i, the i-th character of the i-th element of flight will be '0'.

Examples

```
{7, 10, 9}
```
```
{1, 3, 3}
```
```
{"000",
 "001",
 "010"}
```
```
Returns: 3.7169892001050897
```
Initially there is only one direct flight: between airports 1 and 2. If Snuke adds a direct flight between 0 and 1, the length of the shortest path will be sqrt(13). If Snuke adds a direct flight between 0 and 2, the length of the shortest path will be sqrt(8) + 1. Both cases are equally likely, so the expected length is (sqrt(13) + sqrt(8) + 1) / 2 = 3.716...
```
{4, 1, 5, 6, 6}
```
```
{1, 5, 10, 3, 4}
```
```
{"00110",
 "00101",
 "11000",
 "10001",
 "01010"}
```
```
Returns: 8.927446638338974
```
All airpots are already reachable from the central airport, so no new direct flights will be added. There are two paths from airport 0 to airport 1: 0 -> 2 -> 1 (length: 15.458...) and 0 -> 3 -> 4 -> 1 (length: 8.927...). You should return the length of the shortest path.

{7, 10, 9, 7, 7}

{1, 3, 3, 6, 4}

{"00001",
 "00000",
 "00010",
 "00100",
 "10000"}

Returns: 6.2360162308285005

{97, 27, 20, 34, 30, 37, 65, 21, 74, 27, 84, 79, 15, 78, 16, 7, 11, 24}

{1, 72, 20, 73, 58, 55, 45, 19, 48, 4, 33, 22, 25, 95, 100, 85, 65, 53}

{"000000000000000100",
 "001010000001000000",
 "010010000000000000",
 "000000000000100001",
 "011000000001000000",
 "000000001000000010",
 "000000000000010000",
 "000000000000000100",
 "000001000100001010",
 "000000001000000010",
 "000000000000100000",
 "010010000000000000",
 "000100000010000001",
 "000000100000000000",
 "000000001000000010",
 "100000010000000000",
 "000001001100001000",
 "000100000000100000"}

Returns: 255.25627726422454

{35, 8, 71, 81, 43, 76, 55, 15, 72, 39, 99, 23, 14, 77, 47, 43, 60, 67}

{68, 96, 98, 16, 7, 74, 52, 63, 98, 77, 52, 93, 52, 4, 56, 11, 75, 63}

{"000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000",
 "000000000000000000"}

Returns: 138.0804889521365

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.