Finally contest is over and i was not able to solve this problem.Now after seeing couple of solutions i am really perplexed how solution was so simple.
In short i just wanted to know how ans is : t1/(t1+t2)
Can anyone help me in this…how ??
Thanks.
2 Likes
Hello,
I got the answer only from intuition and all that still confused me for a while was the existence of T4 parameter.
The Try Again ticket has no influence on the answer, simply because you can see that in the end, you either lose or you gain… You can exhaust all Try Again tickets and your probability of winning or losing is still the same…
Same logic went for me on the T4 tickets which are discarded at first… Simply because the probability of winning would change if we got out tickets of type T1 or T2… I can’t explain why this made sense to me, but after working on paper and seeing that T4 < T1+T2 and understanding that all those probabilities would get to sum up to smaller and smaller values, I just had a flash of insight, went for it, and got AC…
I’m also eagerly waiting for the editorial!!!
Best regards,
Bruno
2 Likes
well… i derived it by induction… both t3 and t4 become redundant… try for any value of t1 and t2. Keep t3 constant and replace t4 by t4-1… you ll see answer remains same. Same 4 t4. Both redundant… Hope this helps
1
1 Like
Thanks for your reply and i still believe there must be an reason for this formula.:)Thanks.
Thanx for your ans.
@fiery : There are two parts to the proof .
-
Coins of type 3 don’t matter .
-
Initial draw doesn’t matter .
You can prove both the claims by mathematical induction
Proof 1 :
p(t1,t2,t3) = t1/(t1+t2+t3) + t3 / ( t1+t2+t3) * p(t1,t2,t3-1) . ( Statement 1 )
By induction hypothesis ,
p(t1,t2,t3-1) = t1/(t1+t2) .
which proves Statement 1 gives us assumed formula
Proof 2 :
p(t1,t2,t3,t4) = t1/(t1+t2+t3) * p(t1-1,t2,t3,t4-1) + t2/(t1+t2+t3) * p(t1,t2-1,t3,t4-1) + t3/(t1+t2+t3) * p(t1,t2,t3-1,t4-1) . (statement 2)
By induction hypothesis ,
p(t1-1,t2,t3,t4-1) = (t1-1)/(t1-1+t2)
p(t1,t2-1,t3,t4-1) = (t1)/(t1+t2-1)
p(t1,t2,t3-1,t4-1) = (t1)/(t1+t2)
which proves statement 2 gives us assumed formula .
24 Likes
Thank you so much sir.
2 things you must consider.
- T4 number of cards plays no significance here since either you take 1 or 2 or n number of cards the probability of the box remains same. And also, T4 < T1+T2 then it doesn’t effect the box probability.
- Now, in case of T3, you have to retry and at the end you can either win or loose. So, whether you take T3 cards out or not. The final card you are drawing out of the box is either T1 or T2.
So, from both of these cases we can easily conclude that T4 and T3 doesn’t play a role and hence discarded. And final answer would be winning cards/Total number of cards i.e., T1/(T1+T2).
Hope it helps.
1 Like
@fiery,
the logic is split in two parts:
-
t4 has no significance : Note that these tickets are removed randomly, so in some cases the prob of winning will increase and in others it will decrease. Overall, it will have no effect. I was satisfied with this intuition.
-
t3 has no significance : I actually worked this out mathematically. Let r denote the total number of tickets then we can get,
P[win] = (t1/r)(1 + t3/(r-1) + t3* (t3-1)/((r-1)*(r-2)) + …
P[loss] = (t2/r)(1 + t3/(r-1) + t3* (t3-1)/((r-1)*(r-2)) + …
Note that the big multiplicative term is same in both and can be replaced by L.
Also P[win] + P[loss] = 1
So, we have
P[win] + P[loss] = (t1/r + t2/r) * L
1 = (t1/r + t2/r) * L
L = r/(t1 + t2)
We can substitute this value of L back in P[win],
P[win] = (t1/r)* (r/(t1+t2))
P[win] = t1 / (t1+t2)
13 Likes
Thank you all for answering.Finally i got it.
@s24w It is induction hypothesis. It is clear that p(t1, t2, 0) = t1 / (t1 + t2). Then assuming that we already prove p(t1, t2, t3 - 1) = t1 / (t1 + t2) we prove this for p(t1, t2, t3). This is how mathematical induction works
1 Like
Just a short comment. With the initial constraints (T4 < T1 + T2 + T3) T3 does matter when computing the probability. What mattered in that case was the fact that there is a non-zero probability of obtaining only T3 tickets after removing the T4 tickets.
I was making lots of submissions and I was always getting wrong answer. Then I tried the “dumb” version of outputting T1/(T1+T2) which magically worked. However, I wrote an email to the admins with my observation which was forwarded to the problem setter (as far as they told me). The end result was that the test cases were changed in order to have T4 < T1 + T2 in each test case (so that T1/(T1+T2) was always the correct answer). A nicer way to handle this would have been, in my opinion, to keep the initial constraints (T4 < T1+T2+T3) and find a way to properly solve the problem even when T1+T2 <= T4 < T1+T2+T3 (my initial solution was correct for these cases, too, but not optimized enough - i.e. there exist test cases with T1+T2 <= T4 < T1+T2+T3 on which my initial solution would get TLE - I was going to try to optimize it later, but it turned out that it wasn’t necessary anymore…)
7 Likes
Sir your comment make me to feel that i didn’t understand the solution properly. So can you please elaborate with constraints (T4 < T1 + T2 + T3) how T3 does matter when computing the probability??.Anyways thanx for sharing this.
1 Like
Suppose we solve the case 4 7 1 2 by conditional probability. Won’t we get a different answer than 4/11 ?
I had solved it using combinatorial approach. Let W(Win), L(Lose), TA(Try Again) symobol represent T1, T2, T3 type tickets and T1 + T2 + T3 = T ie total tickets. Now consider a general permutation of T tickets [W W L TA … TA W W L], so Artem will win only when (T4+1)th position is W or TA W or TA TA W etc. Since all these case are mutually exclusive we only have to find probability in all these cases and add them to get the final answer.
Total permutation(TP) = (T!)/(T1!T2!T3!)
N( W in T4+1 th place) = (T-1)!/((T1-1)!T2!T3!)
N( TA W in T4+1 and T4+2 th place) = (T-2)!/((T1-1)!T2!(T3-1)!)
N( TA TA W in T4+1, T4+2 and T4+3 th place) = (T-3)!/((T1-1)!T2!(T3-2)!)
Generalizing it when i TA tickets and 1 W ticket is used
N(TA i times and W in TA+i th place) = (T-i-1)!/((T1-1)!T2!(T3-i)!)
Final probability =![alt text][1]
Now T4 < T1+T2 so min(T3,T-T4) = T3
P=![alt text][2]
@fiery So, here we see that the constraint T4 < T1+T2 is crucial because if this is not the case then minimum(T3,T-T4) can be T-T4 also and sum would then contain some factorials. I have computed that in wolframalpha see this and the solution will give TLE.
[1]: http://discuss.codechef.com/upfiles/temp.jpg
[2]: http://discuss.codechef.com/upfiles/temp.png
6 Likes
i observed the question… saw that every-one was getting a soln. in 0.00 sec
so the solution to the problem would be rather simple , than complex NcR calculations…, moreover, it can be seen that with a bit of observation that the soln. T1/(T1+T2) works…so i got lucky! :), submitted and got accepted.
1 Like
Its basically uses “Theorem of total probability”
If we assume,
Let P(A)= Probability of Artem wining.
P(A/C[i])= Probability that Artem wins given that Chef pick ticket of type T1,T2 and T3.
P(C[i])= Probability of Chef picking ticket of type T1,T2 and T3.
So according to theorem of total probability,
P(A) = P(A/C[1])*P(C[1]) + P(A/C[2]) * P(C[2]) + P(A/C[3]) * P(C[3]).
remember its a summation but here i varies from 1 to 3 respectively.
And T4 was given just for diversion
Theorem of Total probability is a very basic and important theorem of probability very much used in Bayesian Learning.
@i_wanna_rokk, no
if we have the test case (4,7,1,2)
then t1=4,t2=7,t3=1
So,P(A/C[1])= 4/12 * 3/10,
P(A/C[2])= 7/12 * 4/10 and
P(A/C[3])= 1/12 * 4/11.
So as per Theorem of total probability,
P(A) = 4/12 * 3/10 + 7/12 * 4/10 + 1/12 * 4/11 = 12/33 = 4/11.
which is the reqd probability of Artem wining.
and picking any ticket i.e t1,t2 and t3 by Chef are mutual exclusive events,so above formula is mathematically sound and valid.