Winter programming school, day 4

The morning was no different from the others. The sky was clear, though, so I got some decent shots of the hotel partly hidden by trees and of the nearby arena.

I also photographed the courtyard and part of the university buildings; inside, the guard told me that you're only allowed to have a camera on indoors with special permission. I wonder whether things are just as strict at KhNTU.

Today's problems were set by an author from KPI, but since he couldn't make it himself, the lecture and the analysis were given by one of the members of the IASA team from the same university.

The lecture covered problems on inversions in permutations; the more difficult second topic wasn't touched on, since the lecturer wasn't sure he knew it well enough.

The main round featured 7 problems in English, so there were no quirks in the statements. Looking at them overall, the problems turned out easier than the previous days, but the solutions didn't go well, since they failed to pass the time limits. Knowing the solution to a problem didn't help, because the algorithms had to be optimized or solved by other means, using special formulas and properties. Notably, there was an error in one of the tests, which meant one problem was credited to the leaders after the analysis.

But we still figured out the solution to one problem, after talking with the coach, even before the analysis. As it turned out, the solution didn't match the author's, but it did match the one proposed by the lecturer, and since this problem had no killer tests, our solution passed successfully. During the upsolving, after a few attempts, the algorithm was implemented correctly and the problem was credited. In the end, the coach and our team ranked somewhere around 27th-28th place in the upsolving standings, respectively.

Now about what would have been worth knowing to solve today's problems. Besides the already mentioned algorithm optimization and inversions in permutations, one should have known about the permanent of a matrix and Ryser's formula. It wouldn't have hurt to be able to count the number of possible quadrilaterals from a given number of segments of different lengths, which was computed via polynomials, and other properties of brute-force searches, sortings, and so on. But the solutions were strong, since even the person presenting them from the author's team didn't understand all of them and offered his own solutions.

About the wrap-up. Just now they wrote the address www.olimp.sc170.kharkov.ua on the board - the School's information site with a forum. The winners of the day were again the Pointless team from Shevchenko KNU. All the problems were solved by 2 teams, and at least one problem during the main time was solved by 22 teams, which is almost 2 times as many as over the past 2 days. The RockWellTeam from LNU, who sent in the correct solution to one problem in the final minutes, were awarded a painting of the St. Nicholas Cathedral in Kharkiv for their will to win. Tomorrow's author has already set out and will definitely be there.

P.S. Congratulations to biathlon fans on our women winning silver in the relay:-)

Edited 22.02.2008