TopCoder problem "KPlanetaryAlignment" used in SRM 414 (Division I Level Three)



Problem Statement

    

A particular star system consists of a single star, with N planets orbiting it. Each planetary orbit is a perfect circle of distinct radius centered on the star and all orbits lie in the same 2-D plane. The planets move along their circular paths with constant speed and planet i completes 1 full orbit in the time given by the absolute value of periods[i]. periods[i] will be positive if planet i orbits clockwise and negative if it orbits counter-clockwise. A k-planetary alignment occurs when an infinite straight line exists, passing through the center of the star and through the centers of at least k of the planets. A N-planetary alignment occurs at time T = 0, i.e., all the planets lie in a line at this time (see notes for clarification). Return the number of distinct times between T1 and T2, inclusive, when a k-planetary alignment occurs.

 

Definition

    
Class:KPlanetaryAlignment
Method:number
Parameters:int[], int, int, int
Returns:int
Method signature:int number(int[] periods, int k, int T1, int T2)
(be sure your method is public)
    
 

Notes

-The constraints ensure the return value will fit in a signed 32-bit integer.
-Alignments can occur with the planets either on the same side of the star or diametrically opposite each other.
-The configuration of the planets at T = 0 (i.e., whether the planets are all on the same side, or some are diametrically opposite) makes no difference to the answer.
 

Constraints

-periods will contain between 2 and 5 elements, inclusive.
-Each element of periods will be a non-zero integer between -100 and 100, inclusive.
-The elements of periods will be distinct.
-k will be between 2 and the number of elements in periods, inclusive.
-T2 will be between 0 and 50,000,000 (5 * 10^7), inclusive.
-T1 will be between 0 and T2, inclusive.
 

Examples

0)
    
{8,40}
2
0
20
Returns: 5
Here, the first planet is rotating 5 times as quickly as the second. Ater 5 seconds, the first will have completed 5/8 of an orbit, while the second will have completed 5/40 = 1/8 of an orbit. They are therefore diametrically opposite and this is the first 2-alignment after time 0. Further 2-alignments happen at T = 10, 15 and 20.
1)
    
{8,24,40}
2
0
20
Returns: 8
With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20.
2)
    
{8,24,40}
3
0
100
Returns: 4
3-alignments of the same set of planets happen at T = 0, 30, 60, 90.
3)
    
{-10,10}
2
2
26
Returns: 10
Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds.
4)
    
{-1,2,3,4,5}
3
10000
50000
Returns: 53333
5)
    
{-1,1}
2
0
50000
Returns: 200001
6)
    
{-2,91,87,77,71}
4
0
50000000
Returns: 1471

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8673

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13505&pm=8673

Writer:

StevieT

Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Problem categories:

Math, Search