Official

A - Permutation Grid Editorial by evima


Consider the case \(n=5\) and the permutations \(R, C\) are both \(1,2,3,4,5\). Let ? denote the square whose color is not yet determined.

?????
?????
?????
?????
?????

Since the \(5\)-th row should have five black squares, it must be entirely black. The same goes for the \(5\)-th column.

????#
????#
????#
????#
#####

Since the \(1\)-st row should have one black square, all remaining squares must be white. The same goes for the \(1\)-st column.

....#
.???#
.???#
.???#
#####

Since the \(4\)-th row should have four black squares, all remaining squares must be black. The same goes for the \(4\)-th column.

....#
.??##
.??##
.####
#####

Since the \(2\)-nd row should have two black squares, all remaining squares must be white. The same goes for the \(2\)-nd column.

....#
...##
..?##
.####
#####

Since the \(3\)-rd row should have three black squares, all remaining squares must be black. The same goes for the \(3\)-rd column.

....#
...##
..###
.####
#####

Therefore, the square at the \(r\)-th row from the top and \(c\)-th column from the left will be black if \(r+c\ge 6\) and white otherwise.

We can also prove that for a general \(n\), when the permutations \(R, C\) are both \(1,2,\dots,n\), the square at the \(r\)-th row from the top and \(c\)-th column from the left will be black if \(r+c\ge n+1\) and white otherwise. (We can prove it, for example, by induction by determining the outermost squares as we did above and reducing the case to the \(n-2\) case.)

Additionally, when we have the solution \(M\) for some \(R_1,\dots,R_n, C_1,\dots,C_n\), the solution for that case after swapping the \(a\)-th and \(b\)-th terms of \(R_1,\dots,R_n\) will be \(M\) after swapping the \(a\)-th and \(b\)-th rows. The same goes for columns.

Therefore, the square at the \(r\)-th row from the top and \(j\)-th column from the left will be black if \(R_r+C_c\ge n+1\) and white otherwise.

posted:
last update: