TopCoder problem "JobPlanner" used in TCCC07 Round 2 (Division I Level Three)



Problem Statement

    

You have m workers numbered 1 through m, and you have n tasks that must be completed. You know which tasks can be performed by each of the workers. If worker i completes t different tasks, he must be paid cost[i]*t2. You would like to minimize the total cost of completing all the tasks.

You will be given a String[] can describing the capabilities of your workers. The i-th element describes worker i and contains n characters. The j-th character is 'Y' if the worker can perform the j-th task, and 'N' if he can't. You will also be given a int[] cost. The i-th element of cost is the cost of worker i (as used in the formula above). All indices are 1-based. Return the minimal total cost required to complete all the tasks, or -1 if all the tasks cannot be completed.

 

Definition

    
Class:JobPlanner
Method:minimalCost
Parameters:String[], int[]
Returns:int
Method signature:int minimalCost(String[] can, int[] cost)
(be sure your method is public)
    
 

Constraints

-can will contain between 1 and 50 elements, inclusive.
-All elements of can will contain the same number of characters.
-Each element of can will contain between 1 and 50 characters, inclusive.
-Each element of can will contain only 'Y' and 'N' characters.
-cost will contain the same number of elements as can.
-Each element of cost will be between 1 and 500,000, inclusive.
 

Examples

0)
    
{"YY","YY"}
{1,2}
Returns: 3
In this case each worker can perform any task. It is better to give one task to the first worker, and another task to the second worker. The total cost is 1 * 12 + 2 * 12 = 3.
1)
    
{"YY","YY"}
{1,5}
Returns: 4
In this case it is better to give both tasks to the first worker since the second one is too expensive. The total cost is 1 * 22 + 5 * 02 = 4.
2)
    
{"YN", "YY"}
{1, 5}
Returns: 6
In this case the first worker cannot perform the second task, so we need to use the second worker. The total cost is 1 * 12 + 5 * 12 = 6.
3)
    
{"YN", "YN"}
{1, 1}
Returns: -1
In this case the second task cannot be completed at all.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10891&pm=6177

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , radeye , Olexiy , ivan_metelsky

Problem categories:

Graph Theory