Traffic Lights (SGU 103)

(As a brief disclaimer, I try to only post problems to which I have discovered a solution entirely on my own. Thus, the more difficult problems from wonderful sources such as USACO and COCI are excluded, but I’d still recommend doing them to anyone.)

In brief summary: we’re given an undirected graph of ~300 junctions and road lengths of ~100 each. We want to get from some junction A to B. There are some extra conditions about how each junction has a light that cyclically flashes between blue and purple over time (e.g. 3s blue, 5s purple, 3s blue, …), and how you can only go between some junction M to N if they happen to be of the same color at that time (naturally, you can wait at the light until the lights coincide). It is worth noting that a light won’t stay the same color for more than 100 units of time.

First, we note that if we can ignore the lights (e.g. if lights are synced, so we have no trouble traveling anywhere anytime), this question reduces to a classic single-source-shortest-path problem, which we can solve with Dijkstra’s. Thus, we have a factor of $O(V^2 \log V)$ in the most common implementation, so ~1 million operations. But clearly, we can’t always ignore the lights!

We then think: say we’re stuck at some point A at time T, and we really want to get to B. When is the earliest we can do so, if we can ever do so (since if one is blue when the other is purple, you are stuck forever)? It turns out that if we have such a function and it’s reasonably fast, we can relatively easily alter Dijkstra’s to accommodate for the virtual “wait times”. So if we use an array to store the time to get from the source to any other point, we simply add in the wait times in addition to the traveling times, and thus find the overall time.

But alas, this function is quite tricky to implement. We first note that if we model the cycle of flashes as a line, we can calculate the “position” of the light when we first arrive at a point with a bit of math. For example, if we have a blue light every m seconds, and purple light every n seconds, we get:

We can essentially do operations in $\mod (m+n)$, and checking the color of a position becomes very easy. The runtime of the naive solution is clear: we label light A pos1 (the initial location of A on the line), label light B pos2, then loop $O((m+n)^2)$ times, since there are about $(m+n)$ possibilities for pos1 and about $(m+n)$ possibilities for pos2, we’ll encounter every possibility in that many iterations (as we’re guaranteed a cycle after some point). But this will take about 40 000 operations in the worst case, which should run out of time in a reasonable judge when coupled with the Dijkstra’s runtime (note: it doesn’t on SGU. Pshhh, these test cases are soft).

Now here’s the interesting insight. After some thought, we realize that, after about a loop or two around one line, the earliest time we have both being the same color is when one just switched to that color. Take a moment to think about this. This means that if we assume, say, the best time is when A turns blue, we can find when that happens just by adding (A-line-length) to the position of B (so position of A keeps going back to when-it-turned-blue). Since there are only about $(m+n)$ distinct positions for B, it’s a $O(m+n)$ function if we stop at cycles. Essentially, there are four symmetric cases we need to implement, and a loop or two at the beginning (in case it was already matching or something). This leads to a $O((m+n) * V^2 * \log V)$ algorithm overall, which is about the best you can reasonably do.

Final solution (uncommented)

Essentially, the key to solving this type of problem is to see the big picture (with the Dijkstra’s algorithm), be able to restructure data in more digestible ways (e.g. the “line” analogy to reduce a time-based event to modulo math), and have a bit of mathematical sense to accurately figure out runtimes. Oh, and the flash of inspiration to note only a finite number of points (i.e. $O(1)$ points instead of $O(n)$ points) are relevant overall.

Note: the problem also asks for a reconstruction of the path. In competitive programming, a common method is to use a predecessor array, which basically answers: what was the last point I visited to compute the optimal distance from A to X?