PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Preparer: jay_1048576
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
2644
PREREQUISITES:
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:
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:
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
Move the ones marked in blue, and obtain
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
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!
N = 4k
There are likely several constructions. Here’s one of them.
Start with the ones and zeros in alternating columns, for instance
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
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;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
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) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
else readEoln();
}
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) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
else readEoln();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main()
{
IOS;
input_checker inp;
int t = inp.readInt(1, 100), sum_n2=0;
inp.readEoln();
while(t--)
{
int n = inp.readInt(1, 300); inp.readEoln();
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[0][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])