# SMALLESTDIFF - Editorial

Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

2421

Sorting

# PROBLEM:

You are given N, M, and an array B of size N\times M of distinct integers

Consider an N\times M grid A whose values form a permutation of B. The following process is carried out:

• A token is placed at (1, 1) and moved towards (N, M) either right or down each step.
• On odd moves (1-st, 3-rd, etc) the token is moved towards its larger neighbor
• On even moves the token is moved towards its smaller neighbor
• The value of the grid taken equals the difference between the maximum and minimum element on the path.

Construct A such that this value is minimized.

# EXPLANATION:

First, letâ€™s sort B so that B_1 \lt B_2 \lt \ldots \lt B_{NM}.

Without loss of generality, assume N \leq M.

Note that any path from (1, 1) to (N, M) where we move only right and down will visit exactly N+M-1 cells. Let L = N+M-1 be this length.

Now, ideally weâ€™d like the values on our path to be L consecutive values in B, since this is how we minimize the difference between the largest and smallest of them. However, we also need to account for actually being to place these values to form a valid path, so we canâ€™t just choose any subarray of length L.

The less constraints we have, the better.
So, letâ€™s try to make our path go down first (recall that N \leq M), and then go right after it hits the last row. Once we hit the last row, thereâ€™s only one way to go so the maximum/minimum conditions donâ€™t matter anymore and we can freely place anything there, so we only need to worry about the going down part.

Specifically, we need to ensure we choose values such that:

• A_{2, 1} \gt A_{1, 2}
• A_{3, 1} \lt A_{2, 2}
• A_{4, 1} \gt A_{3, 2}
\vdots

Only by doing so can we ensure we move down for the first N steps.
Notice that the value of A_{1, 1} also doesnâ€™t matter whatsoever.

In particular, we have x = \left\lfloor \frac{N}{2}\right\rfloor constraints of the form A_{i, 1} \gt A_{i-1, 2} and y = \left\lfloor \frac{N-1}{2}\right\rfloor of the form A_{i, 1} \lt A_{i-1, 2}.

Of course, the best way to fulfill these is to pair the largest x elements among our chosen ones with the smallest x unchosen elements; and the smallest y chosen elements with the largest y unchosen ones.

In order to fulfill these conditions, we also need to ensure that the smallest x unchosen elements are all smaller than our largest x elements; and the largest y unchosen elements are larger than our smallest y.
In particular, this means that if we pick the subarray [i, i+L-1] then it must satisfy i \gt x and i+L-1+y \leq N\times M.

The minimum difference is thus the minimum value of B_{i+L-1} - B_i across all subarrays that satisfy the above conditions on i, which is easy to find by just iterating across B.

Once youâ€™ve found i, the starting point of the subarray, constructing A is not very hard:

• Place the x largest elements of the chosen subarray at positions A_{2, 1}, A_{4, 1}, A_{6, 1}, \ldots
• Place the elements B_1, B_2, \ldots, B_x at positions A_{1, 2}, A_{3, 2}, \ldots
• Place the y smallest elements of the chosen subarray at A_{3, 1}, A_{5, 1}, \ldots
• Place the elements B_{NM}, B_{NM-1}, \ldots at positions A_{2, 2}, A_{4, 2}, \ldots
• Place all the remaining elements of the subarray at A_{1, 1} and A_{N, 2}, A_{N, 3}, \ldots, A_{N, M} in any order
• Place all the unplaced elements in the grid in some order

After sorting B, the rest of the solution is \mathcal{O}(NM), giving us a solution in \mathcal{O}(NM\log{NM}).

# TIME COMPLEXITY:

\mathcal{O}(NM\log{NM}) per testcase.

# CODE:

Setter's code (C++)
//Utkarsh.25dec
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=1000023;
bool vis[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
int sumNM=0;
int B[N];
set <int> s;
int n,m;
int A[1005][1005];
ll ans;
void fillGrid()
{
int blockers=n-1;
int mini=(blockers+1)/2;
int maxi=blockers/2;
int pathLen=n+m-1;
int optL=0, optR=0;
for(int i=mini+1;i<=n*m;i++)
{
int j=i+pathLen-1;
int rem=n*m-j;
if(rem<maxi)
break;
if(ans>B[j]-B[i])
{
ans=B[j]-B[i];
optL=i;
optR=j;
}
}
int curr=optL;
for(int i=1;i<=n;i++)
{
A[i][1]=B[curr++];
s.erase(A[i][1]);
}
for(int j=2;j<=m;j++)
{
A[n][j]=B[curr++];
s.erase(A[n][j]);
}
int lar=n*m;
int sm=1;
for(int i=1;i<n;i++)
{
if(i%2==1)
A[i][2]=B[sm++];
else
A[i][2]=B[lar--];
s.erase(A[i][2]);
}
for(int i=1;i<n;i++)
{
for(int j=3;j<=m;j++)
{
A[i][j]=(*s.begin());
s.erase(s.begin());
}
}
}
void solve()
{
s.clear();
ans=1e18;

sumNM+=(n*m);
assert(sumNM<=1000000);
for(int i=1;i<=n*m;i++)
{
if(i==n*m)
else
s.insert(B[i]);
}
assert(s.size()==n*m);
sort(B, B+n*m+1);
if(n<=m)
{
fillGrid();
}
else
{
swap(n,m);
fillGrid();
swap(n,m);
int C[n+1][m+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
C[i][j]=A[j][i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
A[i][j]=C[i][j];
}
// cout<<ans<<'\n';
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<A[i][j]<<' ';
cout<<'\n';
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's code (C++)
// Jai Shree Ram

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}

string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------
int solve(){
static int sum = 0;
sum += n*m;
assert(sum <= 1e6);
vector<int> a = readVectorInt(n*m, 1, 1e9);
//for(auto &i: a) cin >> i;
sort(all(a));

auto solve = [&](int n,int m){
int rb = (n - 1)/2;
int lb = (n)/2;
int ans = LLONG_MAX;
int l = 0,r = 0;
for(int i = lb; i < n*m; i++){
int tl = i;
int tr = tl + (n + m - 1) - 1;
if(n*m - tr - 1 < rb) break;
if(a[tr] - a[tl] < ans){
ans = a[tr] - a[tl];
l = tl;
r = tr;
}
}
vector<int> vis(n*m);
int temp = l - 1;

vector<vector<int>> mat(n, vector<int> (m));
for(int i = 0; i < n; i++){
vis[l] = 1;
mat[i][0] = a[l++];
}
for(int j = 1; j < m; j++){
vis[l] = 1;
mat[n - 1][j] = a[l++];
}
for(int i = 0; i + 1 < n; i++){
if(i & 1){
mat[i][1] = a[++r];
vis[r] = 1;
}else{
vis[temp] = 1;
mat[i][1] = a[temp--];
}
}
int tmp = 0;
for(int i = 0; i + 1 < n; i++){
for(int j = 2; j < m; j++){
while(tmp < n*m and vis[tmp]) tmp++;
vis[tmp] = 1;
mat[i][j] = a[tmp];
}
}
return mat;

};
vector<vector<int>> ans(n, vector<int> (m));
if(n <= m){
ans = solve(n,m);
}else{
auto res = solve(m,n);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
ans[i][j] = res[j][i];
}
}
}
for(auto i: ans){
for(auto j: i) cout << j << " ";
cout << endl;
}

return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
while(t--){
solve();
}
return 0;
}
Editorialist's code (Python)
import sys
for _ in range(int(input())):
n, m = map(int, input().split())
b = sorted(list(map(int, input().split())))
st, mindif = -1, 10**10
cells = n+m-1
swap = False
if n < m:
swap = True
n, m = m, n
ans = [0]*(n*m)
for i in range(n*m):
less = m//2
more = (m-1)//2
if i < less: continue
if i + cells + more > n*m: continue

if b[i+cells-1] - b[i] < mindif:
mindif = b[i+cells-1] - b[i]
st = i
used = [0]*(n*m)
lo, hi = 0, n*m-1
L, R = st, st+cells-1
for i in range(m//2):
ans[2*i+1] = b[R]
ans[2*i+m] = b[lo]
used[R] = 1
used[lo] = 1
lo += 1
R -= 1
for i in range((m-1)//2):
ans[2*i+2] = b[L]
ans[2*i+1+m] = b[hi]
used[L] = 1
used[hi] = 1
L += 1
hi -= 1
onpath = [0] + [m-1 + i*m for i in range(1, n)]
for i in range(R-L+1):
ans[onpath[i]] = b[L+i]
used[L+i] = 1

ptr = 0
for i in range(n*m):
if ans[i] != 0: continue
while used[ptr] == 1: ptr += 1
ans[i] = b[ptr]
ptr += 1
if swap == False:
for i in range(n): print(*ans[i*m:i*m+m])
else:
for i in range(m): print(*ans[i:n*m+i:m])
1 Like

@iceknight1093 Could you please guide me as to where am I going wrong with this.

This answer also gives min score = 30.

Thank you!

1 Like

The WA test cases feature currently doesnâ€™t work correctly when a problem can have multiple outputs, so it unfortunately wonâ€™t help you debug your code in this problem.

1 Like

I am facing the same problem.
Even though my code is giving the EXACT same ans that is present in the sample test case it is still showing wrong ans

1 Like