CHBLLNS - editorial



Author: [Vasia Antoniuk][3]
Tester: [Sergey Kulik][4]
Editorialist: [Mugurel Ionut Andreica][5]






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.


The answer is min{R,K-1}+min{G,K-1}+min{B,K-1}+1.


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 solution can be found here.
Tester’s solution can be found here.
[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

Please help.