RandomFlights
TCO14 Round 3A · 2014-03-26 · by rng_58
Problem Statement
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.
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'.
{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
Submissions are judged against all 264 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomFlights with a public method double expectedDistance(vector<int> x, vector<int> y, vector<string> flight) · 264 test cases · 2 s / 256 MB per case