Practice

Contest

Simple

DP

Problem:

Calculate the amount of square submatrices of a given matrix which have ones on and above their main diagonal.

Explanation:

Even regardless the fact that the constraints are large, all the numbers are equal to one. Therefore, we just have to calculate the amount of square submatrices of the given matrix. To do that, we can brute force the size of the submatrix - let’s call this number s and add the product (N-s+1) * (M-s+1) - naturally, it’s the amount of possible top left corners for the submatrix of the size s, to the answer.

Even O(N^5) solution will do here. We can do a brute force for a top left corner and the size of a submatrix. It is already O(N^3). Then, we just check the submatrix in O(N^2) time. Thus, we have obtained O(N^5) solution.

There is also an O(N^4) solution. Again, let’s do a brute force for a top left corner and the size of the submatrix. And now we have to check whether the submatrix is good in any way with the complexity O(N). Let’s notice that a good submatrix C[][] should contain ones in the i-th column at the positions [1; i] (we consider that the matrix is 1-indexed). As it is a consecutive range of cells, we can use the standard approach to calculate the amount of ones in the rectangle. Generally, there will be O(N) such rectangles to check, so we have obtained the O(N^4) solution.

The model solution has O(N^2) complexity.

Observation: if the triple (X, Y, s) where (X, Y) describes the top right cell and s describes the size of the submatrix denotes a good square, then the triple (X, Y, s-1) also denotes a good square. Of course, now we consider the case when s>1. So, for every cell (X, Y) let’s calculate F[X][Y] - the maximal possible s where (X, Y, s) still denotes a good square. The answer to the problem, therefore, is the sum of all possible F[X][Y].

How to calculate F[][] efficiently? Let’s denote the amount of the consecutive cells with ones right under the cell (X, Y) by G[X][Y]. Then, F[X][Y] equals to min(F[X][Y-1]+1, G[X][Y]). This can be explained. If we have a good matrix of the size N, it is impossible to obtain a good matrix of the size bigger than N+1 by adding only a single column to it. It becomes obvious if we look at the figure that is formed by the cells that are on or above the main diagonal of the matrix. So, upper limit for the F[X][Y] is F[X][Y-1]+1. But it is not always possible to increase the size of the new matrix, because the last column of any good square submatrix should consist only of ones. So, if we don’t have enough ones below (X, Y), we just say that F[X][Y] equals to G[X][Y] - just the maximal possible submatrix that could end here. It is OK to consider it G[X][Y], because in this case G[X][Y] <= F[X][Y] and as we mentioned earlier, if the triple (X, Y, s) where (X, Y) describes the top right cell and s describes the size of the submatrix denotes a good square, then the triple (X, Y, s-1) also denotes a good square.

Setter’s solution:

Solution to sub tasks 2 and 3 can be found here.

Solution to sub tasks 2, 3 and 4 can be found here.

Solution to all the subtasks can be found here.

Tester’s solution:

Can be found here

4 Likes

My solution was O(N^3), simply computing whether square matrix ending at (ri, ci) and size i is good. And the square matrix ending at (ri, ci) with size i is good, iff matrix ending at (ri-1, ci-1) is with size i good and there are i ones starting at (ri, ci) and up (last column in good matrix are ones).

I was so close, just change the flag 3D char (boolean) array mc and rc to 2D int array…

there is also O(N^2 log N) solution . Firstly choosing top left corner with O(N^2) then make binary search for maximum square . we can pre calcuate dp arrays for finding sum of triangle described in statement like calculating sum of any rectangle O(1) . here is implementation

1 Like

I couldn’t understand the solution completely,
For the example,
2 2
1 1
0 1

Output is 3, where I was expecting it to be 4. Am I missing something or wrong somewhere, Kindly help me out!

Setter’s solution returns 4.

Are you testing it properly? There are not spaces between 1 1 and 0 1…

I tried with the setters solution and it is returning 3 to me, even if we do it manually using the logic of setters solution, I am getting 3.
For the input I have provided, the line feed has been removed and hence it is appearing in that way. 2 2(next Line)1 1(next Line) 0 1.

There are 3 setter’s solutions. Which one did you try? Get the link to IdeOne if possible.

Are you sure you there are NO SPACES in your input? See the second test case in previous code, it returns 3, but only because input is in incorrect format…

I am using the 3rd one (http://www.codechef.com/download/Solutions/LTIME03/Setter/MATRIX2_FULL.cpp). I am giving input in correct format, providing it manually and the calculated output is 3. For this simple input, one can execute the code manually, that is also giving 3 as output.

oh Okay, Now I got it. I missed to check that characters are not separated by space. Apologies!

//