TopCoder problem "GreenWave" used in SRM 289 (Division II Level Three)



Problem Statement

    

A new road has been opened. It is L meters long, and it is divided into one-meter sections called positions. There are traffic lights at various positions on the road. If there's a traffic light at position i, it means that a car at position i must wait until the light is green before it can proceed to position i+1. Traffic lights are either red or green, and they change every five seconds.

There are some cars waiting to enter into the road. Each car is one meter long, and there can never be more than one car at a single position of the road. Once a car enters the road it cannot overtake other cars. The cars' speeds are given in the int[] speeds, where the i-th element is the speed of the i-th car. Each traffic light starts out red, but the duration of that first red light varies between one and five seconds, inclusive. Then, the five second cycle starts. The initial red light duration may be different for each traffic light.

Suppose that the road goes from left to right. The cars move as follows:

  • Step 1: Each car already in the road (from right to left) tries to move rightward as many positions as its speed indicates, but it can be blocked by another car or a red traffic light (here rightward means increasing its position).

    Then, if position 0 of the road is free, the car with the lowest index in speeds that has not yet entered the road enters at position 0, without moving.

    This step takes one second.
  • Step 2: The traffic lights are updated, if necessary. This step takes no time.
  • Step 3: If all the cars have left the road, stop, otherwise go to Step 1.

You are given L, the road length, speeds, the speed of each car, and lights, the position of each traffic light. Determine the duration of the first red light for each traffic light that minimizes the total time it takes for all the cars to leave the road (that is, the number of seconds elapsed until the last car leaves the road). Return a int[], where the i-th element is the duration of the first red light of the i-th traffic light. If two solutions give the same time, return the one that comes first lexicographically.

 

Definition

    
Class:GreenWave
Method:getFirstRed
Parameters:int, int[], int[]
Returns:int[]
Method signature:int[] getFirstRed(int L, int[] speeds, int[] lights)
(be sure your method is public)
    
 

Notes

-When a car leaves the road (by moving past the rightmost position on the road), it can no longer block the other cars.
-Solution A comes earlier than B lexicographically if A has a lower value than B in the first position at which they differ.
 

Constraints

-L will be between 1 and 500, inclusive.
-speeds will contain between 0 and 10 elements, inclusive.
-Each element of speeds will be between 1 and 30, inclusive.
-lights will contain between 0 and 5 elements, inclusive.
-Each element of lights will be between 0 and L-2, inclusive.
-All the elements of lights will be distinct.
 

Examples

0)
    
10
{1}
{0}
Returns: {1 }
Second 1: There are initially no cars in the road. Since position 0 is unoccupied, the car is able to enter the road.

Second 2: The traffic light has just turned green. The car can move right to position 1.

Second 10: The car moves from position 8 to position 9 (the last position on the road).

Second 11: The car leaves the road.

1)
    
50
{1}
{4, 5, 6, 7, 8}
Returns: {1, 2, 3, 4, 5 }
2)
    
300
{2, 1}
{16}
Returns: {4 }
When the duration of the first red light is 4 seconds, neither car will ever be blocked by a red light.
3)
    
300
{1, 2}
{16}
Returns: {3 }
Although the second car has to wait for the traffic light for one second, it is fast enough to catch up with the first one.
4)
    
60
{12, 15, 20}
{58}
Returns: {1 }
Remember that once a car leaves the road, it no longer blocks the other cars.
5)
    
340
{16, 15, 29, 7, 9, 15, 2}
{125, 156, 274, 309, 211}
Returns: {5, 1, 1, 1, 1 }
6)
    
494
{11, 7, 11, 6}
{438, 251}
Returns: {3, 1 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9810&pm=5920

Writer:

esteban

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Simulation