You are not logged in. Please login at www.codechef.com to post your questions!

×

REL205 - Editorial

PROBLEM LINK:

Practice 
Contest

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.

This question is marked "community wiki".

asked 12 Nov '16, 23:01

black_well's gravatar image

5★black_well
292
accept rate: 33%

edited 12 Nov '16, 23:02

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×9,473
×675
×296
×10

Asked: 12 Nov '16, 23:01

Seen: 96 times

Last updated: 12 Nov '16, 23:02