We make one key observation: Dankey Kang should never stop in the middle of the road unless he is facing a red light. This is because any time spent waiting can be spent moving and potentially waiting afterward instead. This greedy decision will never incur additional negative consequences.

Using this knowledge, we can simply simulate Dankey Kang's trip if he initially waits ~0 \dots T-1~ seconds and output the best time found.

Time Complexity: ~\mathcal{O}(NT)~

To solve the second subtask, we first note that we can simplify the traffic lights by finding the time interval in which the light is green, with respect to 0 seconds. If a light's offset is ~o_i~, then we can say that it is green in the interval ~[-o_i,-o_i+g_i) \pmod{T}~. Note that these times should be non-negative.

Then, we realize that many initial start times are unimportant. In fact, there are only ~\mathcal{O}(N)~ initial start times that need to be checked. For each traffic light, let ~[l_i,r_i) \pmod{T}~ be the interval of time where the light is red. Then, we need to make sure to start at time ~l_i-1-cumulativeDistance(i)~. This value should be non-negative and under modulo ~T~. A proof of why only this time is necessary to check is left to the reader as an exercise (hint: if an initial time ~x~ is not checked, then no light turns red at time ~x+1~).

Time Complexity: ~\mathcal{O}(N^2)~

To solve the final subtask, we need to make a few more observations.

First, if Dankey Kang is forced to stop at some traffic light, and then starts immediately when it turns green, the next traffic light he will stop at, if any, will always be the same. Therefore, for each light and starting time, there must be a set amount of time it takes to reach the end. We can run an ~\mathcal{O}(N^2)~ algorithm to find the next light Dankey Kang will stop at if he starts moving from a given light when it turns green. However, this is too slow, and we will seek to improve this time complexity.

Second, we can "ignore" the distance in between each light. The distance simply adds unavoidable time to Dankey Kang's trip, which can always be factored into our answer afterward. However, each light's green time interval needs to change depending on its cumulative distance from the start. Suppose travelling to light ~i~ takes ~t~ seconds. Then, no matter what Dankey Kang does, there will be an additional offset of ~t~ seconds in light ~i~'s cycle. Thus, each light's green interval is now ~[-o_i-cumulativeDistance(i),-o_i-cumulativeDistance(i)+g_i)~. Once again, remember that these times should be computed modulo ~T~, and should remain non-negative.

Now, we consider the intervals where each light is red. If we plot these intervals on a graph of time ~\pmod{T}~ vs. light number, then we can see that we can go through a consecutive interval of lights non-stop if we can draw a horizontal line without touching an interval. Now, following the idea for subtask 2, we want to find the next light that Dankey Kang must stop at if he starts moving from a light as soon as it turns green. To visualize, we draw a horizontal line from the endpoints of each red interval and the important starting times until we hit another red interval or if we cross the ~N^{th}~ light.

We can use a data structure that can support insertions, deletions, and lower bound queries in sub ~\mathcal{O}(N)~ time. C++ set and map and Java TreeSet and TreeMap support these operations in ~\mathcal{O}(\log N)~ time each. We want to process the intervals in order of increasing light number, and we can use a line-sweep idea. For each interval, we can use lower bound on the data structure of intervals to find which previous intervals are stopped by the current one. Then, we delete those intervals and insert the current interval into the data structure. We also need to employ a similar method using the starting times. Be wary that time wraps around ~T~.

Bonus: If Dankey Kang leaves at a random starting time, you can find the first location that Dankey Kang will stop at in ~\mathcal{O}(\log N)~. Afterwards, you can compute the travel time in ~\mathcal{O}(1)~.

Time Complexity: ~\mathcal{O}(N \log N)~