Match Strategy
"If you take it slow you'll move up."

Wednesday, August 7, 2002
By KaiEl,TopCoder Member

If you ask most coders about their strategy for TopCoder matches, they'll probably answer with something like "score a lot of points" or "code the problems correctly." This isn't chess after all; it's computer programming. No need for deep strategy here, just code quickly and accurately. As cintamani puts it "this is about trying not to make a mistake, that's all there is to it."

Dig a little deeper, though, and you'll find that little differences in style and approach can be all that separates a top-tier coder from a low-level gray-name. The decisions a coder makes about match preparation, coding, and challenging can affect the final outcome of a tight match. I did a post-match interview with the members of two different rooms - one in each division -- to get some idea of how these various strategies play out in the coding arena.

Pre-match strategies

Some of the most important strategy decisions in a TopCoder match come before the match even starts. It's important to arrange yourself and your environment (a.k.a. your computer desk) for optimal performance in the hours before a match starts. Setting everything up just right can help you get "into the zone" during a match, leading to faster submissions and higher scores.

Nearly all of the interviewed coders have music ready to play during a match. Some coders, like FlySkippy1, will listen to any type of music, "just so long as its not too quiet," while others prefer to listen to rap, trance, techno or classical music as they program. Leadhyena_inran listens to remixed videogame music while he codes because TopCoder "is the closest thing to a videogame for coding... and it needs an appropriate soundtrack."

Tastes were almost as divergent on the issue of eating and drinking before a match. Some coders, like sreesree, can't code when they're hungry while others, like Mr. Sketch, "always [code] on a full stomach." Most coders, like Liam "can't program without caffeine," while some, like Leadhyena_inran, "gave up caffeine for the SRMs." Jhedlund articulated the most popular position on pre-match food: "I'd rather code when my stomach is not bothering me... so not hungry, not too full" Mr. Sketch adds the following words of caution: "I'd hate to be halfway though coding and get hunger pains and have to go raid the fridge."

Most of the interviewed coders made sure to have a pen and paper nearby so they could jot down notes and work out solutions while coding. Some coders gather even more outside materials before a match: kv recommends keeping graph paper handy, "for the occasional geometry problem," while CodePony sometimes uses a calculator because it's "handy for checking bounds on brute force problems."

Many coders recommended having the Java API or C++ STL documentation nearby, either in a web browser or a textbook, to check syntax during a match. However, a few coders, like cintamani, feel that "looking things up costs too much time," and recommend coding "with what you don't need to look up."

Most coders also suggested using the bathroom before the match starts because, as stkaway puts it, you "don't want to get caught up in the middle of the match."

Leading off...

So now that you're all set with a full CD player, a full bottle of coke, and an empty bladder, it's time to start the all-important coding phase! The first question every coder has to answer during this phase is which problem to open first. Overwhelmingly, coders seem to prefer opening the easiest problem first, and working their way up from there. Batty explains the standard reasoning behind this strategy: "I only occasionally get the medium [problem], and never the hard, so any other strategy would be stupid on my part."

Despite the popularity of the ascending order strategy, many coders have deviated from it at least once, with varying results. For instance, negotiator has only won when he opened the second problem first, "for some random reason." cintamani, on the other hand, once tried opening the Division II 1000-point problem first and didn't find it helpful. "If you can't finish all three, you can't do it an any order," he explains.

kv, a highly ranked red-name coder, points out that the top-level coders often open the hardest problem first, "because if there isn't enough time to do them all, it's better to get 500+1K instead of 250+500." ValD questioned the soundness of this strategy for lower-level coders like himself, saying that it's "a greedy strategy that often doesn't pay off." Leadhyena_inran offered what is probably the soundest advice on this subject: "Do the highest one that you can comfortably code first."

Careful planning

Once you've opened your first problem, whichever one it might be, it's time to code. Or is it? Most coders recommend against diving into the coding immediately, and instead studying the problem statement carefully before starting. FlySkippy1 says that "about a minute," of consideration is usually enough, while ValD says that you should take "as long as you need to fully understand it... sometimes up to ten minutes."

At the very least, you should glance at all the examples before you code. As sreesree recounts, "sometimes I didn't realize what the problem is unless I stepped into the final example. That was a nightmare." Batty, a coder who admits to "diving into coding too early," thinks that he probably would have done better in a recent match if he had "read it clearly through with the examples and thought it out. As it stood I had a nearly working solution that I never quite debugged."

If you absolutely can't stand wasting all that time reading and re-reading, stkaway recommends jumping into the routine parts of a problem while thinking about the tougher parts. "Let's say the problem has some tokenizing stuff," he explains, "I will just go ahead and do the tokenizing part and think about the problem in the middle of tokenizing, since it's pretty straightforward coding there."

Test, 1-2-3

Once you've coded and compiled a problem, the delicate balancing act of self-testing begins. Too much testing can lower your score considerably, but too little can cause your problem to fail on a tricky system test or challenge. How do you know what to test for, and how much to test for it?

Most of the interviewed coders found that the examples provided in the problem statement were a more than sufficient test for their code. "The examples will more often push the specifications," according to Leadhyena_inran. For some coders, in fact, even typing in the provided examples takes too long. "If I want to get more points, usually I'll take the simplest one (1st example) and last example," explains stkaway. Skeeve admits to occasionally skipping testing altogether if he's "totally jammed on time, but thinks [the code] is good."

cintamani joins some other coders on the opposite end of the testing spectrum, stressing careful testing of everything and anything you can think of. You should test "the examples, plus the borderline inputs. Check the part that says 'Topcoder will ensure.' Watch for empty lists, unexpected legality of negative input, etc." kv's testing method mediates between the two extremes: "run all examples, submit, then look for boundary conditions (and resubmit if you find them)"

Challenging Challenge Phase

The coding phase is over. You've tested all your problems to the point of overconfidence. It's time to milk those last few points out of this match by totally screwing your roommates over. That's right; it's the challenge phase.

As in the coding phase, the question of what to look at first comes up again in the challenge phase. Coders seemed evenly split on this issue. Some coders go after the fast submissions that are likely to be sloppily coded and fail on a boundary case. Similarly, other coders go after the slow submissions that coders try to sneak in right before the buzzer, which "are usually rushed and don't even pass all the examples," according to ermular. A few coders will try to challenge problems that they had trouble with first, or problems that were conceptually tough, but most look for slow or fast submissions first.

Almost every coder interviewed recommended being conservative in your challenges. kv cites past experience for his lack of aggressiveness: "I got burnt in the beginning, so now I'm very conservative. I challenge only what I am sure will fail." Mr. Sketch agrees, saying he'd "have to be 10000% sure before challenging." Leadhyena_inran lead the minority position on aggressive challenging, saying that he'll sometimes "gamble if I'm in a gap for scoring, like 100 points either way." Jlyer concurs: "Sometimes... I'd challenge if I can see I have nothing to lose by challenging."

The interviewed coders also recommend against wasting time looking at solutions whose algorithm aren't immediately apparent. "If it's a mess, it's not worth the effort," explains Skeeve. ValD agrees, saying that hard-to-read code is often right, even if you can't tell why. CodePony's challenge strategy consists of scanning the source code quickly, then looking closer if there's any area of the code that makes him uncomfortable. "Sometimes I'll spend a couple minutes," CodePony said of his slightly more time-intensive strategy, "though I check to make sure it hasn't been challenged by someone else already."

Finding your own strategy

So where does all this leave you, the coder looking for that extra edge to push himself up in the rankings? With so many different strategy questions to answer, and so little consensus between coders as to what those answers should be, it can be a little baffling coming up with a strategy that works for you.

The best method for this seems to be simple experience. Participate in as many single round matches as you can, and stay after them to consider what worked and what didn't. Talk with other coders about their strategies in the lobby and analyze the code of people who got the high scores for the night. If one match a week isn't enough to build your experience, don't be afraid to use the Practice Room. Over 100 matches worth of great experience is there for the taking.

For a quick fix, though, the best overall strategy TopCoder success seems to be patience. Don't get so caught up in the excitement of the coding arena that you end up rushing and losing points. Leadhyena_inran recalls some words of wisdom that the highly ranked ZorbaTHut gave him on this issue: "If you take it slow you'll move up."

If that doesn't work, then you can always try taking negotiator's advice and "just pretend it's for money. That works wonders."

Special thanks to the coders in room 7 on SRM104 and Room 2 of SRM 105 for all their help with this story.

Would you like to write a feature?