RandomRoadBuilding | Topcoder Archive

Problem Statement

Absurdistan is a country with several cities. Some pairs of cities are currently connected by bidirectional roads. Whenever a road is built in Absurdistan, the workers build bridges where necessary to make sure that no two roads intersect outside the cities. The current road network was built using this rule.

As one would expect, the road building process in Absurdistan is really absurd. Each year the Grand Visier randomly picks a pair of distinct cities, and then flips a biased coin. If the coin ends up heads, the workers will build a new road between the chosen two cities (even if multiple such roads exist already). If the coin ends up tails, the workers will destroy all roads that directly connect the chosen two cities.

The coin is biased in such a way that it is more likely that a new road will be built. Building a road or destroying the existing roads always takes the workers exactly one year. The entire process will terminate as soon as the road network connects all cities in the country.

You will be given a String[] countryMap containing the current map of Absurdistan, and a double buildProbability giving the probability that the biased coin ends up heads. The j-th character of the i-th element of countryMap is a digit representing the current number of roads connecting the i-th and the j-th city.

Return the expected number of years the process will take.

Definition

Class:: RandomRoadBuilding
Method:: expectedTime
Parameters:: String[], double
Returns:: double
Method signature:: double expectedTime(String[] countryMap, double buildProbability)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

countryMap will contain between 1 and 7 elements, inclusive.
Each element in countryMap will contain the same number of characters as the number of elements in countryMap.
Each character in each element of countryMap will be a digit ('0'-'9').
The i-th character of the i-th element of countryMap will be '0' for all i.
The i-th character of the j-th element of countryMap will be equal to the j-th character of the i-th element for all pairs of i and j.
buildProbability will be between 0.51 and 1, inclusive.

Examples

```
{"00","00"}
```
```
1.0
```
```
Returns: 1.0
```
In the first year the workers connect the two cities and we are done.
```
{"00","00"}
```
```
0.75
```
```
Returns: 1.3333333333333333
```
This time it is possible that the coin flip will end up tails, and thus the expected time increases.

{"0301","3007","0002","1720"}

0.757

Returns: 0.0

This road network is already connected.

```
{"000","000","000"}
```
```
1.0
```
```
Returns: 2.5
```
In the first year we will connect two of the cities. In the next year, it is possible (with probability 1/3) that we'll pick the same two cities. Therefore the expected time is longer than two years.
```
{"010","100","000"}
```
```
0.75
```
```
Returns: 2.2222222222222223
```
Even though we already have one road, we can still lose it, if we are unlucky.

{"010200","100000","000000","200000","000000","000000"}

0.6

Returns: 10.69738458056897

Already for six cities the process can take quite a long time.

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.