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

×

FRNDMTNG - Editorial

PROBLEM LINK:

Practice
Contest

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

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 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

alt text

Time Complexity:

$O(1)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution
Tester's solution

This question is marked "community wiki".

asked 15 Jun '15, 13:16

balajiganapath's gravatar image

6★balajiganapath ♦♦
75542742
accept rate: 77%

edited 20 Jun '15, 00:15


11

Cakewalk ???? Seriously ???

link

answered 15 Jun '15, 15:14

vpyati's gravatar image

3★vpyati
1545
accept rate: 0%

edited 15 Jun '15, 15:15

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) rishabhprsd72★
3

Well , this question was totally related to JEE mathematics ,I guess... Infact,I had solved it!

(15 Jun '15, 17:05) anh1l1ator6★

@shashaa35 see this link

link

answered 15 Jun '15, 21:28

shivam9753's gravatar image

4★shivam9753
696112
accept rate: 17%

@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!!

link

answered 15 Jun '15, 18:33

varunn123's gravatar image

3★varunn123
412
accept rate: 0%

edited 15 Jun '15, 19:02

programming is basically mathematics and this problem proves it clearly

link

answered 15 Jun '15, 21:49

bikashsingh's gravatar image

2★bikashsingh
152
accept rate: 0%

2

Maths is indeed important but go out and see the real world. Programming != Maths :)

(03 Jul '15, 02:23) amitt0012★

@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

link

answered 15 Jun '15, 22:31

varunn123's gravatar image

3★varunn123
412
accept rate: 0%

edited 15 Jun '15, 22:34

(@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.

link

answered 18 Jun '15, 02:55

arcticblue's gravatar image

4★arcticblue
812
accept rate: 18%

edited 19 Jun '15, 02:43

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

link

answered 15 Jun '15, 15:17

aniruddha_paul's gravatar image

2★aniruddha_paul
35213
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) eknoor2924★

Try imagining Pauli's exclusion principle. ;)

(20 Jun '15, 23:22) mb13mb13_19951★

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.

link

answered 15 Jun '15, 15:21

ladpro98's gravatar image

5★ladpro98
1
accept rate: 0%

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

link

answered 15 Jun '15, 15:25

vpyati's gravatar image

3★vpyati
1545
accept rate: 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

link

answered 15 Jun '15, 15:53

varunn123's gravatar image

3★varunn123
412
accept rate: 0%

edited 15 Jun '15, 15:55

I did used the area concept but bam! WA.

link

answered 15 Jun '15, 16:34

beshamberc's gravatar image

2★beshamberc
11
accept rate: 0%

I don't agree it was a cakewalk. It required case analysis and a proper implementation to get A.C.

link

answered 15 Jun '15, 16:51

apptica's gravatar image

5★apptica
949210
accept rate: 17%

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.

link

answered 15 Jun '15, 18:24

aayushkapadia's gravatar image

6★aayushkapadia
4456
accept rate: 12%

edited 15 Jun '15, 18:38

@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?

link

answered 15 Jun '15, 18:27

thakkarparth07's gravatar image

3★thakkarparth07
1
accept rate: 0%

can anyone please explain the figure!!

link

answered 15 Jun '15, 21:18

shashaa35's gravatar image

4★shashaa35
25114
accept rate: 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.

link

answered 15 Jun '15, 21:28

ar56's gravatar image

3★ar56
-32
accept rate: 0%

We can also solve this by basic probability definition and working a bit on improving the precision. My solution

link

answered 15 Jun '15, 21:33

prabhu_3095's gravatar image

2★prabhu_3095
885
accept rate: 14%

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!

link

answered 15 Jun '15, 21:40

dajoker's gravatar image

2★dajoker
11
accept rate: 0%

Area S1 and s2 why?? We have to ignor all the points on X=Y line or what??

link

answered 15 Jun '15, 22:28

code01aviraj's gravatar image

1★code01aviraj
1
accept rate: 0%

Area S1 and s2 why?? We have to ignor all the points on X=Y line or what??

link

answered 15 Jun '15, 22:28

code01aviraj's gravatar image

1★code01aviraj
1
accept rate: 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.

link

answered 16 Jun '15, 06:57

arcticblue's gravatar image

4★arcticblue
812
accept rate: 18%

edited 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

link

answered 16 Jun '15, 09:26

dollarakshay's gravatar image

4★dollarakshay
17617
accept rate: 4%

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!

link

answered 17 Jun '15, 00:44

rahulkhairwar's gravatar image

4★rahulkhairwar
111
accept rate: 0%

@rahulkhairwar this is a question which has area consideration. But to understand why it happened you may have look at this link

link

answered 17 Jun '15, 09:30

apptica's gravatar image

5★apptica
949210
accept rate: 17%

Any better explanations? Please help!

link

answered 18 Jun '15, 02:11

radeonguy's gravatar image

1★radeonguy
1449
accept rate: 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 ?

link

answered 18 Jun '15, 17:26

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

@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.alt text

link

answered 18 Jun '15, 22:07

apptica's gravatar image

5★apptica
949210
accept rate: 17%

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,,,,,

link

answered 21 Jun '15, 19:25

rohitangira's gravatar image

3★rohitangira
939
accept rate: 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

link

answered 21 Jun '15, 19:52

apptica's gravatar image

5★apptica
949210
accept rate: 17%

edited 21 Jun '15, 19:54

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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