Easy and Efficient Programming for Contests

A few of the tricks I will present here are not always the best approach, so use them only when you really need to. For instance, if you are creating a complex application that is being co-developed by a large team, it is a good idea to make everything as clear as possible, rather than inserting complicated code that may drive the others crazy. Nevertheless, at a programming contest, it would come handy.

Most of the tips I will share are the result of years of experience at programming contests or bright thoughts from more inspired people. I invented none of these examples, but I tried them out in my own code snippets, and they work like a charm, creating code that is both simple and fast.

Therefore, I will point out the initial source of these ideas, so make sure to give him all the credit. In this article, most of the ideas came from Alexandru Mosoi. Additionally, note that this is an article series about programming contests. In these, I try to answer questions like what they are and why you should participate in them. Finally, I also present a collection of useful tricks that will help you finish out in front.

If you missed the first two parts, you could find them at my profile under the names of “Programming Contests: Why Bother?” and “Preparing for a Programming Contest.” Now, as I promised you in the previous articles, let us get on with this.

How to write code

The problem with most beginners is that they do not realize the importance of clean and visible code. Most people say that this only puts extra effort into the equation and complicates your life for no reason. They will only see how wrong they are when they start to lose competitions for this. The sooner you comprehend this, the better.

One of the crucial things to learn is how to use the language to create code that is both readable and “followable.” By this, I mean that you need to write your code so you can instantly tell at every single point what you are doing. Of course, many things can be done in a multitude of ways; however, you want something clean and simple, so in the event of a bug, you can detect it in a short period.

One of the ways to achieve this is to make use of functions. Use them to structure your code in sub-segments according to tasks. Each piece of a function should nevertheless fit inside a screen; therefore, they should be around 30-50 lines long and not longer. The golden rule is that the complexity of the function (to write/ understand) is in inverse proportion with its length.

Prefer, as long as it is an option, solutions that are simpler, and fewer bugs can occur inside them. Therefore, use C instead of C++ as long as you can. This way, you will create a more reliable program that also will turn out to be faster most of the time.

Sure, C++ offers a couple of ways to resolve elegantly some traditional problems; however, these will show their muscles inside larger and more complex programs. When we are talking about contest programming, C will do so many things faster.

I myself programmed a couple of algorithms in C++ just to observe that the college’s code in C runs significantly faster. For instance, sorting a vector of ints with std::sort is slower than using an array of ints and sorting it with the qsort.

Additionally, “cin” “cout” and “cerr” slow down the application significantly. The bottom line is, if you have an option, do not use STL and C++. When you break down your code into smaller functions, you may use the inline keyword so you will not lose speed due to the function call.

This will tell the compiler at compile time to take this and insert 1:1 to where the function is called (if the function is smaller, and this will not make a significant change to the size of the exe), or just place that in cache of the CPU at run time. However, the cache has a limit, so do not declare all of them in this way, because this will mean none of them is inline.

Make sure you use the const and static keywords also. If a parameter for a function is passed down that should not be modified, use the const keyword. This will save you a lot of time for eventual debugging, because something still changed it. It is a good idea to use the uppercase letters for more important variables, so they will draw your attention and make you concentrate on them more.

Macros, arrays and memory

Avoid using macros for functions. You can lose points for a simple construction as follows:

#define MAX (a, b) ((a) < (b)? (b) : (a))

 

int query(int a, int b)

{

int k, l, r;

int result = 0;

 

…

result = MAX(k, query(l, r));

….

return result;

}

Observe that sometimes, the MAX is called twice; it’s best to avoid this situation during a contest. Instead, use a function declared as inline:

inline int MAX(int a, int b)

{

if(a > b)

return a;

return b;

}

Most of the time at a contest, the input and output of the program is a file. From this, you can already conclude that you need to use a lot of fscanf and fprintf. However, there is a solution for this. You can bind both of the files to the standard input and output with the function freopen (for newer compilers this has been declared deprecated and there exists a secure version of it).

freopen(“in.txt”, “r”, stdin);

freopen(“out.txt”, “w”, stdout);

This is easy, and from now on, you can read and print all of your files using the scanf and prinft functions, making your life easier and your code a little simpler. Every now and then, you may want to use arrays with negative indexing.

Everyone who is familiar with the Pascal language knows that this was possible with it. Nevertheless, creating arrays in this way is not an option in C/C++, however we can trick the system using the following macro definition.

int A[201];

#define A (A + 100)

Now you have an array that you can “index” from -100 to 100. In addition, it is advisable to use the “++i” operator instead of “i++”; executing the first will be faster. As for the second, a local variable will be created to calculate the new value for “i.” Creating variables this small (int) is not a big task, but it is still an additional task. The situation changes when you use STL and use the operator for iterators. In that case, do not ever use the second construction, as that will lead to a slow execution of your program.

For infinite values, I recommend that you use either one of the following:

#define INFINITY 0X3F

or

#define INFINITY INT_MAX/2

This will be most of the time large enough for the input files and INFINITY plus INFINITY will remain positive and fit inside the int. For setting default values for an array use the memset function.

int array_1[100];

int* array_2;

int length_2;

 

// allocate place using malloc for array_2

 

memset( array_1, 0XFF, sizeof(array_1)); // -1 at every place

memset( array_1, 0X3F, sizeof(array_2)*length_2);// INFINITY

When you want to compare two strings where you know their length, it is faster to use memcmp than strcmp. Do the following:

memcmp(string_1, string_2, MIN(length_1, length_2)+1);

Reading the first character after the white space can be done with the following construction of the scanf:

scanf(“ %c”, &character);

As a final thought for this page, you should remember that the program that generates the input data and the one that solves the problems should be two separate items.

Exploiting the language’s strengths