PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sai1707
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
An N\times M grid A is called best if it satisfies the following conditions:
- Adjacent elements differ by exactly 1.
- 2A_{x, y} = A_{x-1, y} + A_{x+1, y} whenever all three cells are valid.
- 2A_{x, y} = A_{x, y-1} + A_{x, y+1} whenever all three cells are valid.
Given a grid A, find the minimum number of changes needed to make it the best.
EXPLANATION:
The conditions on a grid being best are fairly strong, so let’s try to understand what they actually mean.
Let’s look at the condition on three consecutive elements within a row, i.e. 2\cdot A_{x, y} = A_{x, y-1} + A_{x, y+1}.
If we rearrange this expression a bit, it becomes A_{x, y} - A_{x, y-1} = A_{x, y+1} - A_{x, y}.
In other words, differences between adjacent elements (when going from left to right) must be equal within a row.
Essentially, each row must look like either
x, x+1, x+2, x+3, \ldots or x, x-1, x-2, \ldots
Of course, the exact same applies to each column as well - all adjacent differences must be the same.
So, functionally, we’re just assigning each row and each column a difference of either +1 or -1, and this along with knowing A_{1, 1} will let us know all elements.
In fact, this can be strengthened even further: all row differences must be equal to each other — that is, either every row has a difference of +1, or every row has a difference of -1.
Proof
Suppose there are rows with different differences.
Then, some two adjacent rows, say i and i+1, must have different differences.
Without loss of generality, let’s say that row i has a difference of 1, and row i+1 has a difference of -1.We need to look at a couple of cases now.
First, suppose M \geq 3, i.e. there are at least three columns.
Here, we look at the first three elements of each row.
In row i, suppose they’re x, x+1, x+2; while in row i+1 they’re y, y-1, y-2.
Then,
- |x-y| = 1 should hold, since x and y are adjacent.
So, either x-y = 1 or x-y = -1.- |(x+2) - (y-2)| = 1 should hold, since x+2 and y-2 are adjacent.
This means |x-y+4| = 1, which says either x-y = -5 or x-y = -3.In either case, we obtain a contradiction, so adjacent rows cannot have different differences.
Finally, consider M \lt 3.
If M = 1 then every row is a single element so there’s no row difference at all; this case can be ignored.
So, we need to deal with M = 2.Here, note that the problem constraints guarantee that \max(N, M) \geq 3; so N \geq 3 must hold.
This means that there must either be a row above the i-th one, or a row below the (i+1)-th one.
W.l.o.g. let the row i+2 exist.Now,
- Row i must be [x, x+1], and row i+1 must be [y, y-1].
The only way to satisfy the adjacent difference condition is for y = x+1, so that row i+2 is [x+1, x].- Now, let’s look at row i+2.
To satisfy the column condition, its first element must be x+2 and its second element must be x-1.
However, these don’t have a difference of 1, which is a contradiction!This proves that all the rows must have the same difference, i.e. all +1 or all -1.
This of course applies to the column differences as well.
Note that the common row difference need not be equal to the common column difference.
Now, let’s see what this means for the grid itself.
As noted earlier, if A_{1, 1} is known, and all the row/column differences are known, the entire grid will be known.
However, row/column differences only have two options each, being \pm 1.
Observe that, if the row difference is fixed to be d_r and the column difference is d_c, then for any cell (i, j) we must have
A_{i, j} = A_{1, 1} + d_r\cdot (i-1) + d_c\cdot (j-1).
So, for a fixed choice of differences (d_r, d_c), each cell (i, j) has a unique value of A_{1, 1} for which it doesn’t need to be changed (that being A_{i, j} - d_r\cdot (i-1) - d_c\cdot (j-1), of course); whereas for every other A_{1, 1} it will need to be changed.
Let \text{freq}[x] denote the number of cells that are valid for A_{1, 1} = x. This is the number of cells that don’t need to change, if we set A_{1, 1} = x.
Thus, the minimum number of changes is simply N\times M minus the maximum frequency.
There are only four choices of (d_r, d_c), so we can simply try all of them, compute the minimum number of changes for each, and take the best of the four answers.
TIME COMPLEXITY:
\mathcal{O}(NM\log{NM}) per testcase.
CODE:
Editorialist's code (PyPy3)
import collections
for _ in range(int(input())):
n, m = map(int, input().split())
a = [ list(map(int, input().split())) for _ in range(n) ]
ans = 0
for dr in [-1, 1]:
for dc in [-1, 1]:
freq = collections.defaultdict(int)
for i in range(n):
for j in range(m):
freq[a[i][j] + dr*i + dc*j] += 1
ans = max(ans, max(freq.values()))
print(n*m - ans)
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,m; cin >> n >> m;
ll a[n+5][m+5];
rep1(i,n) rep1(j,m) cin >> a[i][j];
ll ans = 0;
for(auto x : {-1,1}){
for(auto y : {-1,1}){
map<ll,ll> mp;
rep1(i,n){
rep1(j,m){
ll add = (i-1)*x+(j-1)*y;
mp[a[i][j]-add]++;
}
}
for(auto [x,c] : mp){
amax(ans,c);
}
}
}
ans = n*m-ans;
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}