Monday, August 18, 2014

a bit of dp: UVa 10502 - Counting Rectangles

Problem Statement:
UVa 10502 - Counting Rectangles

Given a square array A (made up of 0s and 1s) of dimension less than or equal to 100 x 100, find the number of rectangles formed by the 1s in the square.

Simple brute force approach with time complexity \(O(N^6)\) will lead to TLE since in worst case there are \( {100 \choose 2}^2 \) possibilities to check for, with \(O(N^2)\) checking time each. Hence we need to resort to a more clever strategy, and one that rings a bell is that of 2D array sum DP approach.

Let array S[100][100] be the array in which S[i][j] = \(\sum_{m=1}^i\sum_{n=1}^j\text{A[m][n]}\) (Or simply put, S[i][j] stores the sum of all elements of A which is inside the rectangle bounded by (1,1) and (i,j)). Having this array, we can easily find the sum of all elements in any rectangle in A in O(1) time. With this information, we can efficiently determine whether a rectangle is formed by 1s (since the sum of all elements of A in the rectangle will be equal to the area of the rectangle if the rectangle is fully filled with 1s). Therefore, the running time is reduced to \(O(N^4)\) which is still not bad for the problem. I suspect there is a more efficient algorithm to tackle this problem.