You are not logged in. Please login at www.codechef.com to post your questions!

×

# FRNDMTNG - Editorial

Author: Vasia Antoniuk
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima

Easy

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 EXPLANATION

Suppose $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 75542742
accept rate: 77%

 11 Cakewalk ???? Seriously ??? answered 15 Jun '15, 15:14 3★vpyati 154●5 accept rate: 0% Cakewalk might be a relative term (here), for those who have excellent programming skills it may be a cakewalk for them but for an average coder it was not!! (15 Jun '15, 15:29) 3 Well , this question was totally related to JEE mathematics ,I guess... Infact,I had solved it! (15 Jun '15, 17:05)
 2 @shashaa35 see this link answered 15 Jun '15, 21:28 696●1●12 accept rate: 17%
 1 @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 41●2 accept rate: 0%
 1 programming is basically mathematics and this problem proves it clearly answered 15 Jun '15, 21:49 15●2 accept rate: 0% 2 Maths is indeed important but go out and see the real world. Programming != Maths :) (03 Jul '15, 02:23) amitt0012★
 1 @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/chance-of-meeting-in-a-bar answered 15 Jun '15, 22:31 41●2 accept rate: 0%
 1 (@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 81●2 accept rate: 18%
 0 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 35●2●13 accept rate: 0% 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)
 0 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 5★ladpro98 1 accept rate: 0%
 0 @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 3★vpyati 154●5 accept rate: 0%
 0 @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 41●2 accept rate: 0%
 0 I did used the area concept but bam! WA. answered 15 Jun '15, 16:34 1●1 accept rate: 0%
 0 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 5★apptica 949●2●10 accept rate: 17%
 0 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 445●6 accept rate: 12%
 0 @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 1 accept rate: 0%
 0 can anyone please explain the figure!! answered 15 Jun '15, 21:18 25●1●1●4 accept rate: 0%
 0 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 3★ar56 -3●2 accept rate: 0%
 0 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 88●5 accept rate: 14%
 0 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 2★dajoker 11 accept rate: 0%
 0 Area S1 and s2 why?? We have to ignor all the points on X=Y line or what?? answered 15 Jun '15, 22:28 1 accept rate: 0%
 0 Area S1 and s2 why?? We have to ignor all the points on X=Y line or what?? answered 15 Jun '15, 22:28 1 accept rate: 0%
 0 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. answered 16 Jun '15, 06:57 81●2 accept rate: 18%
 0 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 176●1●7 accept rate: 4%
 0 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 11●1 accept rate: 0%
 0 @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 5★apptica 949●2●10 accept rate: 17%
 0 Any better explanations? Please help! answered 18 Jun '15, 02:11 144●9 accept rate: 0%
 0 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 240●3●9●32 accept rate: 5%
 0 @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 5★apptica 949●2●10 accept rate: 17%
 0 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 93●9 accept rate: 0%
 0 @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 5★apptica 949●2●10 accept rate: 17%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×1,220
×252
×156
×1

question asked: 15 Jun '15, 13:16

question was seen: 6,708 times

last updated: 03 Jul '15, 02:23