PROBLEM LINK:Author: Vasia Antoniuk DIFFICULTY:Easy PREREQUISITES:None PROBLEM:What is the probability that two persons meet if one of them comes at any time from 0 to $T_1$, uniformly at random, and waits for $t_1$ units of time while the other person comes at any time from 0 to $T_2$ and waits for $t_2$ units of time. SHORT EXPLANATIONSuppose $x_1$ is the time at which the first person arrives and $x_2$ for second person. Then note that the following inequalities must hold for them to meet: $x_1 \le x_2 + t_2$ and $x_2 \le x_1 + t_1$ See the figure for an example. Now we just have to find the area of the shaded region. That divided by the whole area ($T_1 * T_2$) gives the answer. EXPLANATION:Coming soon Time Complexity:$O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 15 Jun '15, 13:16

@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!! answered 15 Jun '15, 18:33

@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 http://math.stackexchange.com/questions/103015/chanceofmeetinginabar answered 15 Jun '15, 22:31

(@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. answered 18 Jun '15, 02:55

what is the case when both t1 and t2=0??plx explain! in this case as far as my intitution says that they will meet if both comes together but how will we find the probability of meeting together answered 15 Jun '15, 15:17
t1=0 and t2=0 implies they both meet at the same moment. There are infinite moments(real numbers) in a range.So the probability of meeting at exactly same moment is zero
(15 Jun '15, 15:23)
Try imagining Pauli's exclusion principle. ;)
(20 Jun '15, 23:22)

Although the provided solution is great, I do not think the difficulty of the problem is "Cakewalk". I did some sort of cases analysis and quite complicated formulas to deal with it in the contest. answered 15 Jun '15, 15:21

@aniruddha_paul If both t1 and t2 is 0, then the probability is always 0. That is the only subtask I got right :) answered 15 Jun '15, 15:25

@aniruddha_paul at t1=0 and t2=0 the only points satisfying this condition is the points on diagonals. probability will be= area of diagonal/(T1*T2) since the area of a line is 0 we get the ans =0 diagonal of square will be taken look at the diag in editorial answered 15 Jun '15, 15:53

I don't agree it was a cakewalk. It required case analysis and a proper implementation to get A.C. answered 15 Jun '15, 16:51

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. answered 15 Jun '15, 18:24

@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? answered 15 Jun '15, 18:27

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. answered 15 Jun '15, 21:28

We can also solve this by basic probability definition and working a bit on improving the precision. My solution answered 15 Jun '15, 21:33

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! answered 15 Jun '15, 21:40

Area S1 and s2 why?? We have to ignor all the points on X=Y line or what?? answered 15 Jun '15, 22:28

Area S1 and s2 why?? We have to ignor all the points on X=Y line or what?? answered 15 Jun '15, 22:28

The following book has this problem along with a solution to the simple case when both T1 and T2 are equal. answered 16 Jun '15, 06:57

When you see the editorial and you realize the answer was simpler than you ever imagined it to be. facepalm answered 16 Jun '15, 09:26

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! answered 17 Jun '15, 00:44

@rahulkhairwar this is a question which has area consideration. But to understand why it happened you may have look at this link answered 17 Jun '15, 09:30

I understand the concept of the area of that graph. I don't understand the programatic approach provided by author. Can anybody explain it ? answered 18 Jun '15, 17:26

@shubham99 you need to idealise all types of situations to code this program. In the normal case the answer is (total area of rectangle  total area of two triangles )/total area of rectangle but in case when waiting time of one person is greater than the total time then always they will meet. And some cases are referred by the figure i have uploaded. You may see this code for more help. View Code. answered 18 Jun '15, 22:07

need someone help i m not getting thta how thesse two lines has drawn ,,,and on the T1 axis why t2 exist,,,,same with T2,,,,, answered 21 Jun '15, 19:25

@rohitangira Assume that this question had been given that between time [0 T] only integral time intervals are provided then you may have thought easy to implement it. But here there is continuous variation in time interval so you cant do this. So we can represent this using geometric objects. You can read this . Now to geometrically draw any probability situation you need to know what area should be the total possible outcomes and what area will come under favourable outcomes. The area total that is T1*T2 will be total area of all outcomes. Now to draw these lines assume person with T2 reaches at 0 so he will wait only till t2 time. So mark a point at 0,t2. Now assume same person if arrived at time x will wait till time t2 so the time when he leaves will be x+t2 mark a point x,x+t2. Now go on marking few points you see they represent a line with slope 45 degree. Since the data is continuous you cant mark all points so just join the complete line. Repeat whole procedure for the person who can arrive between time [0 to T1]. I hope you will be cleared. Comment for more help answered 21 Jun '15, 19:52
