Winter School on Programming, Day 5

The author of the problems for the fourth competition day was Andrei Lopatin from Saint Petersburg State University. The lecture topic was string algorithms, specifically methods of substring searching in text. At the start, we were asked who knew what a suffix tree is — a few hands went up, but only a handful could say what a suffix automaton is.

At the beginning we were told about the Knuth–Morris–Pratt search algorithm, also known as the z-function, but even that was hard to grasp, since I hadn't come across it before, and the more difficult part of the lecture passed me by. That part already dealt with searching for many substrings, where the construction of suffix trees and the workings of the suffix automaton were covered, and the suffix array was mentioned. In short, the topic is very useful for any programmer, only it's practically impossible to learn it in a single lecture. That's why I think this kind of string searching ought to be covered in my university's algorithm theory course, and the study of probabilistic automata should be replaced with the study of the suffix one :-)

Toward the end, the lecturer gave the titles of useful books on the subject: D. Gusfield, "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology," and a book in English that does a good job covering suffix automata: "Applied Combinatories on Words," but with practically no proofs.

All in all, the lecture was at a high level, and it became quite clear why the Petersburg university had been the world champion.

At the competition itself, 11 problems were presented about tsars Petya and Vasya; the statements were well posed and the stories about the warring tsars barely distracted from understanding the problem.

I think the first thing worth noting is that at the 55th minute, on the first attempt, our team submitted a correct solution to one of the problems and earned the first point in the main part of the competition along with a balloon. The problem required finding the perimeter of the rectangle bounding a given set of points. Beyond that, we did not obtain fully correct solutions to the remaining problems in the main round, but we ended up ahead of the coach, who hadn't submitted a correct solution in the main round.

Now about what you needed to know to solve the rest of the problems. The first problem called for dynamic programming and geometric formulas for computing angles and segment lengths. For the rest, you generally needed: dynamic programming, Gray code, building trees, working with polar coordinates in three-dimensional space, finding the intersection of a segment and a circle, and, as always, working with graphs, which we didn't even take on.

One problem we also finished off afterwards, since it was solved by repeating iterations up to a certain precision and had a time limit of 2 seconds; in the main round I hadn't thought of such an easy solution, but after the explanations from the lecturer and the coach, I solved the problem. Another interesting point came up: the statement of one problem could be disregarded and you could write the algorithm for a different, easier problem, and both algorithms passed the author's tests equally well.

By the end of the day, according to the ranking, on that day we shared 28th place with one more problem; in the post-contest solving we were 24th, and in the overall standings we're in 31st place out of a possible 49.

At the start of the wrap-up it was announced that in problem K from the first day, test 34 was incorrect and the results would be reviewed. The prize for the best solution — shorter even than the author's solution, thanks to its use of procedures — went to DefaultDream from KNURE. And the best result of the day was put up by Scorpions from LNU. After the awards, the lecturer went on talking about the loss of precision in computations and then moved on to the state of competitive programming itself, the advances in programming over recent years. He told stories about incidents at past competitions. The connection between mathematics and programming was touched on as well.

The host proposed an interesting game for developing teamwork. In it you have to write a program, but the participants have to write the lines of code in turns and can't communicate.

The conversations about games led to the conclusion that positional analysis is very important and can replace brute-force searches and the like. Each game and situation has its own positional analysis. But there's a trick against positional analysis in tic-tac-toe: placing the noughts a knight's move apart.

All in all, this turned out to be the day with the longest, most interesting and most useful lectures, thanks to Andrei Lopatin. After his talk, prizes were handed out to the winners of the previous days, and the School was over for today.

Outside, the snow that had started toward evening was now clearly coming down.

Edited on 22.02.2008