PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: shubham_grg
Testers: iceknight1093, tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N \geq 4, find any N\times N matrix that consists of distinct integers from 1 to N^2, such that no two adjacent cells contain elements that differ by 1.
Two cells are adjacent if they touch horizontally, vertically, or diagonally.
EXPLANATION:
Notice that it’d be nice if we could surround even integers with other even integers, and odd integers with other odd integers.
This is because any two distinct integers of the same parity differ by at least 2.
In fact, doing this greedily is enough to construct a valid matrix.
Let’s fill the matrix first with increasing even numbers, then with increasing odd numbers.
For example, for N = 4 we obtain
and for N = 5 we obtain
It’s not hard to see that this matrix works, because when N \geq 4, there is at least one row separating any two integers whose difference is 1 (for example, for N = 4, 5 is in the third row while 4 and 6 are both in the first), so they’ll never be adjacent in the matrix.
TIME COMPLEXITY
\mathcal{O}(N^2) per test case.
CODE:
Setter's code (C++)
#include <iostream>
using namespace std;
void ANS(int n)
{
int curr=2;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(curr>n*n) curr=1;
cout<<curr<<" ";
curr+=2;
}
cout<<endl;
}
}
int main() {
// your code goes here
int t; cin>>t;
while(t--)
{
int n; cin>>n;
ANS(n);
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(range(1, n*n + 1))
a.sort(key = lambda x: (x%2)* (10**9) + x)
for i in range(n): print(*a[i*n:i*n+n])