# PROBLEM LINK:

Author:

Tester: Felipe Mota

Editorialist: Rajarshi Basu

# DIFFICULTY:

Simple

# PREREQUISITES:

Implementation, logic

# PROBLEM:

Generate an N \times N matrix such that:

- Each cell contains a number from 1 \dots N^2.
- No two cells have the same value.
- For each square submatrix containing cells in rows r through r+a

and in columns c through c+a (inclusive) for some valid integers r, c and a≥0:- M_{r,c}+M_{r+a,c+a} is even
- M_{r,c+a}+M_{r+a,c} is even

# QUICK EXPLANATION:

## Do this Quickly

Alternatingly place odd and even numbers in a checkerboard pattern.

# EXPLANATION

## Some Advice

It’s always a good idea to draw pictures in constructive problems, even if a 3x3 matrix.

## Observation 1

The exact numbers don’t matter so much as their parity, ie, whether it’s odd or even.

## Observation 2

When we say the sum of two things is numbers is even, we mean that their parity is the same.

## Observation 3

For the following sequence of claims, just consider 2 \times 2 submatrices.

- Let us just fix M_{1,1} = 1 (because why not).
- This means that M_{2,2} is also odd.
- This means that M_{3,3} is also odd
- We can extend this train of thought and conclude M_{i,i} is also odd \forall i, 1\leq i \leq N.

## Observation 4

Let us say the parity of M_{i,j} is odd. Then the parity of M_{i+1,j+1} , M_{i+1,j-1},M_{i-1,j+1},M_{i-1,j-1}, also has to be odd.

## Observation 5

The above observations together imply a kind of checkerboard pattern, where all black cells of the checkerboard must be of the same parity, and all white cells also must be of the same parity.

## Full Solution

Fill the matrix M in a checkerboard pattern where all black cells have an odd integer and white cells have an even integer (or vice versa). See Setter’s code for implementation. Since we just iterate over all the integers and place them, complexity is simply O(N^2).

# SOLUTIONS:

## Setter's Code

```
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll a[1005][1005];
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll j = 1;
for(ll i=0;i<n;i++)
{
if (i%2==0)
for(ll k=0;k<n;k++)
a[i][k]=j++;
else
{
j+=n-1;
for(ll k=0;k<n;k++)
a[i][k]=j--;
j=a[i][0]+1;
}
}
for(ll i=0;i<n;i++)
{
for(ll j=0;j<n;j++)
cout<<a[i][j]<<" ";
cout<<"\n";
}
}
}
```

## Tester's Code

```
t = int(raw_input())
while t > 0:
n = int(raw_input())
res = [[0] * n for i in xrange(n)]
at = [[] for i in xrange(n + n)]
for i in xrange(n):
for j in xrange(n):
at[i + j].append((i, j))
ptr = 1
for i in xrange(n + n):
for pos in at[i]:
if (pos[0] + pos[1]) % 2 == 0:
res[pos[0]][pos[1]] = ptr
ptr += 2
ptr = 2
for i in xrange(n + n):
for pos in at[i]:
if (pos[0] + pos[1]) % 2 != 0:
res[pos[0]][pos[1]] = ptr
ptr += 2
for i in xrange(n):
print " ".join(map(str, res[i]))
t -= 1
```

Please give me suggestions if anything is unclear so that I can improve. Thanks