Home arrow C++ arrow Page 3 - Easy and Efficient Programming for Contests
C++

Easy and Efficient Programming for Contests


Efficient coding ensures that you complete a task in the smallest time interval possible without complicating your life too much. Now, you do not need to work like this for every little bit of code you type. This approach will be priceless, however, whenever time is of the essence, as it is for a programming contest.

Author Info:
By: Gabor Bernat
Rating: 3 stars3 stars3 stars3 stars3 stars / 9
July 07, 2009
TABLE OF CONTENTS:
  1. · Easy and Efficient Programming for Contests
  2. · How to write code
  3. · Macros, arrays and memory
  4. · Exploiting the language's strengths

print this article
SEARCH DEVARTICLES

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.


blog comments powered by Disqus
C++ ARTICLES

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials