A programming contest is a special kind of challenge -- one in which the most important fact is the knowledge with which you come to the contest and the intuition you will have during it. What really counts is not your level of physical fitness, but the state of your mind. To prepare for something like this requires a different approach. You will found out exactly what it takes if you read further.
Preparing For Programming Contests - During the contest (Page 3 of 4 )
Of course, being ready at the time you are at the contest is even more important than being prepared enough. When you get the problems, make sure you read them all and get a general idea of what you need to do. During the first few minutes, do not even touch the computer; just imagine how you would solve the issue and check it out on paper to see if it works.
In addition, this is the time to clarify any questions you may have related to the problems. Form the questions so the answer can be a clear yes or no; otherwise, you may get a "No Comment" answer. If this happens, it means you may need to reformulate the question or simply that what you asked is already included in the problem. So reread it.
Make sure you plan your algorithm according to the input limits. This can drastically change the difficulty of a problem. For instance, if N<200, an algorithm with a complexity of N^3 will run in a reasonable time, but the situation changes when this is around 2000. Take into account every little detail.
It is recommended that you start with the easiest problem, or, if you cannot choose one like this, start with one that seems most familiar or accessible for you. Make a game plan and stick to it. This means you'll need to allocate a specific time for each of the problems and try to complete them in that time. If you terminate one earlier you can modify your time for the others.
Start searching for possible solutions and find the best of them, but not necessarily from the point of view of efficiency. Rather, find one that has the best complexity/implementation time ratio. Remember that you are asked to solve the problem in a given time, not to find the best possible solution. As always, do not exaggerate and lose more time on searching for a better, easier-to-implement solution if this search takes more than the time to implement a complex algorithm.
Always implement the shortest solution between the ones that have the best complexity. Once you start implementing the algorithm, there are a couple of methods that will increase your writing speed and most important, shorten your debugging/testing time. Let us go over them.
It is an unwritten rule of contests, (unless it is explicitly specified in the problem) that the input data is always correct. Compilation settings do affect the execution time of the application. So do not be amazed if at the contest, your program runs more slowly than at home.
Choose to write code that is simple and structured. In competitions, many prefer to write more C stylish code as it is more secure and offers less places to go wrong. If you have an option, do not use pointers, because debugging them can turn out to be troublesome. This also goes for the use of templates. Operations with real numbers are less accurate than in the "real" world, and slower, so avoid them as well.
Learn to write your programs in a modular form . This will let you debug your programs more easily and make sure that you can follow what you are writing effortlessly. Do not overstate! Remember that calling a function takes extra time. It is best to minimize the number of calls.
Use variables that will tell their purpose within their name. Guess what? A variable can contain more than two characters. Nevertheless, do not waste too much time with this, stay under the 10 character barrier. If you write in a way that will make your code more readable, even after a year, you will make your own life easier. For this purpose, coding standards were invented. If you want to find out more about this, make sure you read my article here . You can skip the comment part at time-pressed contests.
Save and test your application often. You do not want to get in the situation of having a well-made program teamed up with a power surge, equaling an unsolved problem. Nobody will believe that you actually made the program and it was good. Also, testing often can save you precious time in the later debugging process. The catch is to test at every major step. For instance, if the input needs to be sorted, test it so you do not fail at this "milestone."
Sometimes, more of the input data stream is put inside a single file. If this is the case, take extra care, because if your program hangs up at one problem, you will lose the points for all of them. Also, make sure you flush the output stream after each one of the resolved sub-solutions, as you may get some points for the problems for which your program ran successfully.
Your code needs to be short and optimized. How to make this happen will be the subject of the next two parts of this article series. Now I will give you some advice for the debugging part.
Everyone would like to write perfect code on the first try; however, experience tells us that this happens too rarely, so eventually you will arrive at this task. Always make at least four tests to determine if your algorithm is a correct one (a more advisable number is 7-8, though).
The test given on the paper has little significance. This is given most of the time more to confuse the contestant than help him/her. In addition, these never contain those special cases for which you will lose points. So invent tests yourself and run them on this. If one fails, run your program gradually and see where something goes wrong.
If you find the mistake, you may reload the earlier executed test to make sure you have not modified it so that it will now fail. If the time allocated for the problem passes, bring up a version that works at least partially and continue on to the next problems. Do not waste too much time debugging a single program!
When you manage to finish, if you have additional time and the initial algorithm turns out to be too slow, you may try to search for a new one. In this case, keep a back-up file of the original, so if everything goes wrong, you can still present the original solution.