The goal is to find the maximum speed (off speeding) that will allow you to cross all the traffic lights to green.
Warning: You can not cross a traffic light the second it turns red !
Your vehicle enters the zone directly at the speed programmed on the cruise control which ensures that it does not change anymore.
Line 2: An integer lightCount for the number of traffic lights on the road.
lightCount next lines:
- An integer distance representing the distance of the traffic light from the starting point (in meters).
- An integer duration representing the duration of the traffic light on each color.
A traffic light alternates a period of duration seconds in green and then duration seconds in red.
All traffic lights turn green at the same time as you enter the area.
1 ≤ lightCount ≤ 9999
1 ≤ distance ≤ 99999
1 ≤ duration ≤ 9999
Solution
When we visualize the problem in a space-time diagram, we see that moving with constant speed increases the position linearly. We now need to find the steepest curve that passes a green phase on each traffic light.
Since the light switches periodically we could use a sine wave and interpret the phase with negative output as red and positive as green. However, this introduces a lot of rounding errors. Another way is to solve the problem with integers only. Using a congruence relation modulo \(m\), where every \(m\)th element will land in the same class. But we want only two classes with a fixed period. Thats why we double the phase to a red-green cycle which gives \(m=2d\) for the given duration \(d\). Now the half of these classes are red and the other half is green.
The second observation is that the time \(t_k\) needed for the \(k\)th section is \(t_k=\frac{s_k}{v}\) with the length of path \(s_k\) and speed \(v\). Since the speed is given in km/h, we convert it to m/s first. Combining both ideas leads to:
\[p_k\equiv\frac{s_k}{\frac{1000}{3600}v}\equiv \frac{18s_k}{5v}\pmod{2d_k}\]
Now we select half of the time by stating \(p_k<d_k\), which represents the green phase. Solving the modular congruence under rational numbers gives
\[(18 \cdot s_k) \bmod (2\cdot 5 \cdot v \cdot d_k) < (5 \cdot v \cdot d_k)\]
The easiest way to solve the problem now is using this inequality and maximize \(v\). To do so, we start with the given maximum speed, check if we can take this speed for every traffic light and as soon as we fail with one, we start from the beginning a little slower.
let speed = +readline();
const lightCount = +readline();
const lights = [];
for (let i = 0; i < lightCount; i++)
lights.push(readline().split(' ').map(Number));
const isRed = (speed, dist, dur) =>
(18 * dist) % (10 * speed * dur) >= (5 * speed * dur);
for(let i = 0; i < lightCount; i++) {
if (isRed(speed, lights[i][0], lights[i][1])) {
speed--; // Reduce speed
i = -1; // Start again
}
}
print(speed);This works since we scan over every possible speed and check for a functioning path through the traffic lights. As soon as the loop finishes once, the loop ends. However, the overall running time is \(O(nv)\). By solving it with Chinese remainder theorem, a little improvement could be achieved but the problem that needs to be solved is eliminating the inequality. Another idea to improve the performance is not decrementing speed only once for each red light, but for the whole time until this light gets green again. Since \(p_k\) is the position in the red-green time window, it can be used as an offset to the next green phase.