Challenging 101
Friday, October 24, 2003

By Modulator
TopCoder Member

Introduction
What do you do during the challenge phase? Do you sit idle, aimlessly opening and closing problems, willing on the system tests, and watching with envy as coders of the ilk of Yarin, radeye and bstanescu average almost 4 successful challenges in every 5 competitions?

Hopefully this article will rejuvenate your 15 minutes of depression. Challenge phase can be an exciting and, ah, challenging, part of the competition, and hopefully there are a few tips here for everybody to take home.

Understanding the problem
A primary requirement for both solving a problem and challenging other solutions is to understand it. I mean really understand it. Before coding you should analyse it for special cases and boundary conditions, and account for these in your own submission. With your rock-solid comprehension of the problem's darker corners you should now have an arsenal of cases to challenge other people with.

These can come under the category of:

• Unexpected inputs. Look for obscure cases, and perhaps nonsensical inputs, that are still legal.
• Extreme inputs. These can be in the form of:
• Large numbers, which may cause overflow or timeouts
• Small numbers, which may cause precision errors
• Zero is always a special case, as are empty strings and arrays

However, many of these special cases are thoughtfully covered in examples. The real bonus comes if you can spot a program requirement (edge case, or just an innocuous rule) that is not covered by the examples. Bonanza! These conditions give rise to the loathed and loved 'shotgun' challenge phases where problems line up against a firing squad and go down screaming. You should always be looking for this occurring anyway in order to protect your solution, but remember to consider them as potential challenges too.

Simple challenge points
So what if the problems appear so simple, or so well demonstrated in examples, that the challenge phase looks like a good time to catch up on some sleep? There is still hope, but now you will have to get your hands dirty and analyse code in detail. I realize how painful this may sound, particularly as some code is so disgusting it produces strong feelings of nausea in the more 'professional' TopCoders.

However, there are some key areas which require slightly less detailed understanding, and you may even be able to look for them without feeling the need to shower afterwards:

• Loop conditions. If a loop is implemented incorrectly it still may succeed most of the time, and so pass the examples
• Is the loop variable correctly initiated, and incremented?
• Is the terminating condition correct? Should that be a < or a <=?

for(char i = 'a'; i < 'z'; ++i) { ... }
should most likely be i <= 'z'


for(int j = 0; j < v.size(); ++j)
    for(int i = 0; i < v[0].size(); ++i) { ... }
should most likely be i < v[j].size();

• Copy and paste errors. This is an extremely popular method for introducing obscure bugs. I personally have found it very effective in this regard. The cloned code may have changed correctly in all necessary points but one, so look carefully.
• Integer division truncation is not always intentional
• Manually entered data is a classic area for discovering bugs. It is easy to make mistakes when typing in data, and these may only be picked up in rare test cases.
• Is one of the strings spelt incorrectly?
• Is the alphabet missing a letter?
• Check lookup tables.

const string MONTHS[] = { "January", "Febuary", "March", ... }

const int DX[] = { -1, 0, 1, 1, 1, 0, -1, 1 };
const int DY[] = { 1, 1, 1, 0, -1, -1, -1, 0 };

Yes, even if you are daunted at poking around in other people's code, with specific points to look for you can browse their solutions quickly and effectively.

Other common challenge points
Of course, many errors will not fall into these categories - they will just be logic errors that you can only catch by reading the solution line by line. At the deeper level there still are a few common underlying themes in challenges:

• Double imprecision. Always beware of people using doubles when not necessary. In particular look for any use of the equality of doubles (for instance 0.1 + 0.2 != 0.3). Also check that an appropriate epsilon value is used in the conversion of a double to an integer.
• Greedy solutions. Solutions that appear to avoid considering all possibilities by making some assumptions may not always work. Try and come up with an example where the assumption fails.
• Timeouts. Solutions that appear to use brute force analysis or very high recursion may take more than the maximum 8 seconds. Tests run in the arena indicate that 2²⁹ additions, or 2²⁸ multiplications (including loop overhead and variable fetching) will run in just under 8 seconds. These times are for C++, and other languages will be slower. So, if a solution ever looks like making more than, say, 2²⁷ repeated calls or iterations then it is likely to timeout. The limits may actually be a lot lower than this depending on inner loop efficiency.

Also realize that just because an example case may appear large, it may not necessarily be the worst case for inducing a timeout.

These three areas are all a lot more dangerous to challenge, and it will generally pay to first test your challenge case locally, perhaps on your solution or a modification of it. Since most of us don't have play time during the coding phase, the 5 minutes of intermission is an opportune time to do this testing in anticipation of the potential challenges.

The risks
So you think you've found a challenge. You can now sit smugly quiet until the phase finishes and then write something in the chat like:

"JowBlow: I think your 500 fails MWAHAHAHA"

Or, you can put your points where you mouth is and challenge it. A word of caution is appropriate though; eventually you will be unsuccessful in a challenge, and so you must decide whether you can afford to lose the points. In some situations you may have much to gain and little to lose, and in other cases a successful challenge won't really benefit you at all.

Crafting the challenge
You've discovered a flaw, or maybe a canyon, but how do you expose it? Try and pick a test case with the smallest, simplest inputs possible. Then, try and run through the operation of the victim's code in your head. Choose inputs that will get you to your flaw as soon as possible, and which run through as few program flow constructs as possible. Reduce the case to its base essentials. Congratulations! You've finally developed the courage to challenge, to lay it all on the line, and as you tremulously enter the challenge inputs in, the screen flickers, and you realize, yet again, that somebody has beaten you to the challenge. Don't let this scare you into thinking that you need to rush your challenges. It is better to take your time and be confident of your challenge, perhaps losing some opportunities, than to rush it (and get it wrong).

Practice
Finally, practice is very useful. Every time somebody in your room fails a system test, chastise yourself for not finding it in the challenge phase. Then, before looking at the system test case that broke the problem, see if you can determine by yourself what was wrong.

Practice this and you will improve at reading other people's coding styles. Patterns do start to emerge and you will be able to comprehend them quicker over time.

Can't wait to get challenging? Challenge phase isn't just that 15 minutes we have to wait before we can start talking about the problems, it's also 15 minutes of unrestrained vindictiveness - and you might even get some extra points from it.

Would you like to write a feature?