FRNDMTNG - Editorial

editorial
, , , , ,
#1

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

1 Like
#2

Cakewalk ??? Seriously ???

11 Likes
#3

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

#4

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.

#5

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

#6

@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

#7

I did used the area concept but bam! WA.

#8

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

#9

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.

#10

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

#11

@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
#12

can anyone please explain the figure!!

#13

@shashaa35
see this link

2 Likes
#14

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.

#15

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

#16

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!

#17

programming is basically mathematics and this problem proves it clearly

1 Like
#18

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

#19

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

#20

@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