46th ICPC World Finals
Problem authors:
Matthias Ruhl and the World Finals judges
Solved by 92 teams.
First solved after 31 minutes.
Shortest team solution: 668 bytes.
Shortest judge solution: 464 bytes.
Constructive problems such as these have many different approaches. Here is one approach by one judge. Any closed loop must have an even number of curved track segments and straight track segments, so we can start by making both even. There are then three basic cases to handle:
If there are no straight track segments, then we can make one of two “base” tracks shown in Figure 1. You can then use repeated iterations of “RL” on opposite sides of Figure 1b to extend the track by 4 curves at a time, as shown in Figure 1c. Note that there is no way to make a track with exactly 8 curved segments.
(a) Base track: LLLL
(b) Base track: LRRLRRLRRLRR
(c) LRLLRLRLRLLRLLRLRLRL
On the other hand, if there are at least 2 straight track segments, we then branch on the remainder of c (mod 4). Because we have forced c and s to be even, this is either 0 or 2.
Two possible “base” tracks are then shown in Figure 2, and we can extend these figures with 2 straight track segments placed on opposite sides, as well as with the “RL” extensions described above.
(a) LSLLSL
(b) LSLSLLRL
