Programming Tips

The most important point to remember is that it takes a lot longer to debug a program than it does to write one. For this reason you should try to ensure that your program works first time (or nearly so). The main methods to try to ensure that your program has a good chance of working first time are

Think of an algorithm that will work.
Write the simplest program that will implement the algorithm.

The Algorithm

To find a good algorithm

Understand the problem .
Solve it manually first .
Play around with various methods and ideas and ...
... implement the algorithm.

Which programming language should you use?

It is useful to read the Recommended Books but most important is to know the Golden Rules of Programming.

Understand the Problem

To find an algorithm that will work, you must first understand the problem. Be sure that you read it properly. Look at any examples and understand how sample solutions were got. If necessary draw a diagram. When you understand the problem, read it again to get the details (any exceptions or special cases etc.)

Solve it manually

There is no point just typing at the computer. Spend at least five minutes and probably about fifteen minutes thinking about the problem. It can be difficult to do this because there is a good likelihood that all around you there are people typing furiously at the keyboard. ‘Oh No they’re nearly finished you think’. In fact, most of the time they’re hitting the backspace key. In the IOI all the best programmers spent a good while thinking about the problem. Work out how you would solve the problem if you had no computer.

Implement the Algorithm

When you have found an algorithm, try to convert it into pseudocode. Work out how you will store the data, (array, linked list etc.). You will then have a broad outline of the program and you can switch on the computer. Ensure that you have foreseen any tricky input, maximum and minimum values, any exceptional conditions etc. Read the problem again and see if there’s any possible traps. Ensure that your algorithm caters for these exceptions.

If there is any part of the algorithm that you are unsure about, ensure that you get it clear in your head before you go onto writing the program. Remember that debugging takes longer than writing code. Don’t use the computer to help you think. It won’t. It will help you waste time. So get the algorithm completely correct before you start writing code.

See if you can spot any short cuts (playing around with the problem might highlight these).

The Program

Once you have the algorithm and data structure in your mind the program will be a doddle. But there are still plenty of chances for errors. Write the simplest possible program. It always sounds great when you can boast that your program was so complex that it couldn’t be understood by anyone, but it takes much longer to debug a complex program. To write a simple program make it easy to understand. Never write code that you’re not sure will work. You can be sure that it won’t.

Use Structured Programming

Structured programming is where you start designing the program from the top down (i.e. you write the broad outlines first). For example you could start writing the main() routine and just call functions such as get_input(), which you haven’t written yet. This is a bit like writing pseudocode, in that you can forget most of the details (in fact the program should look like the pseudocode). When you have written the main() routine, you can start writing the get_input() routine. Use the same approach here. If there is a subtask, then write a function to handle it. Functions , functions every where should be your motto. (An excellent programmer once told me that he figured most errors came from copying code from one place to another. If you write a function, then you can just call it. There’s no need to copy code from somewhere else.)

Functions should be short. There’s no harm in having a one line function. And a function should never take more than a screen (20 lines).

Another point about structured programming is that you should be able to see the effect of every function call. For example

	x = sqrt(i);

should only change x. No other variable should be changed. In this way it is easy to read through a function and not have to worry about the details of the function that is called. This means no global variables. If you use global variables to pass information to functions, then the variable may change unexpectedly within the function. This is a big source of bugs, and can take a long time to debug. (I’ll outline some exceptions to the global variables rule later on.)

Use sensible variable names

If you use sensible variable names you are less likely to forget what you called a variable. This will save you mixing up variables and causing more obscure bugs. E.g. a typical bug is

	for(i = 0; i <  N; ii++)

The variable incremented in the for loop is incorrect and can be hard to spot (this one has plagued my programs). Use names that the problem suggests, N or whatever, for the size of the input. That is if the problem says that there are N input items, than you can use N as the variable for the number of input items.

Use of global variables

Some people say no global variables, and in most cases this is a sensible rule. For writing these short programs however, there use is justified in some cases (especially where they are not changed during the program).

For input values that don’t change during the program.
For initialised arrays.
In exhaustive search where a recursive program updates a global array.

Input values

Most input values don’t change during a program. For example N the size of the input, will be input once and won’t change for the rest of the program. If it is a global variable, then you won’t have to pass it to all the routines, and you won’t suffer because it isn’t going to change after it is input.

Initialised arrays

Same goes for initialised arrays. In the clock program from the sixth IOI, the moves are part of the problem, and aren’t going to change. It makes sense to store them as an initialised array.

// The possible moves

int moves[9][9] = { {1, 1, 0, 1, 1, 0, 0, 0, 0 },

                    {1, 1, 1, 0, 0, 0, 0, 0, 0 },

                    {0, 1, 1, 0, 1, 1, 0, 0, 0 },

                    {1, 0, 0, 1, 0, 0, 1, 0, 0 },

                    {0, 1, 0, 1, 1, 1, 0, 1, 0 },

                    {0, 0, 1, 0, 0, 1, 0, 0, 1 },

                    {0, 0, 0, 1, 1, 0, 1, 1, 0 },

                    {0, 0, 0, 0, 0, 0, 1, 1, 1 },

                    {0, 0, 0, 0, 1, 1, 0, 1, 1 },

};

Global variables in exhaustive search

There are a lot of examples of using global variables in backtracking exhaustive search. See for example the chess program from Argentina. This is justified because it is otherwise hard to organise the exhaustive search. It does mean that you need to be very careful, because it is very easy to make mistakes. You should practice a number of these backtracking problems until you get used to the technique.

Optimisation

Forget about optimisation. Just get the program working. When it is working and if you think it needs to run faster then you can think about optimisation. Be sure to save the working version. Be sure that it is finished, (completely finished - it should generate the correct output files for all known input), and it should have the correct name so that you can get all the marks for it. Then you can start looking at optimisation. Be sure that the optimisations don’t stop the program from working (very easy to do). Remember that the correct algorithm is worth far more than clever optimisation techniques.

Finished ?

When you are finished, be sure that you’ve followed all the instructions. The output should match the specifications exactly, the program should be in the correct directory and have the correct name. You allow a few minutes at the end to ensure that these specifications are met. Also be sure that you’ve considered all possible input.

Keep it simple

Remember that most problems can be solved using common sense and arrays. Only use other data structures if you are sure that they are the right ones to use and you understand them properly. The one non-intuitive method that you should understand is recursion.

Programming Language

The two most important aspects of a programming language for this type of competition are

Support for structured programming.
Help to ensure your program contains no bugs

C and Pascal are quite similar, but in Pascal it is less easy to make unintended errors, and therefore I would say that Pascal is a better language for these type of problems. (I still use C all the time though.)

For example, you might know that you can access a two dimensional array in C using a[3][3]. However if you accidently type a[3,3], then the C compiler will accept it (as a[3]), the program won’t work and the error is difficult to spot. The Pascal language is not as flexible, and it is not as easy to make such hard to find errors.

The Golden Rules

Don’t forget the two golden rules of programming

Think about the problem
Think about the problem again