PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, construct any N\times N matrix A such that:
- 1 \leq A_{i, j} \leq N^2
- All the A_{i, j} values are distinct.
- Every square with its top-left corner at (1, 1) has odd border sum.
EXPLANATION:
If N = 2, no solution exists, as the sample shows.
Otherwise, there’s always a solution. N = 1 is trivial, so let’s deal with N\geq 3.
First, notice that since our only constraint is certain sums being odd, the only thing that really matters is whether each A_{i, j} is even or odd.
Once this is decided for each cell, the numbers from 1 to N^2 can be distributed to them in any way.
So, our task is essentially to construct a boolean matrix A, such that:
- Exactly \left\lceil \frac{N^2}{2} \right\rceil of the values in A are 1, and the rest are 0 (this fixes the positions of the odd numbers).
- The border sum of every square containing (1, 1) is odd — in other words, the border of every such square contains an odd number of ones.
Suppose we have an N\times N matrix that satisfies these conditions. Let’s try to extend it to an (N+1)\times (N+1) matrix by adding one row and one column.
We only need to ensure that with the newly added numbers, the border of the (N+1)\times (N+1) square created has an odd number of ones; the rest are already taken care of by the existing N\times N matrix.
Observe that we’re really just adding in all the numbers from N^2+1 to (N+1)^2.
It can be seen that there’s always an odd number of odd numbers among them; that is, the newly created row/column contribute an odd number of ones to the border.
Why?
(N+1)^2 - N^2 = 2N + 1.
So, either N+1 of the new values are even, of N+1 of them are odd; and this is determined entirely by the parity of N^2+1 (the first number in the range).
if N is even, N^2+1 is odd and so N+1 values are odd; note that N+1 is itself odd here.
If N is odd, N^2+1 is even and so N+1 values are even; making N values odd (note that N is odd here).
So, the new row/column we create always contributes an odd number of ones to the border.
To ensure that the border has an odd number of ones in total then, we just need to ensure we constructed the smaller matrix with an even number of ones in the rest of the border.
Image for visualization
Visually, the red areas below are new (and have an odd number of ones), and we need to ensure that the blue area contains an even number of ones.
With this in mind, there’s a rather simple construction.
We start with N = 3, the “base case”.
The matrix
100
001
111
will be our starting point. Note that it satisfies all the conditions we need: it has the correct number of ones, all necessary borders have an odd number of ones, and the part
100
0
1
has an even number of ones, allowing us to extend it further.
Now, extend this matrix by one. As noted above, we’ll add an odd number of ones to it, so the new border will satisfy the condition; we only need to ensure that the top/left border continues to have an even number of ones.
But this is really easy to do! The top and left borders lengthen by one each, so simply place a 0 at each of them then distribute the ones however you like.
For example, moving from 3 to 4 to be done as:
100 -> 1000
001 0010
111 1111
0011
Simply keep repeating this process:
- Place a 0 at cells (1, N) and (N, 1).
- Then, distribute the necessary number of ones among the remaining part of the border.
Once you have your boolean matrix, it’s quite easy to convert it to a solution to the actual problem; just place odd and even numbers appropriately.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n == 1:
print(1)
continue
if n == 2:
print(-1)
continue
ans = [ [0 for _ in range(n)] for _ in range(n)]
ans[0][0] = ans[2][1] = ans[2][2] = ans[1][2] = ans[2][0] = 1
for i in range(3, n):
odds = 0
if i%2 == 1: odds = i
else: odds = i+1
for j in range(odds//2):
ans[i][j+1] = ans[j+1][i] = 1
ans[i][i] = 1
# for i in range(n): print(*ans[i])
nxte, nxto = 2, 1
for i in range(n):
for j in range(n):
if ans[i][j] == 0:
ans[i][j] = nxte
nxte += 2
else:
ans[i][j] = nxto
nxto += 2
for i in range(n): print(*ans[i])
