ConnectCountry | Topcoder Archive

Problem Statement

In Absurdistan there are n towns, numbered from 1 to n. From time to time, the Grand Vizier of Absurdistan sends a new order for a road to be built between two given towns. Sadly, all the road workers in the country are illiterate. Thus they just randomly pick two different towns a and b and build a bidirectional road between them (even when those towns are already connected by several roads). The roads are built in such a manner that the only points where a traveler can enter or leave it are the towns it connects. The road administration has resources to build exactly one road per year.

You are given n and a list of roads that have already been built: the int[]s X and Y such that for each valid i there is a road that connects towns X[i] and Y[i]. Return the expected number of additional years it will take in order to connect all the cities in Absurdistan.

Definition

Class:: ConnectCountry
Method:: expectedYears
Parameters:: int, int[], int[]
Returns:: double
Method signature:: double expectedYears(int n, int[] X, int[] Y)
(be sure your method is public)

Notes

Your return value must have an absolute or a relative error at most 1e-9.
In the current country, as described by X and Y, there can already be pairs of towns that are connected by more than one direct road.

Constraints

n will be between 2 and 35, inclusive.
X will have between 0 and 500 elements, inclusive.
Y will have the same number of elements as X.
Each element of X will be between 1 and n, inclusive.
Each element of Y will be between 1 and n, inclusive.
For each valid i, X[i] will not be equal to Y[i].

Examples

```
2
```
```
{1, 1, 2}
```
```
{2, 2, 1}
```
```
Returns: 0.0
```
The country is already connected: there are two towns and there are already three direct roads connecting them.
```
3
```
```
{1, 2}
```
```
{3, 3}
```
```
Returns: 0.0
```
This country is also connected. Note that we can travel from 1 to 2 via 3.
```
4
```
```
{1, 3}
```
```
{2, 4}
```
```
Returns: 1.5
```
The country currently consists of two connected regions: towns 1+2 and towns 3+4. Each year, the probability that a new road is built between these two regions is 2/3, and as soon as that happens the country will be connected. It can be shown that the expected number of years is therefore 3/2.

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.