REC25C - Editorial


Author: rakesh272611
Tester: varan245
Editorialist: rakesh272611




Two Pointer, Binary Search


You are given a matrix of size NXM. You have to find the minimum value K such that, a special square submatrix of size K is possible.

A matrix is considered as special matrix, if the OR of all the elements of matrix is greater than r,

Print minimum value of K that satisfies this condition.

If there is no K that satisfies the condition then print -1.


We have to find a minimum K such that there is a square submatrix of size K that is special. For that we will apply binary search on K and for each K we will check whether there exists a special matrix of size K or not.

We can do this by a Two pointer approach. First we will fix the window of size K in rows and then iterate over the column and check for every K column by two pointer.

After that we will shift the window to the next row and check for every K columns by two pointers again.

By this we can check for all the submatrix whose bitwise or is greater than r.


Binary search on K and prefix bitwise sum to check if the submatrix is special or not.

First for every i,j in our matrix we compute pre[i][j][k] which denotes the count of k^{th} bit present in the submatrix starting from (0,0) to (i,j). To do that, we write

pre[i][j][k] = pre[i-1][j][k] + pre[i][j-1][k] - pre[i-1][j-1][k] (for fixed i,j 0<=k<=20)

Now as we iterate over the 2-D matrix, at some index (i,j) we can easily binary search on value of K (smallest special sub-matrix of size K ending at (i,j)) while checking if submatrix from (i-K,j-K) to (i,j) is special or not by using the prefix bitwise sum.

Kindly refer to the tester’s code to understand thoroughly.


The time complexity for the problem is: O(N * M*log(min(N,M))*20)


Setter's Solution


Tester's Solution


Any other solution or feedback can be posted in the comments. We are always open for them.