NGON (many polygons) on SPOJ

Question

I am trying to solve NGON problem. I am using bottom up dynamic programming here. Recurrence function is:

$$\begin{array}{rl} f(a,b) &= f(a-1,b) + f(a-1,b-1)\,a_i +\frac{f(a-1,b-2)\,a_i(a_i-1)}{2}, a>0,b>0 \\ f(a,0) &= 1, \\ f(0,b) &= 0, \\ \end{array}$$

\$a_i\$ being the points on \$a^{th}\$ side.

I have used a \$O(n^2)\$ algorithm. I can't think anything other algorithm asymptotically faster than this but this is still getting TLE on SPOJ may be due to heavy modulo and long long int calculations. Can you please help me optimize it or recommend a better algorithm (if any)?

#include<stdio.h>
#define MAX 1010
#define MODULO 1000000007

int main()
{
    int test_cases,i,a,b;
    int sides,points[MAX];
    unsigned long long int result[MAX][MAX],temp;
    for(scanf("%d",&test_cases);test_cases>0;test_cases--)
    {
        scanf("%d",&sides);
        for(i=0;i<sides;i++)
        {
            scanf("%d",&points[i]);
        }

        result[0][0]=1;
        for(a=1;a<=sides;a++)
        {
            result[a][0]=1;
        }
        for(b=1;b<=sides;b++)
        {
            result[0][b]=0;
        }

        for(a=1;a<=sides;a++)
        {
            for(b=1;b<=sides;b++)
            {
                result[a][b]=(result[a-1][b]+result[a-1][b-1]*points[a-1])%MODULO;
                if(b>1)
                {
                    temp=(result[a-1][b-2]*points[a-1]*(points[a-1]-1))%MODULO;
                    temp=temp/2;
                    result[a][b]=(result[a][b]+temp)%MODULO;
                }
            }
        }
        printf("%lld\n",result[sides][sides-1]);
    }
    return 0;
}

Answer 1

You code is very crushed together; you hardly have any spaces in a single line.

Your code would be a lot more legible if you added spaces.

For example, you could turn this line:

result[a][b]=(result[a-1][b]+result[a-1][b-1]*points[a-1])%MODULO;

Into:

result[a][b] = (result[a-1][b] + result[a-1][b-1] * points[a-1]) % MODULO;

---

This is highly debatable topic, but I have been taught by people that it is always better to use the pre-increment operator over the post-increment operator.

By that I mean this:

++i

Over this:

i++

---

This is a little nit-picky.

In the signature of main, since you aren't looking for any command like arguments, you should put void in the arguments space.