TopCoder problem "RoadsOfKingdom" used in SRM 425 (Division I Level Three)



Problem Statement

    

Long long ago, there was a kingdom named Kingdom C. There were n cities in Kingdom C, and every pair of cities was connected by a two-way road. Unfortunately, some of those roads may have been destroyed in a heavy rain.

You are given a String[] roads. The probability that the road connecting city i and city j is still available after the heavy rain is d/8, where d is the j-th digit of the i-th element of roads.

The king of Kingdom C is very sad, and he wants to know the probability of the following scenario: Every city is reachable from the capital (city 0), but if you were to destroy any one of the remaining roads, there would be at least one city that is not reachable from the capital. Return the probability of this scenario as a double.

 

Definition

    
Class:RoadsOfKingdom
Method:getProbability
Parameters:String[]
Returns:double
Method signature:double getProbability(String[] roads)
(be sure your method is public)
    
 

Notes

-Your return must have relative or absolute error less than 1E-9.
 

Constraints

-roads will contain exactly n elements, where n is between 2 and 16, inclusive.
-Each element of roads will contain exactly n characters.
-All characters in roads will be between '0' and '8', inclusive.
-Character i in element i of roads will be '0'.
-Character i in element j of roads will be the same as character j in element i of roads.
 

Examples

0)
    
{"04",
 "40"}
Returns: 0.5
There is exactly one road connecting the capital and city 1. The answer is equal to the probability that the road is available after the rain.
1)
    
{"08",
 "80"}
Returns: 1.0
The same example as above, but this time the road is always available.
2)
    
{"00",
 "00"}
Returns: 0.0
In this case, all roads have been destroyed.
3)
    
{"088",
 "808",
 "880"}
Returns: 0.0
Here all three roads 0-1, 0-2 and 1-2 are definitely not destroyed. These roads form a cycle, so you can always remove a road in such way that all cities are reachable from the capital.
4)
    
{"044",
 "404",
 "440"}
Returns: 0.375
Exactly two of three roads should be available, so the probability is C(3,2) * 0.5^3 = 0.375.
5)
    
{"0701",
 "7071",
 "0708",
 "1180"}
Returns: 0.622314453125

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9834

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13516&pm=9834

Writer:

crazyb0y

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Math