PROBLEM STATEMENT
A contest is held where teams of players compete to complete tasks in the least
time possible. Teams earn points when they finish a task faster than other
teams, scoring one point for every team they beat on that task. The points
earned on each task are combined to get a total team score.
Teams are supposed to report in a specific order the time it took to complete
each task. Your team has made the questionable decision to try and improve
their total team score by rearraging the order in which they report their times.
For example, if your team completed task 1 in 10 minutes and task 2 in 15
minutes, you may instead report 15 minutes for task 1 and 10 minutes for task 2.
Given your team's times, and a list of times reported by the other teams,
return the best possible score your team could achieve by changing the order in
which you report your times.
DEFINITION
Class Name: Cheaters
Method Name: getScore
Parameters: int, String[]
Returns: int
Method signature (be sure your method is public): int getScore(int tasks,
String[] taskTimes);
tasks - number of tasks.
taskTimes - String[] of task times for various teams.
Each String is formatted as follows (quotation marks are included for clarity
only)
"time1 time2 ... timeN"
Each time is a number between 1 and 10000, inclusive.
There must be one time for each task.
Example: for tasks=5, a taskTimes String might equal "1 10 100 1000 10000"
the element of taskTimes at index 0 contains the times for your team. The
remaining taskTimes are for the other teams.
returns the maximum number of points your team can get by rearraging your times.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
* tasks is between 2 and 5, inclusive.
* taskTimes has between 2 and 10 elements, inclusive.
* the format of each taskTimes string is "time1 time2 ... timeN". With one time
for each task and one space between times.
* the times are integers with a value between 1 and 10000, inclusive, with no
leading zeros.
Example 1:
tasks = 2
taskTimes = { "5 15", "10 11", "12 20" }
The first element is your team's times, 5 and 15.
There are two ways to report the times "5 15" or "15 5":
The first way: "5 15" earns 2 points for the first task (both 10 and 12 are
greater than 5) and 1 point for the second task (only 20 is greater than 15).
The total points for the "5 15" ordering is 2+1 = 3.
The second way: "15 5" earns 0 points for the first task and 2 points for the
second, for a total of 2 points.
In this case the maximum points possible is 3.
return 3
Example 2:
tasks = 5
taskTimes = { "5 10 15 20 25", "10 10 10 10 20", "20 10 10 10 15", "30 10 15 10
10" }
In this case, a best ordering is { "15 5 25 20 10" } which gives 2+3+0+0+2 = 7
points.
return 7
Example 3:
tasks = 2
taskTimes = { "10 15", "5 10" }
return 0
Example 4:
tasks = 3
taskTimes = { "100 1000 10000", "900 1000 1100", "100 200 300" }
return 3
Example 5:
tasks = 5
taskTimes = { "1 2 3 4 5", "6 5 4 3 2", "3 3 3 3 3" }
return 7