Home arrow C++ arrow Page 3 - More Tricks to Gain Speed in Programming Contests
C++

More Tricks to Gain Speed in Programming Contests


As much as we would like to encourage smart thinking in programming contests, in the end, what makes the difference most of the time is who knows more tips and tricks to gain the extra advantage required. Today I am going to present another collection of them, believing that maybe someday, one of these will help you win.

Author Info:
By: Gabor Bernat
Rating: 4 stars4 stars4 stars4 stars4 stars / 14
July 14, 2009
TABLE OF CONTENTS:
  1. · More Tricks to Gain Speed in Programming Contests
  2. · Maintain the cache intact
  3. · Using the for loop
  4. · Breaking out with smart solutions

print this article
SEARCH DEVARTICLES

More Tricks to Gain Speed in Programming Contests - Using the for loop
(Page 3 of 4 )

By now, you've probably heard all sorts of bad things about the loop encapsulated in C under the name of “for.” Most teachers recommend that you avoid using for loops too much, and write as few of them as you can.

Now I am here to encourage you to take full advantage of its syntax to produce code that is at the same time readable and efficient. For this, let us repeat the syntax of the “for” loop.

for( commands that will be executed before entering the loop;

the loop will run until this statement is false;

commands that will be executed at the end of each loop);

{

commands that will be executed at each loop;

}

Now then, let us see two stylish usages of this loop. The first one is implementing the merge sort (has an average and worst-case performance of O(n log n) ) based on the idea of Mircea Pasoi.

int N, A[N], B[N];

void merge_sort(int l, int r)

{

int m = (l + r) >> 1; // divide by 2 via bitwise operator

int i, j, k;

if (l == r) return; // a single item

merge_sort(l, m); // sort on the left branch

merge_sort(m + 1, r);// sort on the right branch

 

for (i=l, j=m+1, k=l; i<=m || j<=r; )

if (j > r || (i <= m && A[i] < A[j]))

B[k++] = A[i++];

else

B[k++] = A[j++];

 

for (k = l; k <= r; k++) A[k] = B[k];

}

These solutions will not necessarily speed up your code; however, they are easy to implement and easy to follow two attributes that are just as important as being efficient at a challenge. Of course, at a contest you can forget the comments. I wrote them down now just for didactic purpose.

Here the A is the array that you want to sort and for this, we will use the B array. In the end, both of them will contain the sorted list of numbers in ascending order. On the following, I will present how to work with huge numbers without complicating things too much.

These methods are originally from Radu Berinde. The adequate way of dealing with these operations is to store the numbers inside an array with a reverse order of the reading (from the file) and the 0-th value of the array will point out how many digits compose the number. The subsequent methods are easy to implement, easy to understand, and efficient. What more could you desire?

Adding up two large numbers:

void add(int A[], int B[])

{

int i, t = 0;

for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)

A[i] = (t += A[i] + B[i]) % 10;

A[0] = i - 1;

}

Multiplying one large number with a small one:

 

void mul(int A[], int B)

{

int i, t = 0;

for (i = 1; i <= A[0] || t; i++, t /= 10)

A[i] = (t += A[i] * B) % 10;

A[0] = i - 1;

}

Multiplying two large numbers:

 

void mul(int A[], int B[])

{

int i, j, t, C[NUMBER_OF_DIGITS];

memset(C, 0, sizeof(C));

for (i = 1; i <= A[0]; i++)

{

for (t=0, j=1; j <= B[0] || t; j++, t/=10)

C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;

if (i + j - 2 > C[0]) C[0] = i + j - 2;

}

memcpy(A, C, sizeof(C));

}

The minus operator between two large numbers:

void sub(int A[], int B[])

{

int i, t = 0;

for (i = 1; i <= A[0]; i++)

A[i] += (t = (A[i] -= B[i] + t) < 0) * 10;

for (; A[0] > 1 && !A[A[0]]; A[0]--);

}

Dividing a large number with a small one:

void div(int A[], int B)

{

int i, t = 0;

for (i = A[0]; i > 0; i--, t %= B)

A[i] = (t = t * 10 + A[i]) / B;

for (; A[0] > 1 && !A[A[0]]; A[0]--);

}

The rest of a large number divided with a small one:

int mod(int A[], int B)

{

int i, t = 0;

for (i = A[0]; i > 0; i--)

t = (t * 10 + A[i]) % B;

return t;

}


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