PROBLEM LINK:
Author: Divyesh Savaliya
Editorialist: Divyesh Savaliya
DIFFICULTY:
Hard
PREREQUISITES:
Math
PROBLEM:
You are given a circle with radius r. Two persons start to travel on this circular path with different speed and may be different direction also. You are given the radius of the circle and speed of both persons. Speed will be positive in clockwise direction, and negative in anticlockwise direction. Print the number of distinct points, at which they will meet on the circle. If both persons are travelling with the same speed print “INF”.
EXPLANATION:
There is no need of Radius of the circle.
Suppose the circumference of the circular track is D
Speed of A is |Va|. Time taken by A to cover distance D is ta.
Speed of B is |Vb|. Time taken by B to cover distance D is tb.
So, relative speed between them is Va−Vb
Now this is important. A and B will start from the starting point and after a certain time passes they will meet again at the starting point. This time depends on their relative speed. It will be the LCM of their individual times,ta and tb. So at that time, both A and B will be exactly at the starting point again. In this time period they may meet at any number of points which we have to find out.
(Note: After they meet at the starting point again, the cycle continues and they will keep meeting at the exact same points.)
Time taken by both of them to meet again at the starting point:
T1 = LCM (ta,tb) = LCM (D/|Va|, D/|Vb|) = D / GCD (|Va|, |Vb|)
Suppose they meet n times in time T1. So time in between their consecutive meets is, T2 = (T1/n). This time can be calculated by calculating the time taken to meet for the first time after starting. Va−Vb is their relative speed.
So,Time taken by them to meet for the first time, T2 = ( D / (|Va−Vb|) )
Dividing T1 by T2, we find:
n = (T1/T2) = ( |Va−Vb| / GCD (|Va|,|Vb|) )
Time Complexity is same as time complexity of Euclidean GCD algorithm.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.