Challenge24 finals are finally over, and as usual, I hurry to share my impressions about them. The impressions are sponsored by team Progopedia (Andrii Maksay a.k.a. maksay, Sergii Dymchenko a.k.a. kit1980 and me). Such things are the best to write immediately after the contest, while the emotions still invade you. Of course, one can start writing them while still in the competition (and last year I did so — I was pretty useless at night anyways), but this year we felt alert and fought for the points till the last minutes of the contest, so the blog post was postponed.
The main part of Challenge 24 took a bit less than 48 hours: registration and optional sightseeing on Friday, the round itself from Saturday morning to Sunday morning, and winners announcement and closing ceremony (for the toughest contestants who don't really need all that sleep) on Sunday noon. We arrived on Friday mid-afternoon, and went to the university immediately. Fortunately, this time we had no adventures like canceled flights, like the year before, so we arrived on schedule. Not quite in time, though: when we signed all the papers (you know, that we will behave, won't object to the paparazzi and stuff like that), checked in the hardware (this time having just three laptops didn't surprise the organizers) and got to the room where we were to spend the best part of the following day and night, three out of four places in it were already taken, and we had a wide choice of the last one. It was a small one near the door, and we had to do a massive rearrangement to make it at least a bit private (you know, team problemsolving is a delicate trade and requires a fitting setup).
After this we set off to the sightseeing tour, provided by the contest organizers and culminating in a boat trip on the Danube — as far as I know, the first of the kind in all years of Challenge24. Unfortunately, the first pancake turned out to be a blob. The tour turned out to be an accelerated march from the university to the landing, with short "let's make a group photo here" stops without any comment on what interesting things we are passing. I don't mind accelerated marches, hey, I enjoy walking unfamiliar cities, but I prefer to do this with comments and without a laptop in my backpack :-) The boat trip turned out to be, well, a boat trip — music, food and contest-unrelated tourists, but no comments about the views we were passing by. The worst thing about it was that it ended at 10pm instead of the planned 9pm. Evidently, the intention was to stimulate communication between contestants from different teams (that's what I missed a lot last year), but doing this on the evening before the contest, given that a lot of competitors arrived earlier that day and wouldn't mind a couple of extra hours of sleep, seems a bit weird to me. The rational thing to do would be skip the tour, the boat trip, the breakfast and the opening ceremony and spend all this time sleeping and stocking up on strength for the next 24 hours, but alas, we realized this a bit too late — at some point of the opening ceremony itself :-)
The contest started on Saturday morning. The problems were numerous, various and mostly fun: here are the problems and the official editorials. The worst thing about the problemset was that it had nothing about my favorite topic — esoteric programming languages or anything like that. Alas, I had to solve whatever problems there were, with varying success.
A. Alarm system
A typical algo-problem, solved by Andrii and Sergiy for 4 cases out of 10.
B. The Great Mixup
A typical algo-problem with a long and intricate statement which could be simplified to calculation of a product of numbers module 10..07. The simplicity of the solution was tainted by an overlooked zero in the modulo, so we spent quite some time looking for the possible reasons of differences between our answer and the sample from the statement.
A Marathon-style problem which required to generate the smallest set of tests for the given circuit which would detect circuit malfunctions. It was notable for its particularly obscure statement — the only person to understand it from our team was Sergii, who calculated the first test case by hand and explained it to Andrii about half an hour before the contest end. In the following 30 minutes Andrii coded several versions of the solution and cracked the rest of the test cases; and I officially announce that this is the most impressive piece of competitive programming I've ever seen! Not least because this was happening during the 24th hour of the contest, when I was having trouble even with writing plain text.
A sound-processing problem. We could give a try to image processing, but sound is a historically weak spot of our team. Sergii tried to approach it at night, but without much result, except for some lovely purple sonograms :-)
A typical algo-problem. Andrii solved it before I started reading the statement, so I didn't even finish it.
An amazing set of three problems which provided input data as TV transmission. They had to be decoded and (depending on the problem) find a path in the maze (F), count smiling and sad faces in the images (G) or detect enemy planes flying by (H). The last problem had some secret subtasks in it ([user:Alex_KPR,2012-05-03] hints that they involved UFOs, Cthulhu and teletext). I spent a lot of time on this set, but evidently my decoding routine was faulty, so right halves of my images were too noisy to be any good: I couldn't really distinguish a smile from a scowl or a black maze cell from a white one.
IJ. Air hockey
An interactive problem which had bots of all teams play together in something like hockey. Not really our type of a problem, and there were plenty of others to work on, so we didn't pay much attention to it. Well, we had a bot, but it misbehaved, didn't pass even a single test in training mode, and we never sent it to the tournament.
A great interactive problem which had bots pair against each other to play a war game with several types of troops and towns to be captured. A lot of teams created their bots too late or never got to creating it, so playing against them was all lavender — it was enough to take a single town. Our bot could do this and much more interesting things (you bet — we spent most of our time on this problem), so it earned something like 10th place in the final tournament.
Here one had to guide an object consisting of a rectangle and a pair of segments to the given point of the maze in a shortest way; the object could either move directly or turn around the center of one of the segments. The rumor is that this could be coded using a graph of all possible object positions and transitions between them, but I could never code this in time. However, I managed to pass 4 tests by drawing images like this:
How? Mostly by hand. To be more specific, I wrote a small program which could draw the given maze and a trajectory of the object in it, and I picked out the best trajectory by guess-work. My solution held the lead for the first 22 hours of the contest, but alas, after that other teams caught up, and I had only 70/100 points for three of the cases I solved.
18 hours into the contest we got another problem — writing the given set of words into cells of the crossword with intersections so as to fill as few cells as possible. Andrii took this problem as well.
Overall the problemset was nicely balanced this year — everybody in the team had something to do at every point of the competition. I guess that's why we felt awake and alert — I tried to get a nap on a beanbag only once, and without much luck — I was awaken and sent to take care of our bot for problem K. Same goes for other teams — generally the sleeping bodies and somnambulistically wandering people were much fewer than the last year. I also think this year the teams were stronger than before (that's the importance of timely and properly placed advertising); if this trend keeps, the online round won't be easy anymore, and a team without three reds in it might as well save the effort of going to the finals.
The detailed results can be found here; a careful eye could find lots of interesting things in them. For example, the winning team Havka-papstvo (by the way, congratulations!) once again confirmed by belief that a true competitor can't be impeded by petty matters like unusual problems, weird format or unknown language :-) The team which took the last place solved test case I7 — one of those not done by the winners, and so on.
I'd love to hear stories and comments from other competitors — there were plenty of familiar faces at the finals (we even shared a trip from the airport with asaveljevs). Russian version of the post already has some, make sure to check them out!
P.S. Oh, and they've made this video about the contest.