# ODDMATRIX - Editorial

Author: munch_01
Preparer: jay_1048576
Tester: yash_daga
Editorialist: iceknight1093

2644

None

# PROBLEM:

Given N, construct an N\times N matrix that contains each integer from 1 to N^2 exactly once, and also has each row sum and each column sum be odd.

# EXPLANATION:

First, note that the sum of a row/column being odd only depends on the parity of the count of odd integers present in that row/column: the actual values and counts don’t matter.

So, we can instead think of our task as trying to construct a boolean matrix A, such that:

• A has exactly \left\lfloor \frac{N^2}{2} \right\rfloor zeros (and the rest are ones).
• Each row and each column has an odd number of ones.

Once we achieve this, we can place even numbers at the zeros (in any order) and odd numbers at the ones (in any order) and we’ll be done.

As the subtasks hint, we’ll solve for even N and odd N separately.
There are several constructions, I’ll provide a couple of them for both parities.

Odd N
Method 1

We’ll attempt to solve the problem recursively, by placing a certain number of ones and then moving to a (N-2)\times (N-2) square.
For this, we’ll have to:

• Make two rows and two columns have an odd number of ones, while ensuring the rest have an even number (so that the recursion is well-defined).
• Use exactly 2N-2 ones (since that’s the number of odd integers \gt (N-2)^2 and \leq N^2)

One simple way to do this, is to fill the first row with ones, and then place N-2 ones in the second row.
This uses 2N-2 ones, and:

• The first two columns have an odd number of ones; the rest are even.
• The last two columns have an odd number of ones; the rest are even.

Now recursively solve for the remaining N-2 rows and columns.

This results in a pattern that looks like:

\begin{matrix} 111111111 \\ 111111100 \\ 111111100 \\ 111110000 \\ 111110000 \\ 111000000 \\ 111000000 \\ 100000000 \\ 100000000 \end{matrix}
Method 2

It’s possible to do a bit of further casework, depending on whether N = 4k+1 or 4k+3.

N = 4k+3

The following process works:

• If you have at least N ones, fill an entire row with them.
• When you have \lt N ones, place them all in the first column.

Because N = 4k+3, this will completely fill up the first column; and every column will also have an odd number of ones.
The pattern looks like a flag, as in:

\begin{matrix} 1111111 \\ 1111111 \\ 1111111 \\ 1000000 \\ 1000000 \\ 1000000 \\ 1000000 \end{matrix}
N = 4k+1

Repeat the process for 4k+3.
You’ll still end up with a ‘flag’, the only difference now is that all the columns (apart from the first) will have an even number of ones.

To fix this, take the last row that’s all ones, and move alternate ones to the next row; shifting both down and right.
That is, we start off with

\begin{matrix} 111111111 \\ 111111111 \\ 111111111 \\ 1\blue{1}1\blue{1}1\blue{1}1\blue{1}1 \\ 100000000 \\ 100000000 \\ 100000000 \\ 100000000 \\ 100000000 \end{matrix}

Move the ones marked in blue, and obtain

\begin{matrix} 111111111 \\ 111111111 \\ 111111111 \\ 101010101 \\ 10\blue{1}0\blue{1}0\blue{1}0\blue{1} \\ 100000000 \\ 100000000 \\ 100000000 \\ 100000000 \end{matrix}

Which satisfies the necessary conditions.

Even N
Method 1

Similar to the first method for odd N, we will attempt to place a few ones and reduce to the N-2 case.

One way of doing that is to place N-1 ones in the first row in the first N-1 positions, and N-1 ones in the second row in the last N-1 positions.
Both rows have an odd number of ones, the first and last column have an odd number, and everything else is even.

The matrix looks like

\begin{matrix} 11111110 \\ 01111111 \\ 01111100 \\ 00111110 \\ 00111000 \\ 00011100 \\ 00010000 \\ 00001000 \end{matrix}

Note that the smaller (N-2)\times (N-2) matrix we solve is now in the center, rather than on the sides.

Method 2

Just as in the odd N case, it’s possible to do casework here as well, depending on whether N = 4k or N = 4k+2.

N = 4k+2

This one is easy: just arrange zeros and ones in a chessboard pattern!

\begin{matrix} 101010 \\ 010101 \\ 101010 \\ 010101 \\ 101010 \\ 010101 \end{matrix}
N = 4k

There are likely several constructions. Here’s one of them.

\begin{matrix} \blue{1}0101010 \\ 10101010 \\ 10\blue{1}01010 \\ 10101010 \\ 1010\blue{1}010 \\ 10101010 \\ 101010\blue{1}0 \\ 10101010 \\ \end{matrix}

Now, every row and every column has even parity.
To fix it, swap each 1 that lies on the ‘main diagonal’ (marked in blue above) with the zero to its bottom right.
Doing this, we obtain

\begin{matrix} 00101010 \\ 1\blue{1}101010 \\ 10001010 \\ 101\blue{1}1010 \\ 10100010 \\ 10101\blue{1}10 \\ 10101000 \\ 1010101\blue{1} \\ \end{matrix}

and we’re done!

# TIME COMPLEXITY

\mathcal{O}(N^2) per testcase.

# CODE

Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=300005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}

int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

auto readIntVec(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

auto readLongVec(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int32_t main()
{
IOS;
input_checker inp;
int t = inp.readInt(1, 100), sum_n2=0;
while(t--)
{
sum_n2 += n*n;
assert(sum_n2 <= 1e5);
int odd=1, even=2, a[n][n];
fill(a, -1);
if(n&1)
{
rep(i,0,n)
{
a[i]=odd;
odd+=2;
}
for(int i=1;i<n;i+=2)
{
int skip=(i+1)/2;
for(int j=skip;j<n-skip;j++)
{
a[i][j]=odd;
odd+=2;
a[i+1][j]=odd;
odd+=2;
}
}
rep(i,0,n)
{
rep(j,0,n)
{
if(a[i][j]==-1)
{
a[i][j]=even;
even+=2;
}
}
}
}
else
{
for(int i=0;i<n;i+=2)
{
int skip=i/2;
for(int j=skip;j<n-skip-1;j++)
{
a[i][j]=odd;
odd+=2;
a[i+1][j+1]=odd;
odd+=2;
}
}
rep(i,0,n)
{
rep(j,0,n)
{
if(a[i][j]==-1)
{
a[i][j]=even;
even+=2;
}
}
}
}
rep(i,0,n)
{
rep(j,0,n)
cout<<a[i][j]<<" ";
cout<<"\n";
}
}
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())

if n%4 == 0:
ans = list(range(1, n*n+1))
for i in range(0, n, 2):
p, q = i*n + i, i*n + i + n + 1
ans[p], ans[q] = ans[q], ans[p]
for i in range(n):
print(*ans[i*n:i*n+n])
if n%4 == 1:
ans = [ [] for _ in range(n)]
ost, est = 1, 2
lrow = 0
for i in range(n):
if ost + 2*n - 2 <= n*n:
ans[i] = list(range(ost, ost+2*n, 2))
ost += 2*n
lrow = i
else:
ans[i] = [ost] + list(range(est, est+2*n-2, 2))
ost += 2
est += 2*n - 2
for i in range(1, n, 2):
ans[lrow][i], ans[lrow+1][i+1] = ans[lrow+1][i+1], ans[lrow][i]
for i in range(n):
print(*ans[i])
if n%4 == 2:
st = 1
for i in range(n):
if i%2 == 0: print(*list(range(st, st+n)))
else: print(*list(reversed(range(st, st+n))))
st += n
if n%4 == 3:
ans = [ [] for _ in range(n)]
ost, est = 1, 2
for i in range(n):
if ost + 2*n - 2 <= n*n:
ans[i] = list(range(ost, ost+2*n, 2))
ost += 2*n
else:
ans[i] = [ost] + list(range(est, est+2*n-2, 2))
ost += 2
est += 2*n - 2
for i in range(n):
print(*ans[i])

1 Like

There is another approach which is called inductive construction.

Firstly, it’s easy to construct the answer for n=1,n=2.

Secondly, we find that (i+2)^2-i^2 is always a even number, which means that there are the same number of evens and odds, remind us to construct from i \rightarrow i+2.

The basic idea is just match even with even, odd with odd because the inner i \times i matrix is already good. And the last problem is how to fill the elasped 4 blanks.

The anwser is also easy, for n is even, we can construct like

00
11

and for odd we can construct like

10
01
1 Like

For the odd case, printing the magic square will also work as the magic sum (n * (n^2 + 1)) / 2 will be odd when n is odd.

for odd case this construction will work,eg:-n==5
0 0 1 0 0
0 1 1 1 0
1 1 1 1 1
0 1 1 1 0
0 0 1 0 0
for even case this construction will work,eg:-n==6
0 0 1 0 0 0
0 1 1 1 0 0
1 1 1 1 1 0
0 1 1 1 1 1
0 0 1 1 1 0
0 0 0 1 0 0
for printing these patterns we can use two pointers
here 1 are odd nos. and 0 are even nos.