This is the second part of the four-part series article I began here on Dev Articles. The first one also appeared here and tried to elucidate the mystery of why we should bother even to participate in something like this. If you failed to catch it when it originally appeared, you are free to search for it in my profile or by its title: Programming Contests: Why Bother?
As I told you at the end of the previous article, today we are going to focus on how you should prepare and act when participating in a programming contest: before, during, and after it. For a start, let us speak about what to do before.
We can divide the “training camp” that you should go through before the contest in the following parts: theory, mentality, global, simulation, experience sharing, and at the place. These sections will make sure that you’ve put in 90 percent of the effort and investment that is required to be successful at this. The remaining 10 percent is composed of your intuitiveness and (why not recognize it?) pure luck.
Remember that as important as it is to prepare for a contest, it is just as important to not overload your brain. It is advisable to totally relax for about a week before a greater challenge; just enjoy life and recharge your batteries.
You’ll need to understand high-level theories for the contest; that’s the theory element I mentioned above. Most of the time, if you rely only on what your teachers teach you in high school or even at the college/university level, you will easily find yourself facing issues that you cannot solve. This will be mainly because you don’t know a special technique, which seemed extreme and useless within the material for an average student…and therefore, it was not included.
In order to be entirely ready for a contest, you need to read a couple of books that endeavor to cover the algorithms of a field in detail. These are written most of the time by ex-Olympians, people who themselves faced these issues and are explaining and elaborating their own experience.
There are dozens of these kinds of books; nevertheless, there are a couple of them that have earned the title of classics. One that has earned the title of “The Bible of Algorithms” for its value is the appropriately titled Introduction to Algorithms by the trio of Cormen, Leiserson, and Rivest.
The other is Donald E. Knuth’s The Art of Computer Programming; it is highly polished and quite heavy. Other interesting books include The Algorithm Design Manual by Steven Skiena, Programming Challenges: The Programming Contest Training Manual by Steven Skiena and Miguel Revilla, Algorithms by Robert Sedgewick and Computational Geometry: An Introduction by Michael Ian Shamos and Franco P. Preparata (from which you can read an excerpt here ).
Of course, there are more books, which may be worth your attention; however, these are the most popular of them. Then again, the Internet can serve as the most elaborate way to obtain information; sites like the USACO Training Gate and the ACM’s site also have a large database with problems and their solutions. Now let us move forward by focusing on the mentality required.
Before the programming contest
Prior to each contest, many people set up roadblocks for themselves with false ideas and mindsets. I would like to talk about them here so you can get them out of your head before you compete.
The one always invoked is “I am not prepared enough.” Well, the truth is that most of the time, this indeed has some basis. Yet you should not sit back and give up; on a harder contest; the problems may require something more than just pure knowledge, intuition and luck. Go at it with an optimistic and relaxed approach.
Still, do not exaggerate; experience will tell you how much preparation and studying you should do beforehand. Remember that even if all goes wrong, you will still obtain valuable experience for the future. With this, we come to the second false idea: that someone else who is participating is better than you, and that you, therefore, will have no chance.
Wrong. All of you will have the same environment during the contest. S/he may have a better chance, but nothing is done until it is done. Moreover, as I explained before, the experience is one of the main attributes/traits that helps when competing. You can only accumulate this if you go and compete, right?
Another false thought is that you should not start a problem just because it is too hard. You know it is easier to win in a contest where the problems are easy, as solving them requires less effort. The true challenge is to do the same on a contest where the problems are very hard.
Here you may not come up with a perfect solution, just an approach that can solve a part of the tests. This alone can be enough, though, to obtain the desired place. Still, you cannot be sure that you will be number one, as someone may just solve it. If no one makes the maximum score on a contest, it does not mean that none of the participants were prepared enough.
With this, we came to the final mental block. A few contests last for more than a day of competition. If for some reason, you make too few points on the first day, do not say that you have no chance in the future. A good second day can bring home for you the desired place. Remember that the set of problems in contests are hard most of the time, and the points obtained by contestants are rarely close to the maximum. Even winning half of the points can turn out to be sufficient.
Now we can continue to the global preparation session. This involves simply tracking your progress and making it systematic. It is advisable to maintain a list of what algorithms are coming up most of the time, how you implement them, and what problems they can solve.
Plan your approach toward every little detail of the contest. If you know what you want to do and how you imagine doing it, you have already a higher chance to actually do it when you need to. Here enters quite a lot like time managing and tracking your progress, so you know your weak points.
The next part is the simulation. If you want to react better at the contest, the best way to accommodate the situation is to simulate it. Find out the point system, and the structures of the contest in which you are going to participate, and test yourself; then, analyze your comportment.
One of the best ways to do this is to use the many Internet sites that offer a set of problems and accept and test your solution. Do this just as you would at the contest — no breaks or pauses for time, and so on. If you do not act in this way, you will only trick yourself. Ultimately, observe your mistakes and correct them. We all learn best from our own mistakes, so do not fear them.
Experience sharing is also crucial. As I said before, the best knowledge comes from experience. It is advisable to learn from others also, so if you can, take problems to your professors or people who have already participated in the contest. Sometimes there are organized collective sessions; make sure you go to these, as they increase the level of understanding of all contestants.
Finally, the night just before the contest, you should make sure to sleep enough and to be present at the contest in time, with all of the required accessories (like a pen, paper and so on). Moreover, you should also, of course, maintain a mindset that will let you treat the entire contest seamlessly, with little or no effort.
During the contest
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 re-read 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 the 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 fewer 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 about 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.
After the contest and closing thoughts
Sometimes you may finish before your time is up. This happens normally only on the easier contests; nevertheless, if this does occur, do not come out of it yet. Make sure that each one of your programs runs with no errors, and invent more test numbers.
Sometimes you may even write a test generator and a solution checker, as the same are tested later on by a commission. Before you finish, make sure you did everything to get the best result.
This is the time for you to evaluate yourself, so when the results are published, you can contest it if you feel that you earned more. At some competitions, the evaluations are made in front of the contestant. This is the perfect time for you to observe your mistakes, if you made any, and learn from them.
Now you earn experience. Talk with the other contestants. See how they approached problems that you could not resolve, or if they did it in a more elegant fashion than you did. Find out what mistakes they made, also, so you can learn from them.
Now we are done. We went through all of the stages of a contest. Make sure you join us next week when I will be presenting for you a couple of methods that let you write code in a short and optimized way. Thank you for your patience in reading this article.
