TopCoder problem "BikeRace" used in SRM 228 (Division I Level One , Division II Level Two)

Problem Statement

    A pursuit race is run on a circular track. The participants each start at the same start line, but each at a different time based upon their performance in earlier races. Whenever a rider is passed by another rider, he is eliminated from the race. If a previous rider circled the track and reached the start line at or before the time when a contestant is scheduled to start, then that contestant is eliminated at the time the rider reached the start line.

Suppose that the racers each go at a constant speed. Create a class BikeRace that contains a method eliminated that is given track, the length of the track, String[] name, the names of the contestants, a int[] start, the start times of the contestants, and a int[] speed, the speeds of the contestants. It returns a String[] giving the names of the eliminated contestants in the order in which they were eliminated. In case of simultaneous eliminations, list the simultaneously eliminated riders in alphabetical order.

track is in feet, speed is in feet per second, and start is in seconds. Element i of speed, start, and name applies to contestant i.



Parameters:int, String[], int[], int[]
Method signature:String[] eliminated(int track, String[] name, int[] start, int[] speed)
(be sure your method is public)


-track will be between 1000 and 5000 inclusive.
-name will contain between 2 and 50 elements inclusive.
-name, start, and speed will all contain the same number of elements.
-Each element of name will contain between 1 and 50 characters inclusive.
-Each character in each element of name will be an uppercase letter 'A'-'Z'.
-The elements of name will be distinct.
-Each element of start will be between 0 and 1000 inclusive.
-The elements of start will be distinct.
-Each element of speed will be between 1 and 50 inclusive.


{ 0, 100,180} 
{30, 30, 30} 
Returns: { "C" }
Rider A starts at time 0 and goes 3000 feet before B starts at time 100. A passes the start line at time 160, before C can start, thereby eliminating C. But B and A can never catch each other since they are going the same speed so they are never eliminated.
{"BO","JO", "AL"}
{ 10,  0,    15 } 
{ 12,  2,    10 } 
Returns: { "JO",  "AL" }
JO goes 20 feet (10 seconds at 2 feet/sec) before BO starts at time 10. JO is eliminated at time 12 since both JO and BO have gone 24 feet. AL starts at time 15 but is eventually caught by BO since BO is going at a higher speed.
Returns: { "BOBO",  "ANNA" }
Returns: { "A",  "J" }
Returns: { "BILL",  "JIMMY",  "TOM",  "TOMMY" }
SPEEDY just manages to circle the track before any of the others can start. So the other four are all eliminated at the same time, and are listed in alphabetical order.

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Simple Math, Simple Search, Iteration, Simulation, Sorting