Number of parallelograms on a NxM grid

Question

I have to solve a problem when Given a grid size N x M , I have to find the number of parallelograms that "can be put in it", in such way that they every coord is an integer.

Here is my code:

/*
      ~Keep It Simple!~
*/

#include<fstream>

#define MaxN 2005

int N,M;
long long Paras[MaxN][MaxN]; // Number of parallelograms of Height i and Width j
long long Rects; // Final Number of Parallelograms

int cmmdc(int a,int b)
{
while(b)
{
    int aux = b;
    b = a -(( a/b ) * b);
    a = aux;
}

return a;
}

int main()
{
freopen("paralelograme.in","r",stdin);
freopen("paralelograme.out","w",stdout);

scanf("%d%d",&N,&M);

for(int i=2; i<=N+1; i++)
    for(int j=2; j<=M+1; j++)
    {
        if(!Paras[i][j])
          Paras[i][j] = Paras[j][i] = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2; // number of parallelograms with all edges on the grid + number of parallelograms with only 2 edges on the grid.
        Rects += 1LL*(M-j+2)*(N-i+2) * Paras[j][i]; // each parallelogram can be moved in (M-j+2)(N-i+2) places.
    }

printf("%lld", Rects);
}

Example : For a 2x2 grid we have 22 possible parallelograms.

My Algorithm works and it is correct, but I need to make it a little bit faster. I wanna know how is it possible.

P.S. I've heard that I should pre-process the greatest common divisor and save it in an array which would reduce the run-time to O(n*m), but I'm not sure how to do that without using the cmmdc ( greatest common divisor ) function.

Answer 1

Make sure N is not smaller than M:

if( N < M ){ swap( N, M ); }

Leverage the symmetry in your loops, you only need to run j from 2 to i:

for(int j=2; j<=min( i, M+1); j++)

you don't need an extra array Paras, drop it. Instead use a temporary variable.

long long temparas = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2;
long long t1 = temparas * (M-j+2)*(N-i+2);
Rects += t1;
// check if the inverse case i <-> j must be considered
if( i != j && i <= M+1 ) // j <= N+1 is always true because of j <= i <= N+1
    Rects += t1;

Replace this line: b = a -(( a/b ) * b); using the remainder operator:

b = a % b;

Caching the cmmdc results would probably be possible, you can initialize the array using sort of sieve algorithm: Create an 2d array indexed by a and b, put "2" at each position where a and b are multiples of 2, then put a "3" at each position where a and b are multiples of 3, and so on, roughly like this:

int gcd_cache[N][N];

void init_cache(){
    for (int u = 1; u < N; ++u){
        for (int i = u; i < N; i+=u ) for (int k = u; k < N ; k+=u ){
            gcd_cache[i][k] = u;
        }
    }
}

Not sure if it helps a lot though.

Answer 2

The first comment in your code states "keep it simple", so, in the light of that, why not try solving the problem mathematically and printing the result.

If you select two lines of length N from your grid, you would find the number of parallelograms in the following way:

• Select two points next to each other in both lines: there is (N-1)^2 ways of doing this, since you can position the two points on N-1 positions on each of the lines.
• Select two points with one space between them in both lines: there is (N-2)^2 ways of doing this.
• Select two points with two, three and up to N-2 spaces between them.
• The resulting number of combinations would be (N-1)^2+(N-2)^2+(N-3)^2+...+1.
• By solving the sum, we get the formula: 1/6*N*(2*N^2-3*N+1). Check WolframAlpha to verify.

Now that you have a solution for two lines, you simply need to multiply it by the number of combinations of order 2 of M, which is M!/(2*(M-2)!).

Thus, the whole formula would be: 1/12*N*(2*N^2-3*N+1)*M!/(M-2)!, where the ! mark denotes factorial, and the ^ denotes a power operator (note that the same sign is not the power operator in C++, but the bitwise XOR operator).

This calculation requires less operations that iterating through the matrix.