More Tricks to Gain Speed in Programming Contests

Now we've already learned a few interesting methods, so to conclude this article (and this series) I will present a solution that uses the possibilities offered by the C+ world to throw calculating the factorial from the application to the compilation time. This is the original idea of Alexandru Mosoi. All we need is the constant for which to calculate the factorial. All of this will be done during compile time, and the compiler will insert that value for the version that will run on your system

#include <stdio.h>// for printing on the screen

template<int N> // we write a recursive template declaration

struct Factorial {

enum {

value = Factorial<N-1>::value * N

};

};

template<> // and write the specialization for the zero value

struct Factorial<0> {

enum { value = 1 };

};

int main(void)

{

int i = Factorial<4>::value;

char c[Factorial<5>::value];

printf("%d ",i);

printf("%d ",sizeof(c));

}

With the result of:

Remember that templates are a new addition to C++ with which you can create general classes and functions. They are generated only at compile time for the required value/type. Now that is what I call a smart solution. This will throw all the work to the compiler and maximize the readability of your code.

Continue your efforts to learn new smart solutions and you are on the right path to eventually succeed in programming competitions -- and moreover, be envied by the others. With this, I am closing this article series, therefore I would like to thank you for reading all of them and invite you to write down your judgment of them here on the blog, or join the friendly forums at DevHardware or DevArticles and leave me a note there. Live with Passion!