PROBLEM LINK:
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
Time Complexity:
O(1)