PROBLEM STATEMENT
In the past, whole organizations depended on a single, big computer to do all the computational
work. In a particular case, a computer has a list of pending jobs which is described by vector
duration and vector user, each with n elements. duration[i] is the total time in
minutes required to complete the i-th job and user[i] is a string that identifies the user that
requested that job. A user may request multiple jobs. The computer may only process one job at a
time. The waiting time for a user is defined as the time that this user has to wait before all of
the jobs (s)he requested are finished. The computer will always pick a schedule to process the
jobs in such a way that the average of waiting times over all users is minimized. If there are
multiple schedules that can accomplish the minimum average waiting time, the computer will pick
any of them with equal probability.
We need a way to estimate how long the computer will take to finish each of the jobs. Your method
must return a vector containing n elements. The i-th element of your return must be the
expected time in minutes before the computer finishes processing the i-th job.
DEFINITION
Class:BatchSystemRoulette
Method:expectedFinishTimes
Parameters:vector , vector
Returns:vector
Method signature:vector expectedFinishTimes(vector duration, vector user)
NOTES
-User names are case sensitive. A user named "Bob" is different from a user named "bob". See
example 1 for clarification.
-Each element of the returned value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-duration will contain between 1 and 50 elements, inclusive.
-user will contain the same number of elements as duration.
-Each element of duration will be between 1 and 1000000000, inclusive.
-Each element of user will contain between 1 and 50 characters, inclusive.
-Each element of user will contain only letters ('a'-'z','A'-'Z') and at most one space character
that will not be a leading or trailing space.
EXAMPLES
0)
{3, 2, 4, 1}
{"Gil Grissom", "Sarah Sidle", "Warrick Brown", "Catherine Willows"}
Returns: {6.0, 3.0, 10.0, 1.0 }
There is only one optimal way to schedule the jobs: {3, 1, 0, 2}.
1)
{3, 2, 4, 1}
{"mac taylor", "Mac Taylor", "Mac Taylor", "Peyton Driscoll"}
Returns: {4.0, 8.0, 9.0, 1.0 }
This time, there are two different ways to schedule the jobs that are optimal: {3, 0, 1, 2} and
{3, 0, 2, 1}.
2)
{13, 14, 15, 56, 56}
{"Tim Speedle", "Tim Speedle", "Tim Speedle", "Horatio Caine", "YEEEAAAAAAAAAAH"}
Returns: {27.5, 28.0, 28.5, 126.0, 126.0 }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.