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 
