Problem Link:
Difficulty:
Simple
Pre-requisites:
DP
Problem:
Calculate the amount of square submatrices of a given matrix which have ones on and above their main diagonal.
Explanation:
Sub task 1:
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.
Sub tasks 2, 3:
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.
Sub tasks 2, 3, 4:
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.
All the sub tasks:
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