BuildTheBestTeam
TCO07 Qual 2 · 2007-03-07 · by Olexiy
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
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
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.
{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.
{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.
{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.
{1, 2, 3, 4, 5, 6}
{6, 2, 4, 3, 5, 1}
3
1
Returns: 11
{3, 4, 5, 67, 7, 4, 13, 31}
{11, 12, 13, 14, 21, 20, 22, 25}
4
2
Returns: 37
{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.
Submissions are judged against all 108 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BuildTheBestTeam with a public method int maximalStrength(vector<int> usualSkills, vector<int> powerplaySkills, int teams, int ind) · 108 test cases · 2 s / 256 MB per case