Pizza From SpongeBob

Simple description

You have an M×N grid. You have to find the number of different rectangles within this grid.

Solution

First, we break down all rectangles in two types:

1. orthogonal: rectangles whose arms are parallel to X-axis or Y-axis.
2. diagonal: rectangles whose arms are diagonal to X-axis and Y-axis.

Counting orthogonal rectangles:

Well, that’s easy. Let’s take this 7×6 grid for an example:

Every time we can cut a new sub-segment from either AB segment or AD segment, we can construct a new orthogonal rectangle within this grid.

Therefore,

number of orthogonal rectangles = number of different sub-segments that segment [0,M] has × number of different sub-segments that segment [0,N] has

Number of different sub-segments for segment [0,N] 
= in how many different ways we can choose two end points for the sub-segment
= ᴺ⁺¹C ₂
= ((N +1)×N)/2

∴ number of orthogonal rectangles in M×N grid = ᴹ⁺¹C₂ × ᴺ⁺¹C₂

Counting diagonal rectangles:

First, let’s think about those diagonal rectangles which couldn’t fit in grids smaller than M×N.

Let’s think about this diagonal rectangle in 9×6 grid:

Here, we can see that,

DI/AJ = DL/AI = 4

It may seem like a coincident but it’s not.

Let AJ = x and AI = y
∴ DI = N-y and DL = M-x 
∴ (N-y).y = (M-x).x 

It can be proven that this property must hold for all diagonal rectangles that take the full grid to fit. Then again, different rectangles will have at least one of x or y different.

∴ number of fit diagonal rectangles = number of (x,y) pairs that satisfies [ (N-y).y = (M-x).x ] this equation

Now, the tricky part; how to calculate this count efficiently?

Let, (N-y).y = (M-x).x = Q
∴ x and y both divides Q
∴ M = x + (Q/x)
∴ N = y + (Q/y)

So, let’s think it this way:

first, we pick a number Q. Then we calculate all possible pair of (M, N) for this Q we take all divisors of Q and take them as x to get M and take them as y to get N, and then we add 1 to those (M, N) grid’s diagonal rectangle count for this Q.

We do this for all possible values of Q.

int maxQ = maxM * maxN;

for(int i=1; i<= maxQ; i++) {
    for(int j=i, k=1; j<= maxQ; j+=i, k++) {

        if(i+k>maxN || i+k>maxM) {
            break;
        }
        M_N_list[j].push_back(i+k);
    }
}

for(int i=0; i<= maxQ; i++) {

    for(int j=0; j<M_N_list[i].size(); j++) {
        for(int k=0; k<M_N_list[i].size(); k++) {

            int M = M_N_list[i][j];
            int N = M_N_list[i][k];

            if(N != M) {
                diagonal_count[M][N]++;
            }
        }
    }
}

This is the c++ implementation of the given idea. You should notice that we avoided the N == M case during the calculation. That’s because we want to avoid over counting. We can calculate this case in a separate loop by an O(1) formula.

for(int i=2; i<= maxN && i<=maxM; i++) {
    diagonal_count[i][i] = ((i-1)<<1) - ((i%2)^1);
}

Where does this formula come from?

Now that we have the count for fit diagonal rectangles in our hand, we can calculate the count for all diagonal rectangles inside the [M×N] grid. This requires some recursion, a little bit of inclusion-exclusion and a whole lot of rectangle love like Sponge.

total_diagonal_rectangles[M][N] = 
      total_diagonal_rectangles[M-1][N] 
    + total_diagonal_rectangles[M-1][N] 
    - total_diagonal_rectangles[M-2][N];

for(int i=1; i<=N; i++) {
    total_diagonal_rectangles[M][N] += (N-i+1)*diagonal_count[M][i];
}

Complexity

Had the pre-calculation and the optimization been done in proper manner, the complexity would be:

O( maxQ *(number of divisor of maxQ which are < maxM/2 and maxN/2)² )