BGL1213 Editorial

PROBLEM LINK:

Practice

Contest

Author: Satyabrat Panda

Tester: Pritish Priyatosh Nayak

Editorialist: Satyabrat Panda

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a matrix, find out the maximum size square sub-matrix with same digit, i.e, sub-matrix filled with only 1s, 2s, 3s or 4s.

EXPLANATION:

The states of the dp are (r, c, val).
dp[r][c][val] represents the maximum size square sub-matrix filled with val and bottom-right vertex at grid (r, c).

Traversing the matrix in row-major order, at any cell (r, c) with value val, we’ve three options -

  1. Extend the square filled with val and bottom-right vertex at the cell just above the current cell, i.e (r - 1, c).
  2. Extend the square filled with val and bottom-right vertex at the cell just to the left the current cell, i.e (r , c - 1).
  3. Extend the square filled with val and bottom-right vertex at the cell just diagonally to the left of the current cell, i.e (r - 1, c - 1).

Take the minimum of the three values + 1.
The dp transistion looks like this :
dp[r][c][val] = 1 + min(dp[r - 1][c][va], dp[r][c - 1][val], dp[r - 1][c - 1][val])

where val = arr[r][c].

SOLUTIONS:

Setter’s Solution
Tester’s Solution