Problem Link:
Difficulty:
Easy
Prerequisites:
High School Maths
Problem:
Given n tickets, i^{th} ticket can be labelled
 A_{i} with probability P_{i} percent.

B_{i} with probability 100P_{i} 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 nonzero 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 i1 have been assigned labels.
double solve(int i, bool labelsused[16], double probabilitysofar)
if i == n
return probabilitysofar
double ans = 0
for (l,p) in [(A[i], p[i]), (B[i], 100P[i])]:
if labelsused[l1] == true
continue
labelsused[l1] = true
ans += solve(i+1, labelsused, probabilitysofar*p/100.0)
labelsused[l1] = 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:
 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