BSSPC '21 S1 - Lakshy and Palindromic Rectangle

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

It is well known that while squares are bad, arithmetic is even worse for the mental health of highschool age children doing programming contests. For this reason, Lakshy's CCC (Competitive Computing Contest) mental health break entails the Palindromic Rectangle problem.

Given an N \times M matrix of cells which either already contain a lowercase letter or are empty, determine values for each empty cell such that every row and column forms a palindrome.

Recall that a palindrome is a sequence of characters that reads the same backwards as forwards.

While Lakshy could totally do the problem himself, he is too busy struggling to read his poorly written IB HL chemistry notes. He leaves the task to you. Please write a program to help him solve the problem!


1 \le N, M \le 2 \times 10^3

Subtask 1 [10%]

N = M = 3

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line will contain two integers N and M, the number of rows and columns of the grid, respectively.

The next N lines will each contain M characters, representing the rows of the grid. Each character will either be a lowercase letter, or the symbol ., which indicates that the value is unspecified.

Output Specification

If no solution exists, output -1.

Otherwise, output N lines consisting of M lowercase letters each, the correctly filled-in grid. Any valid solution will be accepted.

Sample Input 1

3 3

Sample Output 1


Explanation for Sample 1

All of the rows (iii, ooo, iii) and all of the columns (ioi, ioi, ioi) form palindromes, so the solution is correct.

Sample Input 2

1 33

Sample Output 2


Explanation for Sample 2

It can be shown that there is no way to fill the empty grid cells such that the first row of the grid forms a palindrome, therefore a solution is impossible.


  • 5
    dawangk  commented on Dec. 30, 2021, 5:49 p.m.


    • 0
      Spitfire720  commented on Dec. 31, 2021, 9:07 a.m.


    • 0
      Marshmellon  commented on Dec. 30, 2021, 7:07 p.m. edit 4