PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given an even integer N, find any N\times N grid such that:
- Every integer from 1 to N appears exactly N times.
- Let S_1 denote the sum of elements on the main diagonal, and S_2 the sum of elements on the antidiagonal.
Then, the sum of every two adjacent rows should equal S_1 + S_2. The same applies to any two adjacent columns.
EXPLANATION:
Let’s start with the idea behind the construction to the odd version, and analyze what changes.
The base idea was to choose some permutation as the first row, then set its rotations as the rows - this automatically ensures that all row and column sums are equal, and that all elements along the main diagonal are the same.
However, now that N is even, there is one major change: the antidiagonal is no longer a permutation.
In fact, it can be observed that if the permutation chosen for the first row is P_1, P_2, \ldots, P_N then the antidiagonal contains exactly the elements
P_N, P_{N-2}, P_{N-4}, \ldots, P_2
repeated twice.
So, our job is now to choose P in such a way that
One way to do that is as follows:
Choose P_1 = \frac{N}{2}
This then means we want 2\cdot (P_2 + P_4 + \cdots + P_N) to equal N\cdot (N+1) - \frac{N^2}{2} = \frac{N\cdot (N+2)}{2}
Now, it can be seen that 2 + 4 + 6 + \ldots + N = 2\cdot (1 + 2 + \ldots + \frac{N}{2}) = \frac{N}{2} \cdot (\frac{N}{2} + 1) = \frac{N\cdot (N+2)}{4}
So, quite conveniently for us, choosing P_2, P_4, \ldots, P_N to be the even numbers gives us exactly what we want!
However, there’s one potential issue: we forced P_1 = \frac{N}{2}, but it’s entirely possible for \frac{N}{2} to be even in which case we’d need it at an even position and it can’t actually be P_1.
However, this is easy to fix: we only need to adjust the sum of P_2 + \cdots + P_N while ensuring that \frac{N}{2} isn’t used.
This can be done by, for example, using \frac{N}{2} + 1 in place of \frac{N}{2}, and then using 1 in place of 2 so that the sum remains the same.
As examples, let’s look at N = 6 and N = 8.
For N = 6, there’s no issue: we choose P_1 = \frac{N}{2} = 3 and then choose all the even numbers at the even positions of P.
For example, consider P = [3, 2, 1, 4, 5, 6].
This gives the grid
For N = 8, \frac{N}{2} = 4 is even so we need the adjustment described: instead of choosing all the even numbers at the even positions of P, replace 2 by 1 and \frac{N}{2} by \frac{N}{2} + 1.
For example, let P = [4, 1, 2, 5, 3, 6, 7, 8].
This gives the grid
There are many other constructions possible, likely simpler to describe than this one. Some implementations can be found below.
TIME COMPLEXITY:
\mathcal{O}(N^ 2) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<vector<int>> v(n,vector<int>(n));
for(int i=0;i<n;i++){
int ind=(2*i)%n;
for(int j=0;j<n;j++){
v[i][(ind-j+n)%n]=j;
}
}
for(auto i:v){
for(auto j:i) cout<<j+1<<" ";
cout<<"\n";
}
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
ll a[n][n];
memset(a,-1,sizeof a);
if(n&1){
ll s = 0;
rep1(x,n){
if(x > 1) s = (s+2)%n;
ll j = s;
rep(i,n){
assert(a[i][j] == -1);
a[i][j] = x;
j = (j-1+n)%n;
}
}
}
else{
ll s = n/2-1;
ll dir = -1;
if((n/2)&1) dir = 1;
rep1(x,n){
if(x > 1){
s = (s-1+n)%n;
dir = -dir;
}
ll j = s;
rep(i,n){
assert(a[i][j] == -1);
a[i][j] = x;
j = (j+dir+n)%n;
}
}
}
rep(i,n){
rep(j,n){
cout << a[i][j] << " ";
}
cout << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
grid = [ [0 for _ in range(n)] for _ in range(n) ]
if n%2 == 0:
for i in range(n//2):
for j in range(n//2):
grid[i][j] = grid[i+n//2][j+n//2] = (j-i)%(n//2) + 1
for j in range(n//2):
grid[i][j+n//2] = grid[i+n//2][j] = (i+j)%(n//2) + n//2 + 1
else:
for i in range(n):
for j in range(n):
grid[i][j] = (n//2 + 1 + i + j)%n + 1
for row in grid: print(*row)
.
