CDVA1605 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Diwakar Bhardwaj

Tester: Suraj Prakash

Editorialist: Shubham Kabra

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a L*R matrix of character M and F, we have to find that whether K*K sub square matrix of M or F lies in the L*R matrix or not.

QUICK EXPLANATION:

Basically we have to find the maximum sub square matrix of M and F inside the given L*R matrix in order answer the further queries in linear time. Now, how can we find the maximum sub square matrix of M and F. Well, It is a standard problem of dynamic programming - Maximum sub square matrix in a given matrix.

EXPLANATION:

Let’s find the maximum sub square matrix all consist of ‘M’ in the given matrix then we can similarly find sub square matrix all consist of ‘F’.

Algorithm:

Let the given matrix of M and F is be S[][]. The idea of the algorithm is to construct an auxiliary size matrix A[][] in which each entry A[i][j] represents size of the square sub-matrix with all M's including S[i][j] where S[i][j] is the rightmost and bottommost entry in sub-matrix.

  1. Construct a sum matrix A[L][R] for the given S[L][R].

    a. Create first row and first column of A[][] as, if it is M in S[][], there will be 1 in A[][] otherwise 0.

    b. For other entries, use following expressions to construct A[][]

        If S[i][j] is 'M' then
           A[i][j] = min(A[i][j-1], A[i-1][j], A[i-1][j-1]) + 1
    Else /*If S[i][j] is 'F'*/
           A[i][j] = 0

  2. Find the maximum entry in A[L][R], that will be the maximum sub square matrix all consist of M.

  3. Store the maximum value in a integer variable max_m.

Now, using same algorithm we can find maximum sub square matrix all consist of F only by replacing M by F and vice-versa and store it in another integer variable max_f.

For, the queries that will be asked further, we can directly print “yes” and “no” by checking the character and if K is greater than max_m or max_f (according to asked query for M or F) print “no” otherwise “yes”.

OPTIMAL COMPLEXITY:

\mathcal{O}(L*R + Q) where K is the number of levels.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.