In reality this problem isn't a maze at all, but a wrapper for a shortest-path problem. And, what a wrapper it turns out to be! When first considering this problem, all three regional chief judges had responses similar to: "Yeah, a nice wrapper on shortest path. Just find the intersections, build the graph, and run a shortest-path algorithm." When I initially proposed this problem, I categorized it as moderate/difficult.

Then I went to code the solution...

Conceptually the solution for this problem is fairly straightforward. Find all the intersections, then all the distances between all pairs of intersections on the same object, throw all the distances into an adjacency matrix, and run a shortest-path algorithm. The devil's in the implementation on this one, though! The most difficult part of this problem is construction of the graph. Finding the intersections is just straightforward math (though we expect having to deal with circles rather than just lines---a variation we did consider---will knock out quite a few teams), but keeping track of them all along with what objects they lie on is challenging. Even taking smart advantage of Java Collections, a LOT of code (in terms of a programming contest) is required to build the graph. Once it's built, though, the actual search for the answer is trivial. In my maze.java solution there are about eighty lines of code to build the graph, about fifty lines of code for the required math, and four lines to compute the shortest paths! The code is well-commented, so have a look there if you're interested in the details of the solution.

The length of the solution, the challenge of thinking through what it takes to build the graph, and the somewhat challenging math lead me classify this problem as this year's killer. It's certainly harder than it at first appears, but it's definitely solvable, and I hope to see at least one team solve it.

Don't miss taking a visual look at the test cases! Compile and run the guimaze.java program. If you run it without a command-line argument it will read the same maze.in file that the main solution program reads, but you can pass it a filename and it will read that file instead, so if you want to play with your own input sets, just create your own input file. I wrote this gui wrapper around the main solution because I needed to be sure that the official test cases didn't violate any of the input specifications laid out by the problem statement. Not only does guimaze.java display graphical representations of the input sets, it also outputs messages to stderr if it detects what appear to be problems with the test case. Run the guimaze.java program against the errors.in input file to see that guimaze.java does in fact detect such problems.

A note about running times: In the judging folder is an alternate solution, lc.java, independently coded by Andy. (We find it nice to have at least two independent solutions to hard problems that agree on the answer set.) The algorithmic approach is virtually the same as my own solution, but the implementation approach is quite different. A surprise gotcha was that the lc.java program took twenty to thirty times longer to execute! Running it through a profiler found the culprit to be the creation of millions of small double[] arrays that quickly get discarded. It's a valid approach to solving the problem, however, so I capped the number of objects at 20 instead of 25 and scaled back the test data a bit. On a 400 Mhz Pentium with 256 MB of RAM, lc.java runs in 0:54.847 on the official maze.in (maze.java runs in 0:05.476). Surely this is far below the specs of any machine that will be used for judging, so the standard policy of any program taking more than 1:00 should stand firm.