# MATDIF - Editorial

Authors: shubham_grg
Testers: iceknight1093, tabr
Editorialist: iceknight1093

TBD

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

\begin{bmatrix} 2 & 4 & 6 & 8 \\ 10 & 12 & 14 & 16 \\ 1 & 3 & 5 & 7 \\ 9 & 11 & 13 & 15 \end{bmatrix}

and for N = 5 we obtain

\begin{bmatrix} 2 & 4 & 6 & 8 & 10 \\ 12 & 14 & 16 & 18 & 20 \\ 22 & 24 & 1 & 3 & 5 \\ 7 & 9 & 11 & 13 & 15 \\ 17 & 19 & 21 & 23 & 25 \end{bmatrix}

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() {

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])

1 Like

Not a good problem…I got the solution but it is giving me TLE just because I am printing elements one by one using simple sop statements instead of using stringbuffer :{ !!!

Unfortunately, Java’s default output is extremely slow. If you plan to use Java going forward, it’s important to be aware of this and how to work around it, because simply increasing time limits or lowering constraints might allow suboptimal solutions to pass in faster languages, which is a way worse issue to have.

Both System.out.print and System.out.println flush the output buffer when called, which leads to a massive time loss.
As you can see from your own submissions, using appropriate methods leads to a speedup of 6-7 times, which is extremely huge.

Other languages do have this issue as well: using endl in C++ is bad for the exact same reason, it flushes the buffer; that’s why using '\n' is recommended. The default print function in Python has the same problem, and one can use sys.stdout.write for faster output.

In the end, you do need to be aware of the features and shortcomings of your language, and how to get around them.

2 Likes

Wow, I didn’t even think of this approach. A lot easier than what I did. n = 4 was special case. So I just outputted the sample output for that case.
For the general case, I set the values in serial order starting from 1, iterating in columns and for every column, I set these values in alternate rows, like row, 1,3,5 … and then row, 2,4,…
With this approach, we can also solve for n = 3 case. Here’s the output for n = 5 case for illustration.

1 6 11 16 21
4 9 14 19 24
2 7 12 17 22
5 10 15 20 25
3 8 13 18 23



My submission