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

1 Like

Cakewalk ??? Seriously ???

11 Likes

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

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.

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

@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

I did used the area concept but bam! WA.

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

@shashaa35
see this link

2 Likes

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