## 10648 - Chocolate Box

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Virtual GOD
New poster
Posts: 3
Joined: Fri Feb 06, 2004 11:38 am
Location: Ukraine
Contact:

### 10648 - Chocolate Box

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

### 10648 - Chocolate Box

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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
I used "long double" which was enough precision to get an answer. Normal "double" may work as well.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### distinguishability of choclates

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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine
Please, can sombody give an example of input and correct output for this problem?

Thanks in advance!

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm
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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### SAMPLE INPUT / OUTPUT

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

### Re: 10648 - Chocolate Box

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

``````
``````
Last edited by pradeepr on Thu Jul 30, 2009 3:18 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10648 - Chocolate Box

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

pradeepr
New poster
Posts: 21
Joined: Fri May 25, 2007 11:52 am
Location: India

### Re: 10648 - Chocolate Box

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