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.

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

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

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

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

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

3 Likes

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