PROBLEM LINK:
[Practice][1]
[Contest][2]
Author: [Vasia Antoniuk][3]
Tester: [Sergey Kulik][4]
Editorialist: [Mugurel Ionut Andreica][5]
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
Chef must draw the minimum number of balloons from a box containing R red, G green and B blue balloons, in such a way that he is certain that there will be at least K balloons of the same color among the drawn balloons.
QUICK EXPLANATION:
The answer is min{R,K-1}+min{G,K-1}+min{B,K-1}+1.
EXPLANATION:
Let’s consider what is the worst case that Chef can encounter before he is certain that he extracted at least K balloons of the same color. If all R, G and B are greater than or equal to K then the worst case is that Chef picks K-1 balloons of each of the 3 colors. After extracting 3x(K-1) balloons he can be certain that, after the next balloon he extracts, there will be at least K balloons of the same color. On the other hand, he cannot stop after extracting less than or equal to 3x(K-1) balloons because of the worst case we mentioned (meaning that in this case it’s possible to not have at least K balloons of the same color).
In the general case, when any of R, G or B can be smaller than K, the worst case is defined as follows. For each color C, if there are at least K balloons of that color, then the worst case will contain K-1 balloons of that color. Otherwise it will contain all the balloons of that color. This means that as soon as Chef extracts min(R,K-1)+min(G,K-1)+min(B,K-1) balloons, he only needs one more balloon to be certain that he has at least K balloons of the same color among the extracted balloons. Thus, the answer is min(R,K-1)+min(G,K-1)+min(B,K-1)+1.
Time complexity: O(1) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
[1]: http://www.codechef.com/problems/CHBLLNS
[2]: http://www.codechef.com/APRIL16/problems/CHBLLNS
[3]: http://www.codechef.com/users/antoniuk1
[4]: http://www.codechef.com/users/xcwgf666
[5]: http://www.codechef.com/users/mugurelionut
[6]: X
[7]: Y