Winter School on Programming, Day 2

I'm starting to type this entry in the lecture hall before the summing-up of the first day of the competition. The day began in the morning with the end of a dream about a TV series whose third episode of the fourth season was being broadcast in America at that time — the subconscious really is a curious thing. It was rather cold for sleeping, so we'll just wait and see when the hard frosts set in...

The School itself began with a lecture by the day's problem-setter, Vitaliy Nespirny from Donetsk National University.

The competition itself began with solving practice tasks, during which it turned out that the rest of the team members couldn't read a sequence of numbers from standard input. I, at least, have an excuse in that I don't know C++, but still... Yet another confirmation of my opinion that everyone on a team should "speak" the same language. In the end we somehow sorted out reading and output.

Then the tasks of the main round were handed out, which consisted of 11 problems of a rather high level; obviously, solving them in 3.5 hours was not realistic.

Most of the time went into the first problem, where you had to find the ratio of numbers in a sequence that are divisible and not divisible by a given number. The main difficulty was working with large numbers, but in the end it turned out we had run into some nicely hidden pitfalls.

There's no point in listing all the problems, so I'll dwell on the important and interesting points.

For the future, I should get a good grasp of the Towers of Hanoi, since there were two problems on them. The problem about the astronaut was also interesting; it turned out you could solve it with Dijkstra's algorithm. The problem about billiards was interesting, where instead of tracing a straight trajectory you had to reflect and redraw the table; it was solved using a divisor and solving a system of integers. This same problem won the KhPI team a gold ingot weighing one gram for the best solution. It's also interesting that there was a similar problem in the introductory lecture, only about the intersection of triangles. Plus there was the classic problem about finding the distance between two lines in three-dimensional space. For the future, I should recall the geometric formulas in such a space.

The summing-up is wrapping up now. At the moment we're tied for around 27th place along with the others, and the team's result is the same as the coach's. The winner of the day, with 7 problems solved, was the team from Taras Shevchenko Kyiv National University. Places 2–4, with 6 problems solved, were taken by the teams of KhPI, Kyiv National University, and Lviv National University. All these teams hold leading positions in the country, so there's no point in elaborating. As for records, the fastest solution to the first problem came in 7 minutes.

The whole summing-up has finished, we're leaving. The problems can be solved on all the remaining days and the solutions sent in as after-contest submissions. We'll try to take this up at the hotel.

Edited 22.02.2008