Winter School of Programming, Day 3

The day began like most of the previous ones: with the Circle of Life song from the Broadway musical, which I quickly cut short by killing the alarm on my phone:-) And this night was warmer, because the heating had finally come on once the cold snap set in.

The lecture began with a "roast" by the Lviv team, whose captain had set that day's problems.

It all started with the introduction of the "translator", who mostly moved the tasks from place to place, but at the lecture he translated the team captain from Ukrainian into English for the guests from Georgia and Russia. After a cheerful speech, accompanied by translation, it was announced that the problems would be very easy and there would be no lecture on algorithms. But they did share some genuinely useful information for many of the contest participants — they wrote on the board how to open files for reading and writing in C. Our team agreed that this lecture turned out to be more useful than the previous one. At the end, the Georgian team's coach spoke and presented all sorts of certificates to the same team from the city of the lion — they had taken first places at their own contests but hadn't managed to collect the documents confirming it.

At the contest itself, 7 problems of varying difficulty were given, and their statements were about kumy, salo, and horilka. Of course, all the statements were in the official language. This time the problem-solving went better, since at least some problems were partially solved — two of them failed on the 11th test, and one or a couple on the first or second. The result turned out the same in the end, though it's a pity they only give points for the program passing all the tests, and not for each individual test passed, as at the other contests.

I won't write about the problems, I'll only note the points that would be worth knowing. I spent the most time on the problem that had to be solved with the Hungarian algorithm, and now I really do need to figure it out. I was also short on combinatorics formulas and on how to simplify a formula made of factorials. One problem had to be solved by multiplying a matrix raised to a power by a vector, and of course there had to be a problem on graphs. One problem required knowing the properties of series and how to work in the ternary number system.

During the solution walkthrough, they explained the methods, but some solutions leaned on "well-known" algorithms and properties, and others were presented in the most roundabout ways. In general, after upsolving the result is the same, but it looks like this day's ranking is very similar to the previous day's — only the top 22 teams have any results, not counting the points for upsolving, since I didn't memorize those. But the wrap-up hasn't started yet, I'll type up the next paragraph while they announce it.

As for the awards, the team from Shevchenko University won. The best — and fastest — solution turned out to be for the fourth problem, the horilka one, and, oddly enough, it came from the team at I. Franko Lviv National University. The problem's author — who was also that team's coach and captain — said he was surprised where such an original, fast solution had come from.

So far it's clear which day is in the running for the title of the most fun.

Edited 22.02.2008