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 odd 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:
Every element from 1 to N appearing exactly N times means the sum of the entire grid must be
(1 + 2 + \cdots + N) \cdot N = \frac{N\cdot N\cdot (N+1)}{2}
Now, suppose the sum of the diagonal and antidiagonal elements equals S.
We want every pair of adjacent rows and columns to sum up to S.
In particular, if x is the sum of the first row, and y is the sum of the second row,
- x+y = S must hold.
- This forces the third row to have a sum of x, since it should equal S when added to y (which is the second row’s sum).
- This then forces the fourth row to have a sum of y, then the fifth row is forced to have a sum of x, and so on.
In general, the sum of rows 1, 3, 5, \ldots must be equal; and the sum of rows 2, 4, 6, \ldots must be equal.
Similarly, the sum of all odd-numbered columns must be equal, and the sum of all even-numbered columns must be equal.
Now, let’s do a bit of wishful thinking.
Instead of odd/even, let’s just try to make all rows and columns have the same sum.
One way to achieve this is to make every row and every column a permutation, i.e., contain every integer from 1 to N.
A rather simple way to achieve this is as follows:
- Start with the first row being [1, 2, \ldots, N].
- Form the remaining rows as rotations of the first row.
For example, with N = 5 we’d obtain
Now, we didn’t really consider what happens to the diagonals when this is done.
Note that one of the diagonals (the antidiagonal) is itself a permutation, with a sum of \frac{N\cdot (N+1)}{2}.
Meanwhile, the main diagonal contains all 1's.
We want the sum of both diagonals to equal N\cdot (N+1). Since one diagonal is a permutation, we just need a way to make the main diagonal have a sum of \frac{N\cdot (N+1)}{2} itself.
Here’s where we use the fact that N is odd.
Observe that there was really nothing special about the first row being [1, 2, \ldots, N].
We could have started with any permutation at all, and set the rows to its rotations - this would still result in every row, every column, and the antidiagonal being permutations. The only difference is that the main diagonal would contain copies of not 1, but whichever element is at the top-left corner.
So, let K = \frac{N+1}{2}.
Choose any permutation that has K as its first element and set that to be the first row.
The sum of the main diagonal then becomes N\cdot K = \frac{N\cdot (N+1)}{2}, and all the conditions will be satisfied.
For example, with N = 5, we have K = 3. If the first row is made [3, 4, 5, 1, 2] we obtain the grid
This isn’t the only construction: there are many others possible.
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)