Sunday, February 19, 2012

What is it like to be a (topcoder) problem setter?

You know, there's a question I never get asked: [What is it like to be a problem setter?] but since this blog lacks content, here is the answer anyway. Let's first answer another question: Why be a problem setter?

Money is the root of all problems
If you asked me why do I write problems, I would say that the main reason was money. Yes, really. Money. Money is my main objective of problem setting in topcoder.

No, I don't mean that it is possible to make problem setting your main source of income. Don't ever think that. Problem setting money comes too infrequently for that to be possible. I know that.

It's not the money, it is making money out of algorithms
Well, if the problem setter money is not a big deal then how could I say that money is the main reason I do it? Well, in reality, although money is the main objective of problem setting, I do not mean that money is my final objective. My final objective is to keep playing this game of algorithm contests. It is fun.

Programming contests are a hobby. If there is any serious justification for this hobby it is normally a very long term objective, such as getting good rating to impress some of the few employers that would care about it or to reach a championship after improving yourself for years. Plenty of other times there is not even one of those objectives, and I got to accept that I am one of those guys. I like participating in contests, it is fun for me. Pure algorithmic problems are so... pure, and beautiful. I get to use math rather than design databases and I hate databases, I hate soulless programming, I really do.

... The problem though is that it is very hard to explain your wonderful hobby. And it is even harder when you have a contest scheduled for a day and it overlaps with something else. It is not easy to say "Sorry, I have a contest so I cannot go". At least it was not easy for me before I started problem setting.. Thanks to problem setting money, my beloved hobby is not only a hobby but also a means to make money and I could even call it a job. It makes it a lot more justifiable to spend time working on a contest, and solving a problem. It removes a lot of guilt and it makes it acceptable for you to miss something in order to participate in a contest.

Wait... Then why did you make so many problem sets for free?
In my case, if I ever donated problems for member SRMs, it was with money in mind. Doing stuff for free is a good way to show that you can do that stuff. So that later you will be able to... say, get your problem sets accepted for the Topcoder open, when you are in a bad year and you really need to renounce about getting a TCO t-shirt and it is more convenient to write problems. (Think about it, btw, last year I made more money in the TCO than most of the onsite finalists).

Let's forget about money, What are your other objectives?
Easy, as I mentioned, I really like algorithm contests. I really , really do. There are few things more beautiful than finding out that the problem involving diamonds in a board, is actually about Eulerian paths.

How are problems born?
Thinking of problems is a lot like solving problems. Except that sometimes, you have no idea if the problems have a solution at all and other times, you have no idea if the problem exists. It normally is a very painful process that requires you to keep a notepad and make it a habit to draw weird stuff and look like a lunatic whilst everyone else is doing chit chat.

Sometimes, you don't initially know if there is a solution. Let us say you are frustrated about professors always being late, and suddenly you ask yourself "I wonder if that could be a topcoder problem". Then try to solve it. 99% of the time, there is no solution, or the solution is too easy or too difficult. Or maybe you are not Petr and can't think of the solution.

Other times, you have the solution but there is no problem. Let us say that you have failed to invent a 1000-points problem. You start trying to wonder if you could think of a problem that somehow combined algorithms you think are suitable for that problem difficulty. I noticed that this approach of thinking of the solution first and then of the problem is very good for easy problem levels - It is great for problem levels bellow div1 medium.

A cheap alternative is to take a problem you already know and make it harder somehow. Maybe that problem that had a constraint of at most 50 is actually solvable with at most 1000. The main complication is that your problems have to be original and interesting. So I usually avoid to try this unless the problem is mine.

There are occasions in which you scare yourself. The creative process is like that. Maybe you are in the bus and suddenly think of a new logical conundrum that would be a great div1 easy and then you quickly think of the back story featuring a sphinx and chickens. There is that time in which I thought of a complicated problem involving stacks and a new language and it came out of nowhere.

Once you think of the problem, you still have to get it approved. I only have experience with TopCoder, and to be honest, this is the hardest part. When I first started, I had to convince Olexiy. It was easy because my first problem set was a TCHS (high school) problem set and apparently no one cares. The it became hard because Olexiy left and mystic_tc (Ivan Metelsky) was in charge. I also wanted to write a real SRM. Later rng_58 took charge. Please note that mystic and rng_58 are the first and second place of last year's google code jam. In other words, your problem has to impress some of the best coders in the world.

More often than not, my final problem sets are drastically different from the stuff I had before I ask the admins to approve them. They usually find very easy solutions to the problems I tried to shape for months. Other times they say "That problem is too banal for div1 medium". Other times, the problem difficulty levels get swapped - The problem I thought was a division 1 easy, turns out to be a division 1 medium or even hard". There are occasions though, in which they provide ideas to make the problems more interesting. In fact, if I was completely honest, I would admit that more than one of the div1 hard problems I wrote are at least 95% their idea. They just took the premise I initially had and generated an incredible problem by changing the constraints and finding a very hard solution for them.

The development part
Even after your problem is approved, you still have to develop it. It is likely that Ivan and rng_58 received only a draft of your problem. You now have to make a good looking final version of the problem statement and to create a solution and test cases and something called checkData.

TopCoder is very professional and thus offers a tester to correct the language of your problem statement. As you can guess from my editorials and this blog, my English is so bad that they usually have to correct everything in it. Test cases are more of a joint operation. I try to make random test case generators that cover a lot of different variations and patterns, but there is also the fact that you and at least two other testers wrote a solution for the problem. One of the first solutions is almost always wrong, so finding test cases involves trying to break them. The testers are usually good at finding test cases.

In TopCoder, contestants can create their own test cases. This requires a way to verify that the test case is valid. This is the checkData method. It is a source of pain and rating cancellations, because a mistake here can cause invalid challenges during a match's challenge phase.

Either way, you will probably be receiving notifications about things to change in your problems all the time. And you have to change the problems when you have time. You can also discuss against some suggestions, because sometimes the suggestions change the problem in a way you do not like. But you have to keep objective, and it is better to, more often than not, listen to the testers.

I remember my first SRM, SRM 438. If would do that SRM again, a lot of things would be very different. My greatest mistake was not agreeing to the tester in some important matters. The match was harder than it should have been. Much harder, in fact.

And then...
Your problem set is ready, and all you have to do is wait and see what happens. You have to log in as an admin and answer questions. Then the match ends and here's the bad part: Coders from all over the world have failed the match and their easiest target is the problem set. I know this, because I've been there both as a contestant and as a problem setter. Many times, the problem set I wrote really was wrong. Other times, not so much. But there will always be someone that does not like the problem set. You have to be ready to defend your decisions and also to look at them critically and admit your mistakes. The good news is that the community itself as a whole tends to remain objective.

The worst case scenario is to mess a problem up in a high profile match. That happened to me last year in the topcoder open with RadarSabotage. It was very bad because the problem itself is... beautiful (By now you will have to admit that I am the sort of people that finds true beauty in mathy stuff). You have to learn of mistakes. IE: The mistake in RadarSabatoge was to add things that were not needed. I will never do that again. When you add a test case or a step that isn't needed or does not make sense. There is always the risk that your idea about it not being needed is actually wrong.

There are also good things that happen to you. It is a great thing when someone tells you that they liked the problem set. It is also nice when red coders ask you how to solve the problem. Or when the admin admits he liked your problems.

It also improves your skills. In order to write a problem, you really need to know the problem better than to just solve it. It may also change your perspectives about team work and let you work with some of the best coders around, did I mention those two guys who were 1st and 2nd place in the code jam last year?

Updated: I made some language corrections. I also forgot to mention that this post was inspired by Nickolas' post in codeforces. Although that is probably obvious.


mildbeast said...

I always wonder how you create new problem sets, and this post gives me good answer. Thanks for sharing your knowledge.

Nomail said...

Nice post!

Leandro said...

Great post! You talked a lot about money, so ... how much do you get for one problem in TopCoder? =)

vexorian said...

div2 250: 50 USD
div2 500: 75 USD
div2 1000: 100 USD
div1 250: 100 USD
div1 500: 125 USD
div1 1000: 150 USD.

If a problem is shared between divisions, then the amount you get is the division 1 one.

For tournaments the prices vary.


thank you very very much :)