TopCoder problem "AntarcticaPolice" used in SRM 312 (Division I Level Two)



Problem Statement

    

Year 2100. Humanity is starting to inhabit Antarctica. So far there are N towns, some of them connected with narrow one-way roads.

The president of Antarctica has decided to establish police in his country. The cost of building a police station in each town is given. However, there may not be a need to build a police station in every town. The only requirement is that every town must be reachable from some police station using roads.

As the next elections are approaching, the president doesn't want to expose large police expenses. Thus he wants the average cost of a built station to be as low as possible.

You are given a int[] costs, the i-th element of which represents the cost of building a police station in town i, and a String[] roads representing the layout of the one-way roads. The j-th character of the i-th element of roads is 'Y' if there is a road from town i to town j, or 'N' if there is not. Make the average cost of a built station to be as low as possible and return this cost.

 

Definition

    
Class:AntarcticaPolice
Method:minAverageCost
Parameters:int[], String[]
Returns:double
Method signature:double minAverageCost(int[] costs, String[] roads)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute error of 1E-9.
 

Constraints

-costs will contain between 1 and 50 elements, inclusive.
-Each element of costs will be between 1 and 1000, inclusive.
-roads will contain exactly N elements, where N is the number of elements in costs.
-Each element of roads will contain exactly N characters.
-Each character of each element of roads will be 'Y' or 'N'.
-The ith character of the ith element of roads will be 'N'.
 

Examples

0)
    
{1,2,3,4}
{"NYNN","NNYN","NNNY","YNNN"}
Returns: 1.0
It is possible to get everywhere from anywhere (the towns form a big circle), so we need only the cheapest station.
1)
    
{1,2,3,4}
{"NYNN","NNYN","NNNY","NYNN"}
Returns: 1.0
Once again, the cheapest station is enough.
2)
    
{5,6,7,8}
{"NYNN","YNNN","NNNY", "NNYN"}
Returns: 6.0
We have two separate parts, so we build one cheapest station in each part : (5+7)/2=6.
3)
    
{10,5}
{"NY","NN"}
Returns: 7.5
We have three choices here: build a police station in town 0, in town 1, or in both towns. The second choice doesn't satisfy the requirements since it's impossible to get from town 1 to town 0. Of the two remaining choices, building both is better because it minimizes the average cost.
4)
    
{34,22,25,43,12}
{"NYNNY","YNNYN","NNNYY","NNNNN","NNNNN"}
Returns: 19.666666666666668

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9992&pm=6501

Writer:

Petr

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Graph Theory, Simple Math