Problem Statement
A Christmas cracker is a festive table decoration that resembles an oversized sweet-wrapper. The middle part of a cracker usually contains some small gift and a terrible Christmas pun. ("What does Santa feel when going down a narrow chimney? Claus-trophobia!")
It is customary that each cracker should be opened by two people. Each person takes hold of one end of the cracker and they pull in opposite directions. This will cause the cracker to split into two parts. The cracker always splits unevenly: one of the two people is the winner and gets the central chamber with the prize, the other person is the loser and gets nothing.
Whenever a cracker is opened, the winner is determined randomly. The two people opening the cracker cannot influence which one of them will be the winner.
N guests (numbered 0 to N-1) are attending your Christmas party. You already gave them M crackers (numbered 0 to M-1), and they have already opened all of them. For cracker i, guest number winner[i] was the winner and got the prize, while guest number loser[i] was the loser and got nothing.
A guest is happy if they were the winner at least once.
You would like all guests at your party to be happy. Sadly, that is not always possible: somebody may be really unlucky and lose each time they open a cracker. Thus, you would like the next best thing: at least N-1 of your guests should be happy.
You are now going to buy some additional crackers. You will then give the crackers to your guests to open. You will be handing the crackers out one at a time. For each cracker, you can select the two guests who should open it. You can then wait and see who won before you hand out the next cracker.
Remember that your goal is that at least N-1 of your guests should be happy. What is the minimum number of crackers you need to purchase so that you can reach your goal with absolute certainty? Calculate and return that number.
Definition
- Class:
- ChristmasCrackerHappiness
- Method:
- solve
- Parameters:
- int, int[], int[]
- Returns:
- int
- Method signature:
- int solve(int N, int[] winner, int[] loser)
- (be sure your method is public)
Notes
- The value M (the number of already opened crackers) is not given explicitly. You can determine it as the length of the array winner.
- Each of the new crackers must be also opened by two distinct people.
Constraints
- N will be between 2 and 50, inclusive.
- winner will contain between 0 and 50 elements, inclusive.
- loser will contain the same number of elements as winner.
- Each element of winner will be between 0 and N-1, inclusive.
- Each element of loser will be between 0 and N-1, inclusive.
- For each i, winner[i] will not be equal to loser[i].
Examples
2
{}
{}
Returns: 1
You have two guests. They haven't opened any crackers yet, so neither of them is happy. You can buy one cracker and give it to them. One of them will win. You don't know who it's going to be, but that does not matter: certainly, once they will open the cracker you will have one happy guest and you will reach your goal.
5
{0, 1, 0, 3, 2, 0, 4, 0}
{3, 3, 4, 1, 0, 2, 1, 3}
Returns: 0
All your guests are already happy, no additional crackers are needed.
12
{3, 1, 4, 1, 5, 9, 2, 6}
{5, 3, 5, 8, 9, 7, 9, 3}
Returns: 4
2
{0}
{1}
Returns: 0
2
{1,1,1}
{0,0,0}
Returns: 0
2
{0,1,1,0}
{1,0,0,1}
Returns: 0
25
{13, 17, 14, 18}
{10, 8, 17, 12}
Returns: 20
28
{1, 25, 13, 21, 0, 3, 0, 8, 25, 15, 23, 17, 0, 26, 10, 18, 13, 7, 7, 16, 16, 11, 14, 7, 1, 17, 11, 22, 22, 11, 19, 10, 17, 18, 24, 6, 7, 25, 26}
{24, 1, 4, 10, 4, 12, 19, 13, 16, 18, 27, 8, 4, 20, 7, 23, 10, 6, 16, 24, 3, 25, 13, 20, 12, 22, 9, 25, 26, 7, 26, 18, 8, 11, 17, 19, 1, 15, 9}
Returns: 6
39
{25, 16, 33, 14, 38, 7, 13, 24, 31, 16, 38, 35, 9, 28, 0, 10, 35, 5, 4, 17, 32, 34, 30, 27, 23, 2, 38, 16, 38, 33, 30, 20, 1, 36, 15, 13, 22, 27, 11, 11, 30, 12, 8, 6, 8, 36, 22, 33, 25}
{6, 18, 28, 0, 7, 27, 4, 23, 1, 17, 2, 8, 12, 33, 32, 13, 31, 34, 30, 37, 37, 0, 4, 11, 9, 35, 21, 2, 15, 3, 24, 7, 2, 5, 20, 3, 36, 19, 16, 35, 9, 36, 38, 18, 37, 5, 37, 31, 21}
Returns: 6
38
{7, 26, 26}
{23, 19, 37}
Returns: 35
34
{8, 4, 32, 7, 29, 29, 1, 27, 33, 4, 18, 31, 32, 7, 15, 22, 21, 10, 29, 1, 6, 29, 29, 17, 1, 12, 18, 2, 16, 30, 24, 4, 6, 33, 30, 23, 19, 26}
{14, 6, 6, 33, 19, 25, 22, 23, 6, 6, 28, 23, 3, 23, 3, 26, 17, 17, 13, 19, 14, 30, 19, 29, 29, 21, 3, 10, 31, 0, 1, 28, 30, 28, 16, 18, 6, 19}
Returns: 9
10
{6, 5, 7, 6, 3, 8, 9, 8, 4, 5}
{9, 0, 6, 8, 9, 2, 6, 0, 2, 2}
Returns: 2
42
{31, 26, 3, 14}
{29, 11, 39, 26}
Returns: 37
3
{0, 2, 0, 2, 1, 0, 1, 1, 2, 1, 2, 1, 2, 0, 2, 1, 0, 0, 1, 1, 2, 0, 2, 0, 2, 1, 1, 1, 2, 0, 1, 2, 2, 1, 1, 2, 0, 1, 1}
{1, 0, 2, 1, 0, 2, 2, 0, 1, 0, 1, 0, 0, 1, 1, 2, 1, 1, 2, 0, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0}
Returns: 0
7
{1, 4, 3, 6, 2}
{0, 3, 2, 4, 6}
Returns: 1
17
{11, 2, 10, 3, 1, 6, 4, 10, 2, 10, 13, 16, 11, 16, 16, 13, 14, 13, 13, 15, 0, 6, 10, 1, 13, 3, 14, 3, 3, 10, 13, 1, 10, 5, 13, 15, 16, 15, 16, 3, 7, 6, 0}
{16, 11, 4, 6, 10, 2, 1, 9, 1, 0, 8, 11, 6, 6, 11, 11, 4, 6, 15, 1, 10, 10, 14, 4, 14, 14, 11, 16, 9, 1, 16, 8, 8, 13, 1, 0, 12, 6, 13, 12, 2, 12, 11}
Returns: 2
31
{28, 2, 15, 8}
{2, 6, 6, 7}
Returns: 26
30
{25, 6, 9, 0, 3, 19, 18, 26, 0, 8, 17, 6, 17, 11, 15, 29, 6, 10, 12, 29, 1, 21, 20, 18, 13, 10, 25, 25, 17, 11}
{29, 0, 3, 1, 10, 26, 1, 19, 7, 27, 27, 28, 16, 28, 20, 0, 1, 28, 18, 18, 2, 12, 29, 25, 15, 6, 2, 8, 22, 21}
Returns: 10
28
{11, 1, 2, 9, 19, 22, 9, 1, 19, 14, 14, 13, 23, 23, 10, 23, 2, 8, 27, 13, 11, 3, 22, 12, 12, 5, 9, 0, 0, 18, 21, 18}
{26, 7, 5, 18, 7, 2, 0, 14, 13, 13, 23, 14, 18, 24, 4, 4, 25, 24, 23, 24, 13, 18, 20, 15, 8, 21, 27, 21, 5, 2, 1, 19}
Returns: 9
18
{4, 2, 0, 4, 3, 16, 4, 9, 13, 17, 15, 0, 5, 17, 4, 7, 3, 4, 9, 15, 15, 14, 9, 13, 14, 5, 0, 13, 15, 15, 13, 10, 11, 17, 9, 9, 12, 12, 1, 16, 8, 4, 14, 12, 3, 3}
{1, 12, 11, 5, 0, 8, 12, 5, 1, 13, 16, 11, 4, 8, 9, 11, 14, 3, 6, 5, 7, 9, 7, 15, 17, 11, 5, 17, 11, 3, 4, 5, 7, 16, 11, 6, 7, 1, 12, 12, 5, 16, 5, 6, 13, 1}
Returns: 0
33
{4, 16, 6, 8, 32, 13, 17, 24, 7, 16, 22, 7, 24, 23, 14, 18, 16, 20, 2, 13}
{19, 29, 21, 7, 9, 11, 16, 21, 18, 6, 18, 14, 2, 17, 13, 12, 32, 32, 5, 25}
Returns: 17
44
{41}
{37}
Returns: 42
12
{6, 4, 3, 6, 3, 1}
{3, 11, 11, 11, 4, 9}
Returns: 7
8
{6, 4, 5, 5, 1, 1, 5, 7, 3, 1, 1, 5, 7, 3, 0, 5, 4, 6, 4, 0, 1, 4, 7, 3, 7, 4, 5, 6, 3, 5, 3, 2, 3, 3, 0}
{0, 6, 4, 7, 5, 7, 7, 4, 2, 6, 5, 2, 1, 2, 5, 7, 5, 5, 5, 3, 5, 1, 5, 7, 6, 2, 2, 1, 1, 6, 6, 4, 0, 0, 4}
Returns: 0
32
{28, 18, 6, 31, 17, 21, 18, 13, 27, 4, 16, 24, 20, 29, 18, 10, 15, 11, 23, 14, 19, 2, 13, 30, 1, 22, 0, 18, 17, 26, 15, 29, 29, 3, 5, 8, 25, 28, 11, 15, 2, 25, 28, 6}
{17, 0, 18, 14, 18, 15, 27, 19, 5, 6, 26, 25, 31, 7, 8, 22, 10, 6, 17, 31, 22, 28, 16, 16, 26, 24, 9, 14, 8, 10, 17, 3, 31, 8, 25, 9, 26, 31, 7, 1, 26, 4, 7, 23}
Returns: 2
50
{28, 47, 45, 49, 5, 20, 46, 35, 47, 41, 41, 13, 20, 40, 6, 16, 33, 10, 17, 23, 8, 47, 10, 5, 11, 3, 49, 32, 11, 38, 41, 35, 39, 39, 6, 18, 2, 20, 11, 5, 28, 17, 6, 19, 12}
{38, 49, 49, 31, 40, 47, 9, 8, 15, 46, 34, 16, 39, 19, 17, 44, 48, 30, 1, 19, 13, 48, 1, 28, 12, 18, 44, 31, 13, 28, 0, 23, 41, 15, 26, 33, 12, 11, 12, 39, 3, 13, 21, 40, 26}
Returns: 22
44
{17, 40, 5, 19, 14, 2, 35, 30, 19, 15, 18, 29, 11, 11, 35, 19, 29, 18, 18}
{40, 3, 20, 2, 43, 5, 40, 39, 26, 37, 33, 27, 9, 25, 24, 43, 35, 14, 34}
Returns: 31
38
{28, 34, 11, 16, 25, 20, 21, 7, 24, 27, 8, 5, 27, 15, 15, 0, 16, 34, 1, 21, 25, 34, 19, 12, 16, 4}
{3, 15, 12, 23, 22, 5, 32, 17, 17, 23, 14, 3, 16, 32, 14, 7, 34, 19, 12, 26, 17, 12, 34, 18, 10, 11}
Returns: 19
23
{8, 15, 3, 9, 22, 8, 4, 12, 21}
{7, 7, 6, 2, 9, 17, 5, 15, 9}
Returns: 14
5
{4, 1, 1, 0, 1, 3}
{3, 3, 3, 1, 3, 2}
Returns: 0
29
{2, 10, 8, 17, 26, 7}
{19, 24, 23, 4, 7, 22}
Returns: 22
34
{12, 2, 10, 1, 20, 14, 23, 14, 15, 31, 23, 12, 27, 11, 29, 14, 2, 26, 29, 14, 27, 1, 27, 32, 4, 31, 12, 25, 12, 0, 15, 31, 33, 0, 18}
{31, 21, 20, 33, 25, 15, 3, 13, 13, 32, 29, 32, 25, 26, 8, 27, 23, 0, 21, 6, 23, 33, 24, 16, 10, 3, 14, 3, 17, 17, 11, 23, 23, 15, 8}
Returns: 14
18
{4, 11, 1, 4, 5, 12}
{9, 17, 3, 5, 8, 10}
Returns: 12
32
{16, 6, 22, 16, 0, 17, 17, 29, 29, 9, 23, 8, 13, 1, 6, 3, 24, 31, 13, 10, 23, 3, 11, 15, 30, 30, 27, 3, 31, 14, 20, 14, 24}
{24, 15, 4, 21, 6, 5, 29, 6, 25, 11, 0, 19, 17, 24, 7, 18, 28, 14, 5, 9, 16, 21, 14, 21, 15, 17, 13, 28, 21, 0, 5, 19, 13}
Returns: 10
28
{17, 1}
{1, 20}
Returns: 25
47
{13, 30, 12, 35, 2, 34}
{7, 1, 22, 16, 31, 17}
Returns: 40
9
{1, 5, 7, 0, 4, 7, 7, 2, 1, 4, 5, 7, 0, 7, 0, 6, 1, 3, 5, 3, 3, 2, 3, 7, 8, 1, 4, 8, 1, 7, 3, 0, 2, 8, 4, 2, 4, 5, 2, 5, 8, 5, 2, 2, 6, 6, 5, 2}
{7, 0, 1, 7, 2, 1, 1, 3, 2, 1, 3, 0, 3, 6, 2, 1, 8, 0, 1, 2, 6, 3, 2, 4, 3, 3, 0, 6, 3, 6, 0, 2, 4, 6, 1, 6, 3, 6, 5, 3, 0, 4, 0, 3, 0, 4, 4, 7}
Returns: 0
48
{3, 23, 47, 41, 38, 16, 40, 11, 33, 40, 10, 12, 39, 1, 34, 29, 14, 16, 26, 30, 0}
{42, 3, 21, 39, 26, 5, 4, 40, 21, 13, 17, 22, 45, 8, 40, 9, 39, 29, 24, 38, 22}
Returns: 28
15
{14, 4, 10, 7, 3, 7, 2, 9, 6, 6, 3, 0, 5, 0, 13, 3}
{1, 1, 4, 3, 8, 8, 13, 2, 10, 1, 12, 1, 10, 6, 4, 10}
Returns: 3
5
{2, 2, 2, 1, 0, 2, 0, 3, 4, 4, 3, 2, 4, 3, 1, 2}
{0, 4, 4, 3, 2, 1, 1, 1, 0, 2, 4, 4, 1, 1, 0, 3}
Returns: 0
40
{13, 32, 2, 20, 17, 8, 26, 7, 7, 14, 33, 11, 39, 11, 38, 7, 25, 20, 17, 0, 32, 34, 17, 11, 32, 0, 32, 37, 19, 36, 19, 26, 36, 37, 23, 21, 15}
{19, 13, 22, 26, 24, 14, 8, 23, 33, 1, 29, 9, 34, 23, 25, 5, 5, 4, 36, 27, 33, 9, 11, 10, 28, 5, 13, 23, 25, 12, 32, 4, 35, 31, 12, 3, 1}
Returns: 17
23
{6, 12, 0, 4, 17, 21, 12, 11, 7, 3, 7, 6, 12, 8, 18, 14, 12, 13, 15, 1, 5, 4, 6, 11, 19, 17, 11, 4, 22, 1, 20, 1, 4, 20, 5}
{5, 1, 1, 12, 6, 0, 17, 4, 0, 11, 9, 10, 14, 4, 14, 15, 5, 22, 5, 17, 14, 0, 4, 5, 15, 4, 14, 12, 0, 0, 18, 15, 7, 9, 6}
Returns: 3
20
{9, 19, 13, 5, 10, 3, 18, 11, 17, 7, 6, 19, 14, 14, 5, 7, 8, 0, 3, 12, 1, 11, 18, 1, 14, 1, 3, 8, 10, 6, 11, 0, 11}
{7, 6, 6, 6, 11, 8, 12, 1, 3, 4, 17, 13, 10, 11, 15, 16, 15, 16, 19, 5, 2, 14, 19, 17, 18, 15, 11, 12, 14, 5, 17, 18, 18}
Returns: 3
17
{13, 1, 11, 9, 7, 15, 7, 6, 2, 15, 12, 6, 15, 0, 10, 7, 6, 10, 16, 7, 0, 12, 1, 16, 10, 10, 11, 16, 14, 1, 5}
{3, 7, 2, 8, 9, 12, 0, 3, 12, 13, 8, 12, 8, 5, 16, 4, 4, 9, 9, 1, 14, 11, 13, 14, 0, 8, 9, 15, 8, 13, 6}
Returns: 2
15
{6, 11, 10, 13, 7, 0, 14, 4, 7, 1, 8, 10, 12, 4, 11, 5, 13, 14, 8, 8, 3, 13, 1, 9, 1}
{0, 2, 4, 11, 5, 7, 1, 3, 10, 10, 4, 3, 5, 1, 8, 3, 12, 12, 7, 13, 14, 2, 2, 7, 0}
Returns: 0
15
{5, 0, 14, 7}
{1, 13, 11, 12}
Returns: 10
38
{30, 13, 10, 4}
{10, 4, 13, 14}
Returns: 33
14
{12, 11, 10, 3, 6, 11, 8, 7, 6, 0, 12, 8, 2, 3, 12, 8, 9, 0, 10, 5, 1, 4, 8, 7, 12, 7, 13, 6, 3, 7, 3, 4, 9, 8, 2, 10}
{13, 13, 6, 5, 10, 13, 10, 2, 12, 10, 2, 4, 0, 0, 13, 9, 8, 11, 12, 3, 4, 10, 1, 11, 6, 9, 3, 9, 0, 9, 2, 3, 12, 7, 7, 1}
Returns: 0
35
{33, 3, 10, 24, 18, 21, 19, 25, 31, 5, 19, 18, 19, 31, 7, 20, 33, 21, 21, 28, 12, 2, 0, 1, 31, 32, 29, 18, 27, 21, 8, 4, 6, 23, 13, 17, 31, 18, 23, 20, 13, 12, 13, 11, 10, 13, 30, 23}
{19, 11, 26, 20, 25, 7, 7, 27, 0, 1, 12, 25, 10, 30, 8, 2, 15, 1, 13, 4, 28, 27, 13, 15, 8, 30, 28, 4, 10, 19, 5, 28, 26, 18, 34, 11, 9, 13, 22, 34, 24, 17, 4, 8, 5, 16, 19, 24}
Returns: 6
32
{10, 28, 27, 6, 10, 2, 9, 30, 19, 26, 29, 26, 26, 14, 17, 11, 27, 7, 7, 20, 24, 12, 14, 25, 2, 9, 4, 11, 23, 22, 27, 18, 3, 28, 27, 1, 2, 1, 3, 7, 2, 6, 7, 15, 0, 9}
{9, 27, 31, 17, 16, 0, 2, 26, 16, 19, 17, 19, 25, 31, 19, 8, 30, 28, 31, 25, 15, 5, 30, 6, 7, 26, 29, 10, 28, 23, 24, 2, 28, 21, 31, 20, 19, 16, 4, 0, 15, 22, 15, 0, 2, 16}
Returns: 5
32
{7, 25, 20, 27, 23, 10, 18, 26, 30, 15, 18, 29, 21}
{26, 12, 16, 30, 9, 27, 13, 19, 24, 10, 14, 0, 4}
Returns: 19
49
{39, 22, 14, 7, 19, 5, 48, 44, 30, 20, 6, 20, 0, 25, 12}
{33, 17, 35, 16, 8, 48, 40, 2, 3, 19, 9, 39, 32, 34, 20}
Returns: 34
9
{6, 3, 6, 1, 5, 6, 7, 2, 4, 4, 0, 4, 3, 0, 4, 5, 0, 7, 6, 4, 6, 2, 1, 0, 6, 8, 8, 5, 1, 8, 3}
{8, 2, 3, 6, 8, 7, 5, 7, 5, 7, 3, 2, 4, 8, 6, 4, 7, 5, 7, 5, 2, 7, 0, 1, 7, 7, 5, 0, 5, 6, 7}
Returns: 0
17
{7, 11, 0, 3, 9, 3, 3, 13, 12, 8, 11, 12, 11, 1, 10, 13, 5, 16, 5, 13, 0, 8, 8, 11}
{1, 16, 8, 4, 10, 2, 14, 16, 13, 12, 6, 15, 6, 13, 16, 10, 8, 12, 9, 12, 13, 3, 12, 0}
Returns: 4
48
{}
{}
Returns: 47
17
{1, 3, 14, 10, 14, 7, 13, 0, 8, 14, 12, 10, 5, 11, 10, 11, 11}
{8, 11, 8, 14, 1, 6, 9, 2, 5, 12, 2, 8, 16, 3, 1, 1, 4}
Returns: 5
12
{ }
{ }
Returns: 11
2
{1, 0 }
{0, 1 }
Returns: 0
5
{0, 1, 0, 3, 2, 0, 4, 0 }
{3, 3, 4, 1, 0, 2, 1, 3 }
Returns: 0
12
{3, 1, 4, 1, 5, 9, 2, 6 }
{5, 3, 5, 8, 9, 7, 9, 3 }
Returns: 4
2
{ }
{ }
Returns: 1
5
{ }
{ }
Returns: 4
2
{0 }
{1 }
Returns: 0
50
{0 }
{1 }
Returns: 48