Saturday, February 21, 2009

Remembering Petr Mitrichev Contest 1

Naturally, after taking part in so many programming contests, one accumulates enough ideas to start being a problemsetter. My first ACM-style contest was Petr Mitrichev Contest 1, which I set in August 2006 at the Petrozavodsk training camp, and which was later replayed at I'll try to remember how I came up with those problems.

Problem A - Balance was created when went to a website with a lot of mathematical puzzles in search of inspiration; different "find fake coin" problems didn't seem very well suited to programming competitions, but requiring to output the script and placing rather low constraints turned it from a purely-mathematical problem to quite an interesting DP requiring some accuracy.

Problem B - Cipher was created (or found in some paper, I don't know exactly) by a friend of mine as a side effect of his research.

Problem C - Hyperboloid Distance was created in search of a geometrical problem requiring an algorithmic idea. The more I thought of whether it's possible to solve it exactly or at least reduce it to a computation of  some integral, the more I liked it (since mathematical solution, if at all possible, seemed way more difficult than the approximate algorithmic one); The precision of 0.1 was there to be absolutely certain that my solution was correct and to make the problem a little easier, although I believe my solution had output much more correct digits after the decimal point.

Problem D - Real Fun was a special case in a research article that I was reading; I was amazed at the beauty and simplicity of the solution, and I still believe this problem follows the spirit of ACM ICPC-styled contests the most (among the problems of this contest).

Problem E - Hippopotamus was created as the "first problem to solve" for this contest, by adapting the idea of a simpler problem requiring exactly k iron boards among each m. This problem is quite standard, and stands out a little in terms of difficulty, but without such problem the contest could've become even more boring :)

Problem F - Ice-cream Tycoon was created because I've wanted at least one problem requiring log(n)-style data structures. There's nothing particularly interesting about it, as almost every similar question can be solved in a similar way using almost the same data structures. This is the kind of problems that's very easy to come up with.

Problem G - 4-3 King was one of the problems that I've had in mind for a long time (maybe a couple of years), but it was difficult to choose the exact variation of this idea (separate the given not-necessarily-convex n-gon in the given way) that will be both solvable and interesting to solve. I like the final version of the problem, and I've thought it would be the second easiest problem in the contest, but somehow the contestants didn't prove that :)

Problem H - Circular Railway was again a special simple case in a research article that I was reading. Luckily, it allowed for several different solutions, and thus I think was quite appropriate for the format.

Problem I - Shortest Paths was directly based on an entire research paper by David Eppstein, and I didn't expect anyone to solve it during the contest - the sole purpose was to share the amazing fact that there's such an effective solution to it with the participants :)


And while we're talking about problemsetting, please note the two upcoming contests: These contests will take place at under the standard ACM ICPC rules. They were set earlier at the Petrozavodsk training camps. For those of you who find this timing inconvenient, they'll be available on afterwards as virtual contests, so that you can solve them and have the scoreboard reflect your 'current' position.


  1. Are the solutions for these problems discussed anywhere?