November 15, 2018 Introduction to the Marathon Finals

Topcoder Open onsite competition kicked off on Wednesday morning with two contests, one of them the Marathon Finals. I wrote the problem the finalists are working on, and so far everything is peaceful and quiet, so I can take some time to tell you more about the problem.
The aptly named VanishingMaze problem lets you navigate a maze of tiles which disappear as you walk on them. The tiles have numbers on them, and your goal is to visit tiles with numbers 1, 2, 3, and so on, until the maximal number you can reach. The catch is, once you’ve visited a tile number X, you can safely step on tiles with numbers less than or equal to X, but numbers X+2 and greater will disappear as you step on them – and you can’t visit those cells again. On the other hand, you only get points for tiles which you made disappear. There is a multiplier indicating when you’ve destroyed each of the tiles (later in the route is better), and another one indicating what percentage of the goal you’ve accomplished in the end; see the problem statement for the details.
Here is a short animation which shows a path for a simple example. Note the red question marks – they indicate wildcards, a special type of a tile which turn into whichever number you need next when you step on them.

For larger cases, you’ll need to maintain a careful balance between keeping a lot of tiles to be able to walk the maze on later stages and to reach more numbers, and destroying them at just the right time to get the most of the score. The wildcard tiles present a separate challenge – should you use them as soon as you can, since you can’t destroy them to get points, or should you save them until they are right next to you and all other goal tiles are far away?
You see that this task is fairly different from what we’ve done for the finals previously. It has zero uncertainty, and you’re given all information you need right away. The problem used to be inspired by a certain board game, but in the three weeks we’ve been working on the problem (together with JacoCronje and gorbunov) the original idea changed so much that it’s perfectly unrecognizable (other than the “You are exploring a maze…” part). I still hope to evolve the original idea into a different match (non-TCO one), in which the randomness would be less important, so I apologize for not telling you everything about the problem the finalists could have faced instead of the one they are facing 🙂
You can hear more about the Marathon finals today in the live broadcast; I’m really curious about what approaches the finalists will come up with. Stay tuned!