PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, construct an N\times N grid such that for each pair (i, j), we have A_{i, j} equal to the MEX of the elements in the i-th row and j-th column other than A_{i, j} itself.
EXPLANATION:
When working on constructive problems, rather than trying random things and hoping they work, it’s useful to make some observations about the structure of the solution to restrict what we need to look at.
So, suppose we have a grid A that satisfies the MEX property.
One observation that can be made is that no row (or column) can ever have duplicated elements.
This is because, if A_{i, j} = A_{i, k} = x, then when considering (i, j) the set of elements will include x from A_{i, k}, and the MEX of a set of elements including x cannot be x.
This tells us that each row and each column must have distinct elements.
A natural idea now is to try and give the values \{0, 1, 2, \ldots, N-1\} to every row and every column.
It’s not hard to see that if we’re able to do this, it’s a valid solution - if we have A_{i, j} = x, then we know that the i-th row and j-th column don’t contain x at any position other than (i, j), but will also definitely contain all the integers 0, 1, 2, \ldots, x-1, so the MEX will indeed equal x.
So, how do we construct such a grid?
One simple solution is as follows:
- Start with the first row equal to [0, 1, 2, \ldots, N-1].
- Then, make all the other rows cyclic shifts of this row, i.e. the i-th row will equal
[i-1, i, i+1, i+2, \ldots, N-2, N-1, 0, 1, 2, \ldots, i-2]
For example, if N = 6 the resulting grid is
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(range(n)) + list(range(n))
for i in range(n):
print(*a[i:i+n])