Editorial for BSSPC '21 S1 - Lakshy and Palindromic Rectangle - Olympiads Online Judge

Editorial for BSSPC '21 S1 - Lakshy and Palindromic Rectangle

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: azeng

Subtask 1

In order for every row and column to be a palindrome, the grid must be of the form:

$\displaystyle \begin{bmatrix}a & b & a \\ c & d & c \\ a & b & a\end{bmatrix}$ $[\begin{matrix} a & b & a \\ c & d & c \\ a & b & a \end{matrix}]$

Where $a, b, c, d$ $a, b, c, d$ are (not necessarily distinct) lowercase letters. We therefore check each group of cells that must contain the same letter if we can make this the case, filling in empty cells as needed.

Time Complexity: $\mathcal O(NM)$ $O (N M)$

Subtask 2

Generalizing the previous solution to an arbitrary $N$ $N$ by $M$ $M$ grid, we notice that every cell $(i, j)$ $(i, j)$ , denoting the $i^\text{th}$ $i^{th}$ row and $j^\text{th}$ $j^{th}$ column, is with a set of four not necessarily distinct cells that must contain the same letter: $\{(i, j), (N-i+1, j), (i, M-j+1), (N-i+1, M-j+1)\}$ ${(i, j), (N - i + 1, j), (i, M - j + 1), (N - i + 1, M - j + 1)}$ . Since these sets are disjoint, we can handle each one independently, like in the previous subtask.

Time Complexity: $\mathcal O(NM)$ $O (N M)$

Comments

There are no comments at the moment.