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 http://acm.sgu.ru. I'll try to remember how I came up with those problems.

Read more

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 :)

Comments?

And while we're talking about problemsetting, please note the two upcoming contests:

• Petr Mitrichev Contest 3 (including problems by Michael Levin and Irina Shitova) will take place on March 1, 2009 11:00 (Moscow Time),
  
• Petr, Michael_Levin and VitalyGoldstein Contest (aka Petr Mitrichev Contest 4) will take place on March 15, 2009 11:00 (Moscow Time).

These contests will take place at http://acm.sgu.ru 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 http://acm.sgu.ru afterwards as virtual contests, so that you can solve them and have the scoreboard reflect your 'current' position.