Connection Status:
Competition Arena > PickingUp

PickingUp

SRM 430 · 2008-12-20 · by Janq

SRM 430 · 2008-12-20 · by Janq · Brute Force, Search
Class Name: PickingUp
Return Type: int[]
Method Name: fairPickingUp
Arg Types: (vector<long long>, vector<long long>)
Problem Statement

Problem Statement

There are two captains who want to form two teams of equal size. There are N players to choose from, and both captains have given a rating to each of the players. The ratings are given in the long[]s score1 and score2, where score1[i] is the first captain's rating of the i-th player, and score2[i] is the second captain's rating of the i-th player. The total score of a team is defined as the sum of all its players' ratings according to the team's captain. Players must be assigned to the two teams such that the difference between the teams' total scores is as small as possible. Return a int[] containing exactly N elements, where the i-th element is the team to which the i-th player is assigned. The first captain's team is team 1, and the second captain's team is team 2. If multiple solutions exist, return the one that comes first lexicographically.

Notes

  • A sequence A comes before sequence B lexicographically if A has a smaller value at the first position where the sequences differ.

Constraints

  • score1 and score2 will contain between 2 and 36 elements, inclusive.
  • score1 and score2 will contain the same number of elements.
  • score1 and score2 will each contain an even number of elements.
  • Each element of score1 and score2 will be between 1 and 10^15, inclusive.
Examples
0)
{1,2,1,2}
{2,1,2,1}
Returns: {1, 1, 2, 2 }
1)
{5,9}
{8,6}
Returns: {1, 2 }

If we assign the first player to the first team and the second player to the second team, the team scores will be 5 and 6. In the opposite case, the team scores would be 8 and 9. In both cases, the difference is equal to 1. The answer is {1,2} because it comes before {2,1} lexicographically.

2)
{2,3,4,7}
{2,4,5,8}
Returns: {1, 2, 2, 1 }

The only way to balance the teams is to assign the first and last players to the first team. The first team's score will be 2+7 and the second team's score will be 4+5.

3)
{1,5,6,8}
{7,5,3,1}
Returns: {1, 2, 1, 2 }

We cannot balance these teams evenly. We can come close by assigning the first and third players to the first team. The first team's score will then be 7 and the second team's score will be 6.

4)
{300,300,300,300}
{600,10,10,10}
Returns: {2, 1, 1, 2 }
93)
{50,50,50,1}
{30,30,30,150}
Returns: {1, 2, 2, 1 }

Teams must be of equal size.

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

Coding Area

Language: C++17 · define a public class PickingUp with a public method vector<int> fairPickingUp(vector<long long> score1, vector<long long> score2) · 119 test cases · 2 s / 256 MB per case

Submitting as anonymous