TopCoder problem "BuildTheBestTeam" used in TCO07 Qual 2 (Division I Level Three)



Problem Statement

    

Several people want to play hockey, so they use the following algorithm to split themselves into teams. There are teams captains, numbered from 1 to teams, who select players for their respective teams. The draft process is split into several rounds, which are enumerated starting from 1. Captain 1 starts round 1 of the draft by picking a single player, followed by captain 2 and all the other captains in order of ascending indices. When captain teams makes his pick, round 1 is over. If any unpicked players remain, the draft continues with round 2. In round 2, all captains make their picks in 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.

One of the captains wants to have a team which will use powerplay tactics during its games, while all the other captains want to have regular teams. Powerplay skills are different from the usual skills required for playing hockey. You will be given int[]s usualSkills and powerplaySkills. The i-th elements of usualSkills and powerplaySkills represent the usual and powerplay skills, respectively, of the i-th player.

During the draft, a captain of a regular team will always pick the player with the highest usual skill among all remaining players. If several players have the same maximal usual skill, the player with the higher powerplay skill will be picked. The captain of the powerplay team will make his picks in such a way that maximizes the final total powerplay skill in his team. This means he won't necessarily always pick the remaining player with the highest powerplay skill (see examples). You will be given an int ind - the 1-based number of the captain who wants to build the powerplay team. Return the total powerplay skill of the team he chooses.

 

Definition

    
Class:BuildTheBestTeam
Method:maximalStrength
Parameters:int[], int[], int, int
Returns:int
Method signature:int maximalStrength(int[] usualSkills, int[] powerplaySkills, int teams, int ind)
(be sure your method is public)
    
 

Constraints

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

Examples

0)
    
{10, 10, 10, 10, 10, 10}
{20, 20, 20, 20, 20, 20}
3
2
Returns: 40
All players have equal skills, so the order of picks doesn't matter here. The powerplay team will get 2 players with powerplay skills of 20, resulting in a total skill of 40.
1)
    
{10, 10, 10, 10, 10, 10}
{10, 30, 10, 10, 30, 10}
3
3
Returns: 20
The two players with higher powerplay skills will be the first two picks, so team 3 will get only 2 players with powerplay skills of 10.
2)
    
{1, 2, 3, 4, 5, 6}
{6, 5, 4, 3, 2, 1}
3
1
Returns: 11
The powerplay team can get players with powerplay skills of 6 and 5.
3)
    
{1, 2, 3, 4, 5, 6}
{6, 2, 4, 3, 5, 1}
3
1
Returns: 11
4)
    
{88, 82, 82, 73}
{68, 74, 14, 1}
2
1
Returns: 75
According to the rules the powerplay captain has the first and the last picks, while the other captain has the second and the third. The powerplay captain has the following choices: 
- Pick player 1. The second team will pick players 2 and 3, and player 4 goes to powerplay team. 
  The total strength of powerplay team will be 68 + 1 = 69.
- Pick player 2. The second team will pick players 1 and 3, and player 4 goes to powerplay team. 
  The total strength of powerplay team will be 74 + 1 = 75.
- Pick player 3 or player 4. In either case, the second team will pick players 1 and 2.
  The total strength of powerplay team will be 14 + 1 = 15.

Problem url:

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

Problem stats url:

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

Writer:

Olexiy

Testers:

PabloGilberto , brett1479 , vorthys

Problem categories:

Dynamic Programming