...A Problem is Born
Wednesday, September 11, 2002
By KaiEl,TopCoder Member

You probably haven't put much thought into the problem creation process before, have you? You probably just take it for granted that every week there will be new and well-written problems waiting for you in the TopCoder Arena, don't you? Well, someone has to write those problems before you can code them. Someone has to test the solutions to those problems before you can challenge them. These often-neglected members code feverishly just so that you can have the privilege of competing in TopCoder every week! I went into the administrator's lobby during one match to de-mystify the process of how a problem gets from the writer's imagination on to your screen.

Starting off the Process

The problem creation process starts every month when TopCoder's head problem writer, lars2520, sends out an e-mail to TopCoder's 100-plus registered member-writers. "There are a lot of people who have written at some point, but only about 10 or so respond in any given month," lars2520 says of the demand for the writing duties in each match, for which the writer gets paid $500. "Becoming [a writer] is just a matter of asking to be one, for the most part. We'll generally let people write if they've been around for a while."

Once selected, a writer doesn't submit a completed problem all at once. First, a rough draft is put into TopCoder's writing and testing system, the Member Problem Submission Quality Assurance System (MPSQAS). At this point, the writer has to give "just the basic idea," according to lars2520. "Enough that I know what's going on, and can see what the solution will be."

"You usually write up the problem sans details/test cases," adds brett1479, the problem writer for SRM109. Each idea is checked against the hundreds of problems in the TopCoder database by lars2520, to make sure no two problems are ever alike. "Writers try not to repeat problems already done, and then Lars hits us if we do," brett1479 jokes.

Some may think that writing the problem statement is secondary to coding an elegant solution, but for problem writers this is often not the case. "The statement is really the core," brett1479 says of the most important part of problem writing. "A good statement can take an impossible 'nobody gets it' problem, and make it doable. Coding is usually the easiest part."

Inspiration

So where do those myriad problem statements come from? It can vary from match to match. "Sometimes I try to give a problem that is a good learning experience," says brett1479. "Something that'll introduce the coders to a particular algorithm. Other times, I just get a problem that sounds so good, and try to see what the algorithm is."

lars2520 says he sometimes gets ideas from classes at school. "We would be doing something, and I would think, such and such, which was vaguely related, would make a good problem," he recalls.

Sometimes, however, the most inspired problem ideas are the hardest to actually use. "The only problem I have with the truly inspirational, 'aha that's a great problem,' problem is that I usually don't get anyone solving them," brett1479 says. "I have definitely come up with ones that I determined were algorithmically impossible given the constraints."

lars2520 agrees: "Often the most interesting things are too hard for a competition. It happens a lot actually. It's always sort of tricky to make the problems hard enough that they are interesting, but easy enough that people can get them in 75 minutes."

Coding, Testing, Coding Again, Testing Again...

Once the basic idea for a problem is approved, it's time to write up the first of many solutions that will make sure the problem is perfect before the match. An average solution can take anywhere from two to ten hours to write, depending on the problem and who's coding it. "The writer/tester solutions have to be written extremely cleanly, since all the code is combed through," says brett1479. "So there is a balance between 'Code it as fast as possible' and 'Make it so clean.'"

"Usually all the problems end up with at least 3 solutions," lars2520 says, only one of which is from the person who wrote the problem. The others come from a group of testers who are paid to look over the problems before they get to the Coding Arena. "There is an elaborate writing/testing harness in place," brett1479 said of the MPSQAS system. "The functionality is quite nice."

lars2520 describes the testing process: "All of the system test cases are run against all solutions. Differences mean someone's wrong, and they have to fix their solution." This process often uses randomly generated test cases, and is pretty good at finding all the errors in the solutions, according to lars2520.

But even one little error can cause problems, as brett1479 found out in SRM109. In that match, a "versioning error" forced TopCoder to re-run system tests and challenges for the Division I Hard problem, delaying results and causing headaches for many members. "It was the right solution on my machine, but the wrong version on MPSQAS," brett1479 says of the error. "If fate decided that I need to have a blemish, this is a good one to have." dok, a TopCoder administrator, said that a problem like this hasn't happened "in quite a while."

Being a Writer

As the above example shows, a writer's job does not end when the match starts. The writer for each challenge has to stay in the administrative lobby during his or her match to help address questions and concerns from other TopCoder members. These usually amount to outright requests for help on the tougher problems, which TopCoder writers and administrators can't give. In SRM109, brett1479 had to deny these requests of about half-a-dozen participants with responses such as, "We can't give out too much help," or "You have to reread the problem, I'm sorry."

Despite these annoyances, brett1479 says that writing for TopCoder is a "pretty nice job. You interact with smart, nice people, you learn a lot, and you get paid, all from home." The best part for brett1479, though, comes after the match is over, "and you realize that your problem set was just used by 300+ users, and they all put an hour and a half into it, and they got something out of it, and that is something nice."

Would you like to write a feature?