Another week with no problems

Gennady came back strong last week, winning two competitions. The first one was TopCoder SRM 673 (problems, results, top 5 on the left). Yet again he's solidified his coding phase lead with a successful challenge - great job!

Open Cup 2015-16 Grand Prix of Europe took place on Sunday, using problems of the ACM ICPC CERC regional (problems, results, top 5 on the left, CERC results, its top 5 below on the left). The top 5 online teams were above the top onsite team, although of course there's less pressure onsite when you're already leading by a problem or two :)

Congratulations to the University of Warsaw team on the very clear onsite victory! As usual with ICPC regionals, it's not clear how many teams will advance to the World Finals. Is this information already public?

And finally, another European regional SWERC 2015 showed some really close competition, with the top two teams separated by mere seconds (results, top 5 on the left). This time I'm pretty sure that at least two teams will be invited to the World Finals :)

Thanks for reading, and check back in several days for this week's summary, where I've finally solved some problems myself and can share them :)

An educational week

I've already shared my impressions about the TopCoder Open 2015 Semifinal and Final rounds; however, this week had another noteworthy event:

Educational Codeforces Round 1 has tried to realize the "only solutions that can truly handle all possible cases should score points" aspiration by allowing 24 hours of challenges, including the ability to stress-test, after the round has ended (problems, results, top 5 on the left, experiment description, experiment analysis). I haven't been participating myself, but from the surrounding blogs it looks like the experiment was quite successful, with many contestants contributing tricky testcases after the round has ended. What are your impressions from this format?

Thanks for reading, and check back next week!

A pre-week

After the TCO dust has settled, let's take a quick look at the pre-TCO week.

Open Cup 2015-16 Grand Prix of Siberia took place on Sunday (problems, results, top 5 on the left). In yet another reshuffle of top Russian teams, the SPbSU Base team got the top spot thanks to almost flawless correctness stats: only one incorrect submission per 11 problems! Such clean stats were once the trademark quality of another famous SPbSU team, the SPbSU 4 that won the world championship in 2014 (for example, here are the stats of the last Petrozavodsk training camp before the said world championship - the "Dirt" column is the fraction of incorrect attempts to correct attempts), so the SPbSU Base team has picked the right example to follow :)

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!

TopCoder Open 2015 Finals Finals

TopCoder Open 2015 Onsite Semifinal Round is over (problems, results, top 5 on the left, editorial, my screencast - might still be processing). The round turned out to have a beautiful but very hard 1000-pointer, so (in retrospect) the right strategy was to solve the first two problems, and then make sure the solutions are correct, most probably via stress-testing. However, many competitors including myself and tourist hoped to get the 1000, and thus failed to test the 250 and 500 properly. I was lucky that my solutions still passed (thanks to the wishes for luck in comments!), while tourist unfortunately had his 500 solution fail - very sorry for that, and better luck next year.

The five finalists will have the final battle very soon - the Final Round starts in about 45 minutes. The problem values are 250. 600 and 1000. Wish me some more luck :)

TopCoder Open 2015 Finals

The final round of the 2015 TopCoder Open, the oldest and one of the most prestigious international competitive programming tournaments for individuals, takes place today in Indianapolis (on the left: a small public library inside a city park). There will be two rounds: the Semifinal round, where 12 contestants participate and 5 advance to the finals, from 10:00 TopCoder time to 12:00 TopCoder time (other timezones), and the Final round for those 5, from 15:00 TopCoder time to 17:00 TopCoder time (other timezones).

TopCoder will be doing live coverage on Facebook, and on Twitch (this one is scheduled to start one hour after the beginning of each round, covering the end of coding phase and the challenges).

Wish me luck!

A week with stabilizers

Open Cup 2015-16 Grand Prix of Ekaterinburg took place last week (problems, results, top 5 on the left). Congratulations to the XZ team on their first win of the season! The results were decided by problem H, which asked to count how many different permutations can be generated by a given set of permutations of order at most 15, and thus boiled down to a beautiful but a bit obscure algorithm: the Schreier–Sims algorithm. In my view, the most important result of this round is an elementary description of the Schreier-Sims algorithm by Andrey Halyavin and Maxim Akhmedov (in Russian).

Problem A was the nicest in my opinion. You're given 10000 points on the plane such that no three points lie on the same line. You have to build a triangulation of this set of points, and then answer 100000 requests of the form: which triangle of triangulation covers the point with the given coordinates? You're free to pick any triangulation, so the goal is to pick such one that allows answering these requests quickly.

Thanks for reading, and check back soon for this week's summary!