CHBLLNS - editorial

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

I think pigeon hole principle is a pre requisite to this problem

not really

that was an easy one

in my solution i used it

its just basic probabilty.

Can anybody please tell me why I am getting wrong answer, for all the test cases I tried I am getting correct answer. URL to answer https://www.codechef.com/viewsolution/9997800

Please help.