TopCoder problem "BuildATeam" used in TCO07 Qual 2 (Division I Level One)



Problem Statement

    

Several people want to play hockey, so they use the following algorithm to split themselves into teams. First, there are teams captains, numbered from 1 to teams. The captains select players for their teams, always trying to pick the strongest player who hasn't been picked yet. The draft process is split into several rounds, which are enumerated starting from 1. Captain 1 starts round 1 of the draft by picking the strongest available player, followed by captain 2 and all other captains in order of ascending indices. When captain teams makes his pick, round 1 is over. If not all the players were picked, the draft continues with round 2. In round 2, all captains make their picks in the reverse order - so captain teams starts the round, and captain 1 ends it. Rounds 3, 5 and all other rounds with odd numbers go similar to round 1, while all rounds with even numbers go similar to round 2. For example, if there are 4 captains, they'll pick players in the following order: 1, 2, 3, 4, 4, 3, 2, 1, 1, 2, 3, ... The draft is over when all players are picked.

You will be given a int[] skills, representing the skills of all players. Also you will be given an int teams - the number of teams which must be created. You are to simulate the draft process and return the maximal team strength among all the teams. The strength of a team is the sum of the skills of all its players.

 

Definition

    
Class:BuildATeam
Method:maximalStrength
Parameters:int[], int
Returns:int
Method signature:int maximalStrength(int[] skills, int teams)
(be sure your method is public)
    
 

Constraints

-skills will contain between 2 and 50 elements, inclusive.
-Each element of skills will be between 1 and 100, inclusive.
-teams will be between 2 and 50, inclusive.
-The number of elements in skills will be an integer multiple of teams.
 

Examples

0)
    
{10, 9, 7, 3, 3, 2}
3
Returns: 12
The players will be split into the following teams: 
Team      1    2   3
Round 1   10   9   7 
Round 2   2    3   3
Teams 1 and 2 both have a strength of 12, while team 3 has a strength of 10.
1)
    
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
4
Returns: 21
Team 1 has the maximal strength of 12 + 5 + 4 = 21.
2)
    
{10, 10, 10, 9, 8, 8, 3, 1}
2
Returns: 31
Players 1, 4, 5 and 8 (with strengths of 10, 9, 8 and 1) go to team 1, while the other four players (with strengths of 10, 10, 8 and 3) go to team 2. The total strength of team 1 is 28, and the total strength of team 2 is 31.
3)
    
{10, 8, 10, 1, 10, 9, 3, 8}
2
Returns: 31
The same people as in example 2, but placed in another order.
4)
    
{98, 19, 11, 11, 11, 11, 23, 55, 1, 4, 3, 4, 6, 8}
7
Returns: 99

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10731&pm=7627

Writer:

Olexiy

Testers:

PabloGilberto , brett1479 , vorthys

Problem categories:

Simple Search, Iteration