Easy and Efficient Programming for Contests - Macros, arrays and memory
(Page 3 of 4 )
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.
Next: Exploiting the language's strengths >>
More C++ Articles
More By Gabor Bernat
