Wednesday, January 12, 2011

TopCoder - SRM 146 DIV 1 - RectangularGrid - countRectangles

problem statement

In this problem you have to count the number of none-square rectangles in a given rectangle.
What I do is this, that I try to count all of
1*2, 1*3 ... 1*w
2*3, 2*4.... 2*w
......................
rectangles.

and I do this once for my rectangle and another time with the new rectangle with width and height swapped.
this is my code:
    long long func(int w, int h)
    {
        long long res = 0;
        for(int i = 1; i <= h; i ++)
            for(int j = i+1; j <= w; j ++)
                res += (w-j+1) * (h-i+1);
        return res;
    }
    long long countRectangles(int w, int h)
    {
        return func( w, h ) + func( h, w );
    }

How did I find this solution? I just tried to check it out on a piece of paper and I saw that there is a template for placing the rectangles with different width and heights in a larger rectangle.
For example if you want to place a 1*2 rectangle in a large rectangle, first you have to count how many of them are placed in a single row, (width-2+1) and multiply this number in height that is the number of 1*2 rectangles that are placed horizontally in a rectangle.

There are another solutions that I'm thinking about them, using 4 and 3 loops that I think they are trivial, and using 1 loop or even no loop that I'm thinking to understand them completely, then I'm gonna add them here.

No comments:

Post a Comment