TopCoder problem "PowerPlants" used in SRM 364 (Division I Level Two , Division II Level Three)



Problem Statement

    

Our hero, Homer, has just woken to a horrible discovery! While sleeping at work, several of the power plants in the state have lost power. Even worse, his boss is on the way to his office, and if he doesn't have the situation fixed in time, he'll be fired. He's called you, desperately asking for help, and you've agreed to help him figure things out.

Homer has given you connectionCost, in which the j-th character of the i-th element indicates the cost to restart power plant j using power plant i; a digit ('0'-'9') stands for a cost of 0-9, while an uppercase letter ('A'-'Z') stands for a cost of 10-35. Homer has also given you the plantList, in which the i-th character indicates whether the i-th plant is still working after the power outage; a 'Y' indicates that it has power, otherwise, it is an 'N'. A plant can only be used to power another plant if it currently has power. Finally, he gives you numPlants, the minimum number of plants that need to be powered to save Homer's job. You need to return the minimum cost needed to power at least numPlants plants.

 

Definition

    
Class:PowerPlants
Method:minCost
Parameters:String[], String, int
Returns:int
Method signature:int minCost(String[] connectionCost, String plantList, int numPlants)
(be sure your method is public)
    
 

Constraints

-connectionCost will contain exactly N elements, where N is between 1 and 16, inclusive.
-Each element of connectionCost will contain exactly N characters.
-Each character of connectionCost will be a digit ('0'-'9') or uppercase letter ('A'-'Z').
-plantList will contain exactly N characters.
-Each character of plantList will be 'Y' or 'N'.
-At least one character of plantList will be 'Y'.
-numPlants will be between 0 and N, inclusive.
 

Examples

0)
    
{"024",
 "203",
 "430"}
"YNN"
3
Returns: 5
The cheapest way is to restart plant 1 using plant 0. Once plant 1 is active, you can then use it to restart plant 2.
1)
    
{"0AB",
 "A0C",
 "CD0"}
"YNN"
3
Returns: 21
Here we can use plant 0 to restart both of the others.
2)
    
{"1ABCD",
 "35HF8",
 "FDM31",
 "AME93",
 "01390"}
"NYNNN"
5
Returns: 14
3)
    
{"012",
 "123",
 "234"}
"NNY"
2
Returns: 2
4)
    
{"1309328",
 "DS2389U",
 "92EJFAN",
 "928FJNS",
 "FJS0DJF",
 "9FWJW0E",
 "23JFNFS"}
"YYNYYNY"
4
Returns: 0
5)
    
{"01","20"}
"YN"
2
Returns: 1
The cost to restart plant 0 using plant 1 may differ from the cost of restarting plant 1 using plant 0.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10778&pm=8062

Writer:

connect4

Testers:

PabloGilberto , radeye , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Search