Method to solve a task

Arthur Charguéraud and Mathias Hiron for www.france-ioi.org

The goal of this document is to help you solve an algorithmics task efficiently. It describe a method in several steps going from the text of the task to a code implementing the correct solution. The advice you will find in this document are not specific to IOI, they can be applied as soon as you have to find and/or program algorithms.

Steps of the method

1. Read the task
2. Solve examples
3. Find an algorithm
4. Pseudo-code the algorithm
5. Check your solution
6. Code your solution
7. Test your solution
8. Debug your code

Annex: being organized

1) Read the task

The first thing to do is to read the task carefully, and fully! This might seem obvious but experience shows that some people impatient to solve the task miss some important details. To avoid that, you need to take some time reading the task, and do not hesitate to read it several times to understand everything and miss no details.

What is important:

• Do not misunderstand. If you understand something else than what is described, it's over. Do not start solving before being sure to understand well the task.
• At the end, you must have the task in your head. You do not want to have to read it back again every 30 seconds when searching for a solution.
• Rephrase the task as simply as possible, so as to triage key ideas and the decorating story.

Rephrasing a task is what you do naturally when you want to explain it to someone who has not read it. In general, some short sentences are enough when using precise algorithmics vocabulary, like "graph", "shortest path", "dag" (directed acyclic graph), "subset", etc. Here are some example of task rephrasing:

• We have N integers between -1000 and +1000, and we want to select some of them to reach a given sum.
• We have a tree with positive or negative weight on each node, and we want the subtree whose total weight is maximal.
• We have a graph, and we want a closed path passing exactly once on each vertex.
• We have a rectangular grid, each cell have an altitude, and the goal is to compute the largest rectangle such that the difference between the highest cell and the lowest cell is not more than 10.

It is absolutely crucial to check that the rephrased version is really equivalent to the task. No details should be forgotten, and check that the rephrased version is neither a generalization nor a simplification of the task.

It is very important to concentrate until the end on the total understanding with no misunderstandings. You should forbid yourself to try to guess the whole task when you have read only half of it, because it is the best way to misunderstand what is written in the second half. Once you have finished reading the description, read the constraints quickly, and check your understanding of the task on the given example studying it carefully, then come back to the constraints to learn them by heart. Try as most as possible not to let your mind drift away to solving whereas you are still not sure you are solving the right task!

2) Solve examples

You have read and understood the task, then you rephrased it as simply as possible, now you have to solve it. Searching randomly in your head until you reach the perfect solution is not the most efficient way to proceed on hard algorithmics tasks.

The first step in searching for an algorithm consists in asking how you would do yourself, to solve the task by hand, on paper. How can it help? The human brain is very smart (at least compared to a machine) so it has good chances to find a way to solve the task correctly, and then it is pretty lazy in general, so it will naturally find an efficient way to solve the task. A correct and efficient solution is exactly what we are looking for!

Solving examples on paper is a lot more helpful than just getting ideas. To solve examples, we first need to generate examples. During this step, we generally start by generating very small examples that we be the limit cases, and we also notice which will be the worst cases to solve. Then, having examples solved by hand will let us check that our algorithm is correct, and will be used later to check its implementation.

To sum up, solving example will be useful for:

• begin ideas;
• find the limit cases (trivial cases and pathological cases);
• prepare a test suite and debug efficiently.

What is hard is to generate interesting examples. Theses example must be:

• different, so as to make visible all possible cases;
• correct, otherwide it can make us loose much time;
• cleanly solved, to be able to use them during the test step;
• big enough to be interesting, but not too much not to loose time.

3) Find an algorithm

On hard tasks, you will probably not find the solution only solving a few examples. This does not mean you should skip the step of solving examples by hand. The goal is not to stay blocked thinking on the task. To come to a working solution, there is no secret, you have to follow a methodic way.

The method is detailed in the method to search for an algorithm, here is a summary:

1. Read the task carefully, and rephrase it.
2. List the dimensions.
3. Search a good graphical representation of the problem.
4. Generate examples, solve them entirely by hand.
5. Describe the naive solution, then try to improve it.
6. Simplify the problem, then generalize the solutions obtained.
7. Try a different point of view, try the classical algorithms.

Reminder: apply this method on all subproblems encountered.

4) Pseudo-code the algorithm

Once you have found an algorithm to program for a given task, do not jump on your keybord to code it right away. Between having an idea of the algorithm in your head and knowning what is the best way to program it, there is still some work. If you start coding right away, you will risk loosing yourself in details and get something too complicated, or miss some details. One algorithm may be implemented in many different ways, which can be more or less difficult to program, and more importantly more or less bug-prone.

To get your mind ready at the time of implementation and writing your program in a simple way, reducing the risk of bugs, it is important to spend some time thinking on paper on the way to organize your code. To do so, a very efficient mean is to start writing the pseudo-code of your algorithm. The pseudo-code of an algorithm is a lightweight version of its implementation. Keeping only the essential elements of the program and ignoring language-specific details and obvious parts, pseudo-code allows to work efficiently on the structure of the program and on the important points like limits or mathematical formulas.

Pseudo-code being much shorter than the whole program, we can write several versions of it, each simpler than the previous one, without losing much time. Once we have found the simplest way to organize our program, we can then start programming peacefully, focusing only on writing details. Discover the secrets of pseudo-code, what it looks like, what should be written and what should not.

5) Check your solution

Wait until you have an algorithm you are sure about, and you have tested by hand on some examples, and checked it is efficient enough, before thinking about programming it. Programming takes time, and noticing our algorithm is wrong once it is implemented is a huge loss of time. Do not start before being 100% sure. Thinking well before starting coding will avoid you to lose a lot of time for what you have left to do. Experience shows contestants take a lot more time fixing their errors, of any type, than solving the task itself and writing the main part of the program.

Do not start coding before having checked that your algorithm:

• solve the task (read it again!),
• is correct (in particular it must solve correctly the examples you generated at the beginning, including the limit cases),
• has the complexity you think it has (compute it carefully),
• has the simplest pseudo-code as possible.

Also make sure you will have enough time left to test and debug it after it will be coded. If there is not enough time left, rather choose a simpler version, should you get a partial score. It is better to have 9 chances over 10 to get 50%, than try to get 100% but having only 1 chance over 4 to get that score, leaving 3 chances over 4 to have a bug and finally only get 10%. No one can pretend coding without bugs. It should be taken into account and limit our ambition to get 100% in order to get better average scores and improve more.

6) Code your solution

When you write your code, your goal above all is to reduce the risks of bugs:

• Write code as simple as possible, not minimizing the number of characters in your source code, but minimizing the probability of appearance of a bug.
• Do not try to optimize the code, you may not get more than 10 or 15% more, and you seriously increase the risk of introducing a bug and get 0. If you have time left and that your algorithm does not have a sufficient complexity to get 100%, optimizing the main loop of the algorithm will be much more profitable than trying to optimize random parts of the code.
• Take your time. With a good pseudo-code, cide can be written very quickly. If you take your time, you may take 5 minutes more coding, but you will divide by two the number of bugs in the code, and that much time not lost debugging.

All these techniques aiming at simplifying the code as much as possible and reducing appareance of bugs are details, for those coding in C++, in the document coding properly in C/C++.

Once you have finished writing the last line of code, you still have not finished this coding step. Yes, when we say "coding", we mean "coding right". To code right, you need to be focused during the whole code writing phase, and then you have to fully focus to proofread the code. Proofread your code, several times and in different ways. There are techniques for that, aiming at checking you forgot nothing and every line is correct. For example, you can read the code line by line, but also variable by variable. It is also interesting to read the code in parallel with the pseudo-code.

These proofreading techniques will be detailed in another document.

7) Test your solution

There are two thinkgs to check. First, that your algorithm is correct. Then, if it is correct, that it has the expected speed and memory consumption. Obviously, in a perfect world, everything is fine. But in practice, it is pretty rare that algorithms are good on the first shot. Testing your solution does not take much time anyway when everything is correct.

To check your implementation, the method is to take an example, run the program on it, look at the output, and compare to the result obtained solving it by hand. A second method, much more powerful, consists in checking that the data structure used in the algorithm behaves correctly during the execution of the algorithm. Let us detail it distinguishing two possible cases:

• First case, if the data structures used in the algorithm are simple (arrays), we can print them entirely along the iterations of the algorithm. Doing so we can check at each step that the state of the algorithm is coherent.
• Second case, if the data structures are complex, then we will first test them separately before starting to test the whole algorithm. We will write more code doing some requests on these complex structures in order to check they behave in a coherent way.

In both cases, the overhead work is almost nothing: just a few lines of code. The gain of the method is that it really help detecting and fixing possible bugs.

Here is the recommanded order of examples to test:

1. the example of the task,
2. the examples solved entirely by hand,
3. other examples generated at that time,
4. worst case examples, as much as possible.

To generate a worst case test, it is often sufficient to generate an input file using a loop with a printf. But on some tasks, it might not be as easy as that, and we do not always have time to write a generator. In these cases, we have to read again the theoretical complexity of the algorithm, and trust theory.

There will be a document detailing how to write lines to test and debug.

Very important: keep all your test file. Do not take the bad habit to write a first test, modify it several times testing it every time, without keep the different versions. Kepp all your test files to be able to reevaluate them quickly whenever you change your code. Fixing a bug, we may add another one... Do not lose time writing test files you deleted.

8) Debug your code

When we find an example on which the algorithm is wrong, we first have to simplify the example. Take a minute to get the smallest possible example on which the program does not work correctly, this will make you win a lot of time. Indeed, the more simple the example is, the less things there are to display to follow the execution of the algorithm step by step on the example.

Once you have the minimal buggy test, use the printing functions of the data structures to find the bug. If it is not enough, add a few lines to show the choices made by the algorithm (for example the parameters of recursive calls), additionnaly to data inside the structure. Do not show only the parameters of the calls: you will see there is a problem at some point but you will not know why.

Remark: some people love to use their favourite debugger (for example gdb). These tools are very efficient to debug big projets, but they are pretty unfit when it comes to algorithmics. The only case a debugger can be useful, is to localize a segfault (invalid memory address).

Debugging takes a lot of time compared to the rest. We must imperatively be rigourous, methodic, and know when to stop after some point even if we have not found the problem. It is dangerous to spend more than 15 or 20 minutes debugging. In 95% of the cases if we cannot find all the bugs in 10 minutes, then our code is too complicated or, even worse, the algorithm is wrong. Conclusion: everything must be done not to have to debug, that is doing seriously all these steps:

• simplifying the algorithm,
• verifying the algorithm,
• simplifying the pseudo-code,
• verifying the pseudo-code,
• proofreading the code in different ways,
• test independently hard parts of the code.

Annex: being organized

To think well, you must have good conditions. In particular, you must avoid losing time searching on which page you wrote the first example, you should rather use an eraser than striking through the lines, and the margin can be useful to leave small notes on the different phases taken to find the solution. To have good conditions:

1. Take a pencil and an eraser. Erasing is very practical, it helps improving some parts of what we wrote without having to copy everything.
2. Take a big sheet of white paper. Find paper which stays flat after rubbing several times.
3. Write the name of the task and the page number on top of each paper used for the task, to be able to come back to it later.
4. Write the time of beginning and ending of each step of research in the margin, to manage your time properly.

Do not be too lazy, prepare good conditions, you will see it is very profitable. If you doubt about these advice, try at least once to follow them carefully during a full 5-hour contest, and you will understand.

Conclusion

If some of the steps are not clear to you and you do not see what we mean, send us an e-mail to entraineur[at]france-ioi.org to help use improve the phrasing of our ideas in this document.

If you think our advice are not optimal and your way is more efficient, take the time to apply our advice carefully on three algorithmics tasks right now. If you really tried them and still have not changed your mind, send us an e-mail to explain your point of view. Maybe you will help us improve the method!

Good luck, best wishes for our algorithmics training!