Connection Status:
Competition Arena > BuildATeam

BuildATeam

TCO07 Qual 2 · 2007-03-07 · by Olexiy

TCO07 Qual 2 · 2007-03-07 · by Olexiy · Simple Search, Iteration
Class Name: BuildATeam
Return Type: int
Method Name: maximalStrength
Arg Types: (vector<int>, int)
Problem Statement

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.

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

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

Coding Area

Language: C++17 · define a public class BuildATeam with a public method int maximalStrength(vector<int> skills, int teams) · 56 test cases · 2 s / 256 MB per case

Submitting as anonymous