 Practice

Contest

Easy

# Pre-requisites:

High School Maths

# Problem:

Given n tickets, ith ticket can be labelled

• Ai with probability Pi percent.
• Bi with probability 100-Pi percent.
Find the probability that all tickets get distinct numbers.

# Explanation:

The most important thing to notice about this problem was that while there can be upto 50 tickets, at most 16 labels are available. Therefore, by pigeon hole principle, if the number of tickets is more than 16, then at least one label will be shared by two or more tickets. Hence, the probability is non-zero only if n≤16.

Now, it is clear that the number of ways of allotting labels to tickets is 2^n, because each ticket can have one of the two labels. Therefore, we could brute force over all possible allotments of tickets in O(2^n) time, and for each assignment, find

• probability of that assignment
• If the assignment is valid or not
Calculate the sum of probability of all valid assignments, and that is your answer.

Find pseudo code of a recursive implementation of the solution below. There can be many different ways to implement the same thing, as will be apparent in setters/testers/editorialist’s solutions.

``````
// all tickets from 0 to i-1 have been assigned labels.
double solve(int i, bool labels-used, double probability-so-far)
if i == n
return probability-so-far
double ans = 0
for (l,p) in [(A[i], p[i]), (B[i], 100-P[i])]:
if labels-used[l-1] == true
continue
labels-used[l-1] = true
ans += solve(i+1, labels-used, probability-so-far*p/100.0)
labels-used[l-1] = false
return ans
bool labels = {false};
if n<=16
finalans = solve(0, labels, 1)
else
finalans = 0

``````

# Setter’s Solution:

Can be found here

# Tester’s Solution:

1. Mahbub’s
``````
2. Sergey's

``````

# Editorialist’s Solution:

Can be found here

4 Likes

why was I getting segmentation fault in this code

http://www.codechef.com/viewsolution/2632363
??
I mean on my machine it worked ok .Is it possible to get the case for which the code failed??

In this Problem I used the binary representation of a number to get all the combination of given Ai and Bi.
Here is the pseudo code:

taken={0}

for i=0 to i=(2^n) -1:

``````for j =0 to n-1:
k = 1<<j
if(k&j==1)
if(taken[A[j]]==0)
taken[A[j]]=1 and tempans = tempand*P
else:
tempans = 0
break
else:
if(taken[B[j]]==0)
taken[B[j]]=1 and tempans = tempans*(100-p)
else:
tempans = 0
break
ans += tempans``````
1 Like

damn!!
i wrote the same code but missing

``````labels-used[l-1] = false
``````

line. Please try to type conditions more clearly …
Others like me would have mistaken the ( 1<= A,B <=16) as two separate conditions as 1<=A and B<=16.

2 Likes

Got wrong answer because of this (when probability was zero.Just making %d gave AC)!! why ??

``printf("%6.9lf\n",0);``
2 Likes

Maybe you were printing -0.000 for some reason. Should that cause WA in special judge?

How can above statement print -0.000 ??

Editorial for practice problem paying up helped me a lot for taking all the combinations…
link to the tutorial is paying up
…my solution is solution

me too used the the same method which i have learned from http://www.codechef.com/wiki/tutorial-paying

Wow! I love that clever application of the pigeon hole principle!

hi… what does for(l,p) implies in the above editorial.

for (l,p) in [(A[i], p[i]), (B[i], 100-P[i])]:

I am iterating over a list of pairs. It is same as

``````
Arr1[] = {A[i], B[i]};
Arr2[] = {p[i], 100-p[i]};
for j = 0; j<2; j++
l = Arr1[j]
p = Arr2[j]

``````
//