Connection Status:
Competition Arena > JobPlanner

JobPlanner

TCCC07 Sponsor 2 · 2007-07-30 · by andrewzta

TCCC07 Sponsor 2 · 2007-07-30 · by andrewzta · Graph Theory
Class Name: JobPlanner
Return Type: int
Method Name: minimalCost
Arg Types: (vector<string>, vector<int>)
Problem Statement

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.

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.

4)
{"YY"}
{1}
Returns: 4

Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class JobPlanner with a public method int minimalCost(vector<string> can, vector<int> cost) · 85 test cases · 2 s / 256 MB per case

Submitting as anonymous