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;
}
Next: Breaking out with smart solutions >>
More C++ Articles
More By Gabor Bernat
/ 8 
