I don’t agree it was a cakewalk. It required case analysis and a proper implementation to get A.C.
I calculated answer and printed first 9 digits after decimal point.It gave me WA.
While whwn i printed with 6 digits it got AC???.How is this possible.Procedure for calculating answer
remains same.
ex… my ans =0.000015555 and when to 6 digits it becomes 0.000016 and error
between these is more than 10^-6.
@varunn123, if t1 = t2 = 0, even then it is possible that they meet if both people come at the same time. How can we say that the probability of them meeting is 0 even when t1 = t2 = 0?
@thakkarparth07 here we are dealing with real numbers and not only integers thats why we are using the concept of area here!! we took T1 and T2 drawn a rectangle and considered the square part in that and calculated the area where we get success(success area)!! at t1=t2=0 we get diagonal so area is 0!! look it in this way the success combinations we get in success area is way too smaller than unsuccessful combinations & successful combined so ans tends to 0. this is what i think!!
1 Like
can anyone please explain the figure!!
Why can’t we take the dimensions of the rectangle as T1+t1 and T2+t2? Suppose if the case is 2 6 2 1 and the second person arrives at 3.5 seconds, then also they have a chance to meet…but from your method it doesn’t seems possible.
We can also solve this by basic probability definition and working a bit on improving the precision.
My solution
I came up with a brute force solution.
Haven’t been able to figure out why it doesn’t work though.
Can someone help?
Thanks!
programming is basically mathematics and this problem proves it clearly
1 Like
Area S1 and s2 why?? We have to ignor all the points on X=Y line or what??
Area S1 and s2 why?? We have to ignor all the points on X=Y line or what??
@code01aviraj X=Y line is for test case when t1=0 & t2=0 for rest of cases that is not true
go to this link and u will get the idea
1 Like
The following book has this problem along with a solution to the simple case when both T1 and T2 are equal.
Digital Dice Book.
With this type of problem it is possible to use the Monte Carlo method to generate some more test answers. This is what I used to finally work out the formula needed.
When you see the editorial and you realize the answer was simpler than you ever imagined it to be.
facepalm
how did that figure come? 
the S1 and S2 areas, I mean!
tried a lot to figure it out, but couldn’t get it! 
could someone please explain?
Thanks in advance!
@rahulkhairwar this is a question which has area consideration. But to understand why it happened you may have look at this link
Any better explanations? Please help!
(@radeonguy) I’ll have a go at explaining it, hopefully it’s helpful.
Person A can arrive any time between 0 and T1. They will wait t1 time before leaving.
Person B can arrive any time between 0 and T2. They will wait t2 time before leaving.
There are four cases
Person A arrives, waits and then leaves before person B arrives. So they never meet.
Person B arrives, waits and then leaves before person A arrives. So they never meet.
Person A arrives, waits and person B arrives before A leaves. So they meet.
Person B arrives, waits and person A arrives before B leaves. So they meet.
The first two cases above match the white areas of the diagram in the editorial.
The second two cases match the orange areas.
The middle green line is if they both enter at exactly the same time. (Note it’s a line so there is no area so the chance of this happening is zero. I realise this may seem a little counter intuitive.)
If A comes in at time 0 then he will wait until t1 before leaving.
If A comes in at time 2 then he will wait until t1 + 2 before leaving.
…
If A comes in at time T1 then he will wait until t1 + T1 before leaving.
This is the right most orange area. The middle green line is the time that A comes in between 0 and T1.
So from the above we can see that if B comes in more than t1 time after A then they will never meet, again this is the right hand most white area.
The same thing applies for B coming in. One slight difference is that A can only arrive up to T1 time this is why the left most orange area has a different shape from the right orange area.
So if A and B can only meet in the orange area (S1 + S2) and the total time they can arrive is T1 * T2 then we get the answer shown in the editorial.
It’s probably best to draw out a test case and to use actual values. Grab someones passing code and verify that you get the same results.
If something still doesn’t make sense then please ask. Or if I’ve got something wrong please correct me.
3 Likes
I understand the concept of the area of that graph. I don’t understand the programatic approach provided by author. Can anybody explain it ?