About problem setting

I finally did it! In 2009-2010, I was helping the Codechef competitions to start.
I created more than 30 problems that were used across 12 different contests.
After, I got distracted (Master Thesis, PhD studies), and I stopped.
After those years, I finally took time to browse my local database of my problems and try and match them
with problems at Codechef. (I never uploaded them directly, it was always uploaded on spoj.pl, and then they were copied.) It was sometimes tricky, but I managed. I feel good about it, like when reconnecting after a long time with a friend. Here is the list of all of them.

What are my impressions about problem setting?
It is a perfect transition between participation in contests and work as a researcher. How so?

  • I always thought of problems at contests as a microresearch.
    You solve a problem, spending at it 5min, 1h, 5h, maybe in extreme cases 1 week.
    You solve a problem that was solved by someone else. Sometimes you can manage to get even better, smarter, cleaner or faster solution than expected one. But you are still inside the ‘safety’ bounds. There exists a guarantee that the solution exists. Even better, you have a magic button to verify your solution: ‘submit’.
    Sometimes you doesn’t even need, after all, the proof of correctness (proof by ACCEPTED, anyone? It happened to us more than I am willing to admit.)
    Scope of impact of successful attack is limited. OK, it is a great joy to solve a problem, but most of the time, it is a ‘fire and forget’. It matters that you solved it, not ‘how?’. Half of the contestants doesn’t care, they also solved it. And even if not, you were not first to solve it. Problem-setter was certainly before you (at least we hope so). At most it is your team that cares, in case of team programming contests. Sometimes you can brag a little after the contest :)
  • My view of problem setting is as a miniresearch.
    Whether you take a known problem and try to modify it, or just had this wonderful, new, crazy idea,
    most of the time it is something new and original. (At least I tried, tried for my ideas to be new.) You create a small, brilliant masterpiece. Level of impact is different. If you are lucky, hundreds will try and attack your problem. You will be asked for a solution, or you will need to present it in front of an audience. It really matters ‘how’. And you need to have a proof!
    It is hard to gain a confidence. Writing a solution is also a different story.
    It is a very educational experience. You need to be extremely cautious, and double, triple check your code. You have no easy way to verify it. It really gave me a lesson to be careful and cautious (and try to mentally prove correctness of your code when writing it) [*]. When under no time pressure like during competition, and having no ‘verify’ button, it usually took days, not hours, to write correct solution!
  • Work as a researcher? Just extrapolate a step further (and eliminate coding part).

If as a competitor, you feel that you burned out, or just like to try something new – try it. Try to create some problems. There are plenty of possibilities, TopCoder, Codechef, ICPC regional contests.
Eternal glory and money gratifications await! It is a great problem-solving training, and very educational experience. And if you enjoyed it, then maybe going step further, and attacking big,scary problems with no guarantee of having a solution, that take months or years to solve is a way for you!

[*](Looking at my performance, still I consider it a wasted lesson)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s