Common Mistakes by Contestants

In this page I have a list of common mistakes made by contestants (who are usually new to the contest). I also provide a few suggestions on how to avoid making these mistakes. Note that there is no one solution to any problem, so feel free to send me any suggestions.

Read the Problem!

There is nothing more obvious, but many contestants do not finish reading the entire problem statement before starting to write code. These contestants end up discovering (before or after submissions) that important details were not handled, and it may or may not be easy to fix it up.

Reading the problem doesn't mean glancing over it; it means carefully reading and identifying all the details. What are the inputs and outputs? How big can the problem get? Anything you can or cannot assume about the input? Is there only one answer, or are there multiple answers? All these should be answered before even attempting to do the question.

Is It Fast Enough?

Once you have a solution in your mind, your first job is not to code it. Assuming that it works, you must first do a quick complexity analysis (usually this is elementary). Check the bounds on all input, as well as any additional assumptions you can make on the input. If it is too slow, don't bother going further. You are just wasting your time.

Many contestants incorrectly treat hard problems as easy ones because they see an easy solution right away but don't realize that the easy solution is too slow. They get "time-limit exceeded" and spend the rest of the contest doing incremental optimization (which sometimes makes the program incorrect). When there is a difference between O(n^2) and O(n log n), incremental optimization generally does not help.

Is It Correct?

Can you convince yourself (or anyone else) that your solution is correct? If you can offer a mathematical proof then it is the best. But not all of us can do mathematical proofs. One way is to try and explain your solution to a teammate. The teammate must not be afraid to ask about anything that he/she does not understand. Even the stupidest question may reveal something that was missed. If you are not convinced, don't just let it go. Press for a good answer.

At the same time, the person explaining the solution must do a good job explaining it. Don't just say "I already thought of that". You should explain in detail what you actually thought of and why it works. Remember that the person asking you the questions is trying to help you. Do not get offended or defensive when answering the questions.

Of course, if you are really good you may find this to be a waste of time. But not everyone is really good.

Getting Trapped by Hard Problems

This is related to the previous point, because many people mistakenly classify hard problems as easy. Only work on a problem in the early stage if you are sure that your solution is correct and fast enough.

Not Using the Scoreboard

The scoreboard is not there just to make your coaches feel good (or bad). If you see a lot of teams are solving a particular problem and you haven't touched it, chances are you missed an easy problem. If you are working on something with very few submissions (or a lot of incorrect submissions), you better know what you are doing.

Unless you are very good, it is unlikely that you know something that all the other teams at the top of the scoreboard don't know.

Checking Against Sample Input/Output

One of the most inexcusable mistake is to submit programs that do not even work on the sample input/output. When you finally have your program, at the very least you should make sure that your program works on the sample input. By "checking", we do not mean typing the input by hand and looking at the output. Type (or copy-and-paste/download) the input and output into files, run it with redirection, and run "diff" on your output against the sample output.

If it doesn't work on the sample input, there is no point submitting. This is sometimes tricky on multi-site contests in which the program works in the contestants' environment but not in the judging environment (e.g. different machine architecture).

Another trick: if the sample input/output has multiple cases, try switching the orders and see if the answers are still correct. Sometimes this will catch problems with uninitialized variables.

Trusting the Sample Input/Output Too Much

Did you assume anything that was not explicitly stated? Just because the sample input gives you a connected graph does not mean that your program will only be tested on connected graphs. Unless it specifically states this in the problem statement, do not make any extra assumptions!

Time Management

Should each person work on different problems? Should two (or three) people work on one problem at a time? This all depends on the team. But if you are stuck on a particular problem for a long time, you should try another one. Sometimes taking a break and coming back to it later helps. It also helps to avoid being stuck at a hard problem.

Another problem is that sometimes you come up with an incorrect solution, type it in, and it does not work (maybe you find out before or after submission). Inexperienced teams often spend the rest of the contest trying to fix the solution. But if you started with a hard problem without knowing it, you will just end up wasting your time. If you are stuck, try another problem.

Debugging

Debugging on the computer is usually bad. It wastes computer time that could otherwise be used to solve more problems. Also, people (especially when under stress) tend to shut their brains off in front of a computer. If you print the code out and try to think it through, it is often more constructive and faster. My advice is that if you can't figure out what the bug is in 10 minutes, print it out and debug it on paper. Also, if you print your code immediately after every submission, you can debug it on paper immediately if your submission is rejected. No need to interrupt someone else working on another problem. Sometimes it helps to do a line-by-line walkthrough of the code with someone else.

If your submission is rejected, try to think of input that satisfies all the constraints given in the problem statement that breaks your program.

Communication

Remember that you are competing as a team. It is okay to critically examine your teammates work to make sure it is correct, but try not to be insulting or sarcastic. Do not argue about stupid things like coding style or variable names. If you believe that your teammates solution is correct and good enough (after thinking carefully), then use it even if you think you have a better solution. Never believe a thing your teammates say without a convincing argument.


Howard Cheng

Valid XHTML 1.0!