An 8-connected day

TopCoder Open 2015 Finals concluded yesterday (problems, results, also on the left, editorial, discussion). This round had a few extremely nervous moments and a happy ending. It started in a usual manner with a 250 that's not difficult algorithmically but requires careful coding. After submitting it in about 10 minutes, I had to choose whether to go for the 600 or for the 1000. Without tourist in the final round my motivation for alternative strategies was much weaker, as increasing the variation at the expense of the expectation was not desirable. Kuniavski has submitted the 250 with higher score than myself, so there was still some motivation to go for the 1000, but I've still decided to go with the 600 hoping to beat kuniavski by solving it faster than him. This problem has later resolved itself because he has resubmitted his 250 for a much smaller score.

That's where things stopped going so smoothly. For quite some time, I had no idea how to solve the problem. After experimenting with a few testcases on paper, I had a plan: each 8-connected set of obstacles has to have a very specific form, and we can determine the direction of jumps along its boundary uniquely. That, in turn, lets us determine the direction of jumps one square further diagonally, and so on, so now we need to check whether those "projections" from different 8-connected sets of obstacles contradict.

This was possible to implement in the remaining time, but it would be extremely error-prone, so I've started the implementation with a random testcase generator and a maximum matching based slow solution to compare with. I've continued to implement the actual algorithm, and with about 10 minutes to go I had it passing the testcases from the problem statement, and most of 1000 randomly generated cases - but not all of them.

I've debugged a failing case on paper, and realized that my logic that checks for contradictions between projections is not strict enough. It was not clear how to fix it properly, and there was about 5 minutes remaining in the round at this point, so I've decided that my solution is probably completely wrong and started to re-read my 250 solution to check for errors.

But then, with about 2 minutes to go, qwerty787788 has submitted his solution for the 600, jumping to the first place. That has switched me to a different mode of thinking: what's a possible fix for my solution for the 600 that I could implement in 2 minutes? I've decided to try making the contradiction checking logic more strict by simply commenting out the specific part of code that caused no contradiction to be reported in the failing case - and was extremely surprised to see the new solution pass all 1000 randomly generated cases! It was extremely important to have the testcases and the testing framework ready by then, as everything happened in a matter of seconds, and I submitted my solution with about 20 seconds to go in the coding phase.

(Photo on the right from the official website) After the coding phase ended, I've ran my solution on 9000 more random cases - and it failed one or two of them :( Because of this, I was quite certain that my 600 solution would fail the system test, and thus started preparing for the challenge phase under the assumption that I have only 225 points. Having debugged my solution a day later, I know that the only bug was in the first part - I was sometimes incorrectly declaring a 8-connected set of obstacle cells to have a bad form, and the bug could only be triggered when such a set wrapped around at least one full cycle in a spiral-like manner. As 8-connected sets of obstacles play no part to the reference solution, it was very hard for the problemsetters to include such testcases into the system test, and thus the solution has actually survived them - but I didn't expect that after seeing it fail the stress testing.

As the challenge phase started, I've learned that all submitted solutions were quite long and hard to check, so challenging seemed hopeless, right until Kankuro challenged qwerty787788's 250-pointer. Now both Kankuro with 265 points and qwerty787788 with 233 points were slightly above my projected result of 225 points, so I've started desperately looking for a challenge. Unfortunately, I couldn't find any flaw in the remaining solutions. The tensions were eased a bit by Kankuro's own 250 failing a challenge from kuniavski, but qwerty787788 still stayed with 233 points until the end of the challenge phase.

After the end of the round, I learned from Egor that the 600 can be solved in a very simple way - I was missing the crucial observation that diagonals are completely independent and can be handled separately, so all the 8-connected-figure complexity was not necessary. I've also learned that qwert787788 had a correct solution, but he only checked it against the example cases and nothing else and thus it was likely to fail. The system test revealed that it did indeed fail, and that my solution unexpectedly passed - but the latter didn't really matter then.

Now I'm deeply regretting the fact that I forgot to turn on the screencast recording before the round started, as it would definitely be valuable to have this experience recorded, so I'm using this blog entry as such recording :)

Thanks a lot to TopCoder, to admins, problemsetters, event planners and organizers, to Jessie, Tim, Makoto and Gaoyuan personally, to the other Algorithm competitors, and to everybody who was watching! See you all at TopCoder Open 2016!

Tweet