PROB - Editorial

gamabunta · July 17, 2013, 6:27pm

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

You are given 3 types of tickets.

A tickets of type 1, the winning ticket
B tickets of type 2, the losing ticket
C tickets of type 3, the try again ticket

You take out D tickets from the sealed box containing all the tickets.

Now, you play the following game

Take out a ticket from the box
If the ticket is of type 1, you win. End the game.
If the ticket is of type 2, you lose. End the game.
If the ticket is of type 3, repeat the game from step 1.

QUICK EXPLANATION

The problem was originally posted with the constraint that

D ≤ A+B+C

This meant that the probability that only type 3 tickets remain was non-zero. MugurelIonut pointed out to the us, on the second day of the contest, that his accepted solution gives the wrong answer for cases where

D ≥ A+B

The judge cases indeed had the wrong answers for such cases. We will discuss in the end, what the answer for such cases is and what would the complete solution have been if the constraints weren’t changed and only the test cases were updated.

But, to maintain the difficulty level of the problem (relative to the problem set), we decided to change the constraint on D to

D < A+B

This ensures there is always either a winning, or a losing ticket after removing D tickets from the box.

EXPLANATION

Let us find the answer when D < A+B.

P(a,b,c,d) = probability that you win if you have a tickets of type 1, b tickets of type 2, c tickets of type 3 and you take out d tickets before starting the game. We know that

P(0,0,c,d) = 0, where c > 0 AND d ≤ c
P(a,0,c,0) = 1, where a > 0 AND c ≥ 0
P(0,b,c,0) = 0, where b > 0 AND c ≥ 0
P(a,b,0,0) = a/(a+b), were a > 0 AND b > 0

Now, we will prove by induction, the following hypothesis

Given that either a > 0, or b > 0

P(a,b,c,0) = a / (a + b)

Firstly, we can see that the following holds true in our hypothesis

P(a,0,c,0) = a / a = 1, is satisfied for all a > 0 AND c ≥ 0
P(0,b,c,0) = 0 / b = 0, is satisfied for all b > 0 AND c ≥ 0

Because of our assumption, a > 0 OR b > 0, one of the base cases - P(0,0,c,0) - is no longer applicable, and we do not need to consider it. But the other base cases must be satisfied by our hypothesis

P(a,b,0,0) = a / (a+b), is satisfied for all a > 1 AND b > 1 AND c = 0

The above is of course true. The probability of winning is equal to the probability of picking the winning ticket - otherwise you instantly lose, since there are no try again tickets and you can only pick the losing ticket.

Now let us assume that the hypothesis is true for some c = t.

P(a,b,t,0) = a / (a+b)

Now, for c = t+1

P(a,b,t+1,0) =
    (a / (a + b + t+1))  // if type 1 ticket is selected
  + (t+1 / (a + b + t+1)) * P(a,b,t,0) // if type 3 ticket is selected

P(a,b,t+1,0) =
    (a / (a+b+t+1)) + (t+1 / (a+b+t+1)) * (a / (a+b))

P(a,b,t+1,0) =
    (a / (a+b+t+1)) * (1 + (t+1 / a+b))

P(a,b,t+1,0) =
    (a / (a+b+t+1)) * ((a+b+t+1) / (a+b))

P(a,b,t+1,0) =
    a / (a+b)

Hence, if the hypothesis is true for c = t, it is also true for c = t+1.

Thus, for all c

Given a > 0 OR b > 0

P(a,b,c,0) = a / (a + b)

Now, We will prove using induction, that

Given d < a+b

P(a,b,c,d) = a / (a + b)

First, we can easily see that out hypothesis is correct in the following cases

P(a,0,c,d) = a / a = 1
P(0,b,c,d) = 0 / b = 0

What we need to show that our hypothesis is correct in the base case d = 0.

P(a,b,c,0) = a / (a + b)

But the above is only true when a > 0 OR b > 0. We can see that since d < a+b, we will always end up with either a > 0 or b > 0.

Hence, the hypothesis is true in the base case. Now we move on and assume that the hypothesis is true for some d = t.

P(a,b,c,t) = a / (a + b)

We have to show that the hypothesis is also true for d = t+1.

P(a,b,c,t+1) =
    (a / (a+b+c)) * P(a-1,b,c,t)
  + (b / (a+b+c)) * P(a,b-1,c,t)
  + (c / (a+b+c)) * P(a,b,c-1,t)

P(a,b,c,t+1) =
    (a / (a+b+c)) * ((a-1) / (a+b-1))
  + (b / (a+b+c)) * (a / (a+b-1))
  + (c / (a+b+c)) * (a / (a+b))

P(a,b,c,t+1) =
    (a / (a+b+c)) * (
        (a-1) / (a+b-1)
      + b / (a+b-1)
      + c / (a+b)
    )

P(a,b,c,t+1) =
    (a / (a+b+c)) * (
        (a+b-1) / (a+b-1)
      + c / (a+b)
    )

P(a,b,c,t+1) =
    (a / (a+b+c)) * (
        1 + c / (a+b)
    )

P(a,b,c,t+1) =
    (a / (a+b+c)) * ((a+b+c) / (a+b))

P(a,b,c,t+1) = a / (a+b)

Hence, the answer for the problem for all the inputs provided for this problem is a / (a+b).

Now, let us consider how to use this much information to solve the cases where D ≥ A+B. There are two possibilities we must consider after removal of D tickets

X = There are no tickets of type 1 or type 2
Y = There is at least 1 ticket of type 1 or type 2

We know that

X + Y = 1

total ways for selecting D tickets =
    ^A+B+CC_D

ways for selecting tickets such that
there are no tickets of type 1 or type 2 left =
    ^CC_D-A-B

Hence,

X = ^CC_D-A-B / ^A+B+CC_D

Y = 1 - X

Now, we know the probability of winning if D < A+B is equal to A / (A+B).

We wish to know the probability of winning, given that there is at least one ticket of type 1, or type 2 left at the end of discarding D tickets. This conditional probability can be shown to be equalivalent to the case where D < A+B.

The sequence of discarding tickets doesn’t matter. It only matters, which tickets were discarded.

Since discarding each ticket is an independent event, we calculate the probability of discarding a sequence of tickets by multiplying the probabilities of the selections of the respective type of tickets.

For example, assume A = 10, B = 20, C = 30. Let us consider discarding (Type 1)(Type 2)(Type 1)(Type 3)

The probability would be = (10 / 60) * (20 / 59) * (9 / 58) * (30 / 57)

If we were to instead discard tickets in the order (Type 3)(Type 1)(Type 1)(Type 2)

The probability would be = (30 / 60) * (10 / 59) * (10 / 58) * (20 / 57)

Which is still the same.

This is important because, now given any sequence of discards, we can club all the discards of type 3 tickets to the beginning. Now, the necessary and sufficient condition for us to ensure at least one type 1 or type 2 ticket in the end is

Discard D-A-B+1 type 3 tickets

We can assume that these tickets were discarded in the beginning without affecting the probabiliy of the outcomes. Thus, the conditional probability of winning when there is at least 1 ticket of type 1 or type 2 is equal to the conditional probability of winning when at least D-A-B+1 tickets of type 3 have been discarded. This is equal to

P(A,B,A+B+C-D-1,A+B-1)

Which, by our solution to the problem for a D < A+B is already shown as A / (A+B). Now, we can apply Bayes Theorem and find the actual probability of winning

Y * A / (A+b)

OR

(1 - ^CC_D-A-B / ^A+B+CC_D) * A / (A + B)

Which completes our solution for any D.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

triplem · July 18, 2013, 3:49am

You really don’t need any formulas or induction at all. There are A+B possible options that your last ticket may be. There is no way of distinguishing any ticket from any other ticket during the whole process, so each of these tickets are equally likely. Thus the answer is A/(A+B).

gauravdrocker · July 18, 2013, 3:13pm

Really nice explanation… Even though i got a ac after few tries but i was still not convinced with the formula that i was using … thanks a lot for this explanation… and it again proves that maths is really a saviour when it comes to logical reasoning … thanks man !!

faiz · July 18, 2013, 3:36pm

Man!! its simple concept of "Theorem of total probability"and as picking ticket t1,t2 and t3 are mutual exclusive events.We can simply use this theorem.No need of such tedious,clumsy and long explanation.

P(A) = P(A/C[1)*P(C[1) + P(A/C[2))*P(C[2)) + P(A/C[3])*P(C[3]).

where,P(A)= probability of Artem wining.
P(C[i])= Probability of Chef picking ticket of type i where i varies from 1 to 3.
P(A/C[i])= Probability of Artem wining given chef pick ticket of type i(i varies frome 1 to 3).

Simple enough.

ash1794 · July 18, 2013, 5:51pm

The setter’s solution link is broken.

piyushchauhan · July 21, 2013, 3:51pm

your solution is simple and fair. Thumbs up!

faiz · July 21, 2013, 4:23pm

@piyushchauhan ,yeah and thanks

lalit_horcrux · July 25, 2013, 10:28pm

Why are you considering A,B before removal of D tickets.If we’ve A’ and B’ tickets left after removal , then we’ve A’+B’ possible options.Isn’t it ?

toktuff · November 2, 2013, 8:21am

Nitpicking but if T4 >= (T1+T2+T3) then there are no tickets left and there is no possibility of drawing a winning ticket, hence the probability of winning is 0. (Matter of definition I guess).

Encoding this constraint gave me an error though.

sagar19l22 · December 27, 2016, 6:13pm

Hello Guys…!!

I have this C Code which I wrote for this problem. It runs fine and gives me the right answers in the Dev-C++ Environment and the ideone Environment. But the CodeChef Online Judge says Wrong answer and doesn’t award me points. Can anyone please tell me what is the problem here…??

PS: Code Below

#include <stdio.h>

int main()
{
int T , T1 , T2 , T3 , T4 , noOT ;
float P ;

scanf("%d" , &T) ;

for (int i = 0 ; i < T ; ++i)
{
	scanf("%d %d %d %d" , &T1 , &T2 , &T3 , &T4) ;
	noOT = ( T1 + T2 ) ;
	
	P = (T1 * 1.0)/ noOT ;
	
	printf("%.2f\n" , P) ;
}
}

deepakkuamre · February 21, 2017, 3:39pm

you’ve got to take action yourself
and not listen to other people. Dr DC Shetty like