LEEXAMS - Editorial

editorial
, , , , ,
1

Problem Link:

Practice

Contest

Difficulty:

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[16], 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[16] = {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

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/LEEXAMS.cpp)  
 2. Sergey's

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/LEEXAMS.cpp)

Editorialist’s Solution:

Can be found here

4 Likes
2

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??

3

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[17]={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
4

damn!!
i wrote the same code but missing

labels-used[l-1] = false

line. :frowning:

5

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
6

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

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

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

8

How can above statement print -0.000 ??

9

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

10

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

11

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

12

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

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

13

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]