EllysPairs
TCO13 Round 1B · 2013-02-19 · by espr1t
TCO13 Round 1B · 2013-02-19 · by espr1t · Greedy, Simple Search, Iteration, Sorting
Problem Statement
Problem Statement
In one of her subjects at the university, Elly and her classmates have to prepare projects. The professor wants the students to work in pairs (groups of two). Each student must belong to exactly one pair and each pair should produce one project. You may assume that the number of people in the class is even.
You are given aint[] knowledge. Each element of knowledge is the amount of knowledge of one of the students. The quality of a project is the total knowledge of the students that work on it. That is, if students i and j form one of the pairs, the quality of their project will be knowledge[i] + knowledge[j].
This creates some problems. If there is a really strong group, their project will be of really high quality. The professor will then compare the other projects to it and will be disappointed by them, giving low grades to the other pairs. Thus, the students want to form the groups in such way that the difference between the quality of the best project and the quality of the worst project is as small as possible.
Return that minimal difference in the quality between the best and the worst project if the students split into pairs in the best possible way.
You are given a
This creates some problems. If there is a really strong group, their project will be of really high quality. The professor will then compare the other projects to it and will be disappointed by them, giving low grades to the other pairs. Thus, the students want to form the groups in such way that the difference between the quality of the best project and the quality of the worst project is as small as possible.
Return that minimal difference in the quality between the best and the worst project if the students split into pairs in the best possible way.
Constraints
- knowledge will contain between 2 and 50 elements, inclusive.
- The number of elements of knowledge will be even.
- Each element of knowledge will be between 1 and 1000, inclusive.
Examples
0)
{2, 6, 4, 3}
Returns: 1
Here obviously grouping the two best people in the class (with knowledge 6 and 4) doesn't make sense. If 6 pairs with 3 and 4 pairs with 2 they will get qualities of 9 and 6, respectively, leading to difference 3. However, there is an even better grouping: 2 with 6 and 4 with 3 for qualities of 8 and 7, respectively. The difference then would be only 1.
1)
{1, 1, 1, 1, 1, 1}
Returns: 0
Some or even all students can have the same knowledge.
2)
{4, 2, 4, 2, 1, 3, 3, 7}
Returns: 2
3)
{5, 1, 8, 8, 13, 7, 6, 2, 1, 9, 5, 11, 3, 4}
Returns: 3
4)
{4, 2}
Returns: 0
Submissions are judged against all 224 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysPairs with a public method int getDifference(vector<int> knowledge) · 224 test cases · 2 s / 256 MB per case