10648 - Chocolate Box

[Virtual GOD]

Hi!
Can anybody explain me task 10648 (Chocolate Box)? I don't understand it while contest and now... For example, what means "n types of chocolate"? It is that we have N different chocolates? and what means "What is the probability that one or more boxes are empty?"... one or more??

Thanks

[Adrian Kuegel]

n types of chocolate means, you have n chocolate pieces, but all look different, so you can distinguish them.
And you have to calculate the probability that at least one box is empty. So this is exactly 1 - probability that all boxes have at least one piece of chocolate in it.

[rotoZOOM]

Hello !
I've found that for calculation probabelities that all boxes are filled I have to deal with Biiiiiiiiiiiig numbers. How I calculate:
For example, let's take 5 types of chocolates and 3 boxes.
All possible distinguished variants for placement chocolates is:

Box1 Box2 Box3
I I III
I II II

Let's take first placemets. All possible variants of box permutation is 3!/2! (as two boxes will have equally number of chocolates). Probabilities such one placement would be 1/(3^5). Permutation of chocolates themselves inside boxes will be 5!/3! (as one of boxes will have 3 chocolates). Well, common probabilities placement of first type is 1/(3^5)*(3!/2!)*(5!/3!)=60/243
Calculate probabilities for second type placement like for first one.
All possible variants of box permutation is 3!/2!. Probabilities such one placement would be 1/(3^5). Permutation of chocolates themselves inside boxes will be 5!/(2!*2!). Well, common probabilities placement of second type is 1/(3^5)*(3!/2!)*(5!/(2!*2!))=90/243
Common probabilities for all placement where all boxes are filled:
60/243+90/243=150/243
So probabilities at least one boxes is empty is (1-150/243).
I show easy example. But when quantity of chocolates and boxes grows, numbers become too large.
Should I use long ariphmetic ?

[UFP2161]

I used "long double" which was enough precision to get an answer. Normal "double" may work as well.

[abishek]

I would like to know how the fact that the choclates are distinguishable affect the answer.
The probabilty that we put a choclate into any of the boxes is same, and so distinguishable or not the probability is the same.

I used a markov chain to model this event and found P^n for the one step transition matrix
where the state is number of filled boxes
but the answer goes to 1 or 0 only in the matrix.
help
abi

[UFP2161]

If you had 2 chocolates and 2 boxes:

If they were distinguishable (label them A and B), the unique ways to box them are:
[AB] []
[] [AB]
[A]
[A]

Thus, the probability that at least one is empty is 1/2.

However, if they were not distnguishable, you would have:
[AA] []
[] [AA]
[A] [A]

Thus, the probability that at least one is empty is 2/3.

[Alexander Kozlov]

Please, can sombody give an example of input and correct output for this problem?

Thanks in advance!

[shuniu]

I used double in my Java program, got WA, I wonder if there is precision error. Here are some of my IO, please tell me if there are errors.

Input:

Code: Select all

100 0
100 5
100 6
100 7
100 10
100 20
100 30
100 40
100 50
100 59
100 60
100 61
100 70
100 80
100 90
100 100
-1

Output:

Code: Select all

0.0000000
0.0000000
0.0000001
0.0000014
0.0002656
0.1134627
0.6651364
0.9768651
0.9998338
0.9999998
0.9999999
1.0000000
1.0000000
1.0000000
1.0000000
1.0000000

[misof]

to shuniu:
first: I used double too, got AC.
second: 100 0 is not a valid input (zero boxes?)
third: Your outputs are correct, the formatting isn't. Read output description carefully.

[shuniu]

thanks, misof, i get AC after i fix that mistake.
btw, i was just trying to be extra careful on the boundary case (0 box), cause the problem never mentioned m>0, and you know how alot of problems try to screw people on such cases.

[Sedefcho]

INPUT

Code: Select all

50 12
100 99
100 100
90 11
29 13
55 52
47 9
98 96
-1

OUTPUT

Code: Select all

Case 1: 0.1476651
Case 2: 0.9999149
Case 3: 1.0000000
Case 4: 0.0020696
Case 5: 0.7881958
Case 6: 1.0000000
Case 7: 0.0352208
Case 8: 0.9999526

[Larry]

If you had 2 chocolates and 2 boxes:

If they were distinguishable (label them A and B), the unique ways to box them are:
[AB] []
[] [AB]
[A]
[A]

Thus, the probability that at least one is empty is 1/2.

However, if they were not distnguishable, you would have:
[AA] []
[] [AA]
[A] [A]

Thus, the probability that at least one is empty is 2/3.

Isn't this wrong, because the probability of the events in the latter case don't happen with equal probability..?

It's like flipping a two coin at the same time - there are three distinct outcomes - 2H's, 2T's, and a HT, but that doesn't mean each occurs 1/3 of the time..

[pradeepr]

I am using long double to store the probabilities of N chocolates being distributed in to M boxes with out leaving any of them empty.
But I am getting precision problems ...

for input N=100 and M=99 , my code outputs 1.0000000 which actually isn't the case.The logic seems to work as evident from outputs for smaller N and M..

I am attaching the code.. Please help me in figuring out whats wrong with this code...

Code: Select all

[mf]

1.0000000 is the correct answer to seven decimal places for n=100 m=99.

[pradeepr]

@mf thanks a lot.. I was confused by the input outputs given earlier.