Problem L of the GCPC 2016 (Maze)

This past Saturday, two friends and I took part in the German Collegiate Programming Contest. Since none of us actually trained much beforehand and it was the first ICPC-like programming contest for two thirds of the team (me included), we were not one of those teams that managed to solve almost all problems, but ended right in the middle of the ranking with a total of three solved problems (even though we were really, really close to solving four 😉 ).

Nevertheless, I’d like to share some insights into one of the problems the organizers of the GCPC came up with. I really like it because there is a beautiful algorithm that you can apply to it and (mostly because) it is somewhat StarTrek related 😉 . The problem I’m talking about is problem L of the GCPC 2016 which you can find in this PDF. The solution of course contains spoilers, so if the problem statement makes you curious I’d recommend giving it a try first and coming back later to see if you found a more elegant solution. If you are a TUM student, you can even run it against all the tests that were used in the contest on TUMJudge.

Continue reading Problem L of the GCPC 2016 (Maze)