BestEvenSplit
SRM 802 · 2021-03-18 · by misof
Problem Statement
Time limit is 3 seconds.
There are N students, where N is even. The students are numbered starting from 0.
Some pairs of students are friends: for each valid i, students X[i] and Y[i] are friends.
For a group project the students have to be split into two groups with exactly N/2 students in each of them. The quality of a split can be measured by the number of friendships that are broken by the split. More precisely, for each split we can count the pairs of friends who aren't in the same group, and we want to minimize this value.
Return the number of optimal ways to split the students into two groups. (Two ways of splitting the students are considered the same if each student's groupmates are the same.)
Constraints
- N will be between 2 and 30, inclusive.
- N will be even.
- X and Y will contain the same number of elements.
- For each i, 0 <= X[i] < Y[i] <= N-1.
- All pairs of friends described by X and Y will be distinct.
6
{0, 0, 1, 1, 3}
{2, 4, 3, 5, 5}
Returns: 1
There are five friendships: 0-2, 0-4, 1-3, 1-5, and 3-5. There is an unique optimal split of these students into teams: one team has to be {0,2,4} and the other {1,3,5}. This way everyone's all friends are on their team.
6
{}
{}
Returns: 10
Each of the 10 possible splits of these students into two groups is clearly equally good.
6
{3}
{5}
Returns: 4
In the optimal split students 3 and 5 have to be in the same group. We have four possibilities for their last teammate.
30
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 25, 25, 26, 27, 28 }
{ 2, 3, 5, 6, 7, 10, 11, 12, 17, 18, 23, 26, 27, 3, 4, 5, 6, 7, 11, 13, 16, 17, 21, 22, 26, 3, 4, 8, 9, 10, 12, 13, 14, 17, 23, 24, 28, 29, 4, 9, 12, 14, 17, 27, 5, 6, 7, 12, 14, 15, 17, 19, 21, 22, 23, 24, 26, 28, 6, 8, 10, 11, 15, 18, 19, 22, 26, 29, 9, 13, 16, 17, 19, 20, 21, 22, 25, 27, 9, 10, 16, 17, 19, 20, 22, 29, 10, 11, 14, 15, 17, 19, 21, 27, 28, 13, 19, 20, 24, 25, 28, 14, 15, 16, 20, 21, 22, 25, 26, 29, 17, 18, 25, 26, 27, 13, 16, 17, 23, 25, 28, 29, 16, 17, 19, 20, 21, 25, 26, 27, 28, 16, 17, 18, 21, 23, 24, 28, 29, 16, 18, 22, 18, 19, 20, 22, 27, 29, 19, 21, 23, 25, 29, 19, 20, 21, 23, 25, 20, 22, 24, 25, 27, 28, 21, 25, 28, 22, 23, 24, 23, 24, 25, 26, 27, 24, 25, 27, 29, 28, 29, 27, 29, 27, 28, 29 }
Returns: 8
2
{}
{}
Returns: 1
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BestEvenSplit with a public method int count(int N, vector<int> X, vector<int> Y) · 78 test cases · 2 s / 256 MB per case