RoadsOfKingdom
SRM 425 · 2008-11-12 · by Olexiy
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
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.
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.
{"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.
{"08",
"80"}
Returns: 1.0
The same example as above, but this time the road is always available.
{"00",
"00"}
Returns: 0.0
In this case, all roads have been destroyed.
{"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.
{"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.
Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RoadsOfKingdom with a public method double getProbability(vector<string> roads) · 114 test cases · 2 s / 256 MB per case