HockeyAllStars
SRM 846 · 2023-05-22 · by misof
Problem Statement
The time limit for this problem is 4 seconds.
A small group of the best players in the whole league has been pre-selected as those who would deserve to play in an exhibition "all-stars" game.
For simplicity, each of these players has been assigned a positive integer representing their skill level. These are given in the
The entertainment the viewers get from an all-stars game comes from two factors: they want to see an exciting, balanced game, but they also want to see all their favorite players. In this problem we'll try to balance these two goals somehow.
Ideally, we would like to split the selected players into two teams with exactly equal skill. (The skill of a team will, naturally, be calculated simply as the sum of skills of its members.) Of course, this might be impossible to achieve, so we'll want to get as close to this ideal goal as possible.
We can deviate from the ideal goal in two ways: First, we can decide not to invite some of the pre-selected players to the all-stars game. Let U be the sum of skills of the uninvited players. Clearly, the higher U is, the farther we are from the goal of showing all the good players, so we want to keep U small.
Second, when dividing the invited players into the two teams who will face each other, we may be unable to achieve a perfect split. Let D be the non-negative difference between the skills of the two teams. Clearly, the higher D is, the farther we are from the goal of having a balanced match, so we want to keep D small.
In order to balance these two goals, we have chosen a positive integer K and we have decided to minimize the total value of (U + K*D).
Calculate and return the smallest achievable value of (U + K*D) over all ways to invite players to the all-stars game and select the two teams who will play each other.
Constraints
- skill will have between 1 and 26 elements, inclusive.
- Each element of skill will be between 1 and 80,000,000, inclusive.
- K will be between 1 and 1,000,000, inclusive.
{100, 200, 300, 400, 1000}
47
Returns: 0
It is possible to split these players perfectly: the first four will play against the fifth.
{100}
1
Returns: 100
All mathematically possible ways to invite and split players should be considered valid solutions, even if they don't make much sense in real life. E.g., there can be a perfectly balanced exhibition game with zero players on each side, or an exhibition game in which a non-empty team plays against an empty team. In this case it does not matter whether we invite the only player or not. If we don't, we have U=100 and D=0, if we do, we have U=0 and D=100. In both cases the total badness of the solution is 100.
{100, 200, 300, 1000, 4000, 4010, 400}
2
Returns: 20
The optimal solution is to invite everyone (U = 0) and create two teams with a small skill difference: D = 10.
{100, 200, 300, 1000, 4000, 4010, 400}
1000
Returns: 8010
These are the same players but now K is much bigger. Now the optimal solution is to uninvite the two best players (U = 8010) and then to split the remaining players perfectly (D = 0), as in Example 0.
{47224006, 8391988, 57738621, 74308314, 60890673, 76610215, 46099729, 34551385, 68779119, 51882812, 52669104, 5490676, 56174496, 3175573, 13751392, 84089, 35407528, 64632920, 73375192, 1226181}
1899
Returns: 175241
{10, 20, 147, 147, 1000, 1001}
100
Returns: 130
Here the optimal solution is a trade-off: we cut the two weakest players (U = 10+20 = 30) and then we form two almost-equal teams with D = 1. (One is 147+1000 and the other 147+1001.)
Submissions are judged against all 122 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HockeyAllStars with a public method long long split(vector<int> skill, int K) · 122 test cases · 2 s / 256 MB per case