The Best Matrix
Source: codechef
Difficulty: 1710

The Best Matrix
A matrix$A$of size$N \times M$is said to be
best
if and only if all of the following conditions are satisfied:$|A[x_1][y_1] - A[x_2][y_2]| = 1$for all adjacent pair of cells$(x_1, y_1)$and$(x_2, y_2)$$(x_1, y_1)$and$(x_2, y_2)$are said to be adjacent if and only if$|x_1 - x_2| + |y_1 - y_2| = 1$.$A[x][y] = \dfrac{A[x - 1][y] + A[x + 1][y]}{2}$for all$1 < x < N$and$1 \le y \le M$.$A[x][y] = \dfrac{A[x][y - 1] + A[x][y + 1]}{2}$for all$1 \le x \le N$and$1 < y < M$.
You are given a matrix$A$of size$N \times M$, and want to make it a
best
matrix. Find the minimum number of values that need to be changed to obtain a
best
matrix.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains$N$and$M$- the dimensions of the matrix$A$.
The$i$-th of the next$N$lines contains$M$integers -$A_{i, 1}, A_{i, 2}, ..., A_{i, M}$.
Output Format
For each test case, output on a new line the minimum number of changes to turn$A$into a
best
matrix.
Constraints$1 \le T \le 10^3$$1 \le N, M \le 100$$3 \le \max(N, M)$$1 \le A_{i, j} \le 10^9$The sum of$N \cdot M$over all test cases does not exceed$10^4$.
Sample 1:
Explanation:
Test Case 1
: The given matrix is already
best
.
Test Case 2
: The given matrix is not
best
because it does not satisfy the$3^{rd}$condition for$x = 1, y = 3$. We can simply change$A_{1, 4}$to$4$, obtaining$[1, 2, 3, 4]$which is
best
.

Sample Input:
3
1 4
1 2 3 4
1 4
1 2 3 2
2 3
1 2 3
4 5 6

Sample Output:
0
1
3

C++ solution:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tc    \
    int t;    \
    cin >> t; \
    while (t--)
#define _cin_(a, n)              \
    for (auto i = 0; i < n; i++) \
        cin >> a[i];
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit | ios::badbit);
    tc {
        int N, M;
        cin >> N >> M;
        vector<vector<int>> matrix(N, vector<int>(M));
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> matrix[i][j];
            }
        }
        int totalCells = N * M;
        int bestChange = totalCells;
        for (int d1 : {1, -1}) {
            for (int d2 : {1, -1}) {
                unordered_map<long long, int> freq;
                int localMax = 0;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        long long candidate = matrix[i][j] - 1LL * d1 * i - 1LL * d2 * j;
                        freq[candidate]++;
                        localMax = max(localMax, freq[candidate]);
                    }
                }
                bestChange = min(bestChange, totalCells - localMax);
            }
        }
        cout << bestChange << "\n";
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

func minMoves(dancers int, chants int, altar [][]int) int {
    totalCells := dancers * chants
    diagonals := [][2]int{{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
    minMagicMoves := totalCells

    for _, dir := range diagonals {
        shiftX, shiftY := dir[0], dir[1]
        illusion := make([]int, 0, totalCells)

        for i := 0; i < dancers; i++ {
            for j := 0; j < chants; j++ {
                mysticIndex := i*shiftX + j*shiftY
                pureValue := altar[i][j] - mysticIndex
                illusion = append(illusion, pureValue)
            }
        }

        sort.Ints(illusion)
        chain, longest := 1, 1

        for k := 1; k < totalCells; k++ {
            if illusion[k] == illusion[k-1] {
                chain++
                if chain > longest {
                    longest = chain
                }
            } else {
                chain = 1
            }
        }

        movesNeeded := totalCells - longest
        if movesNeeded < minMagicMoves {
            minMagicMoves = movesNeeded
        }
    }
    return minMagicMoves
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    text, _ := reader.ReadString('\n')
    ritualCount, _ := strconv.Atoi(strings.TrimSpace(text))

    for r := 0; r < ritualCount; r++ {
        line1, _ := reader.ReadString('\n')
        parts := strings.Fields(line1)
        dancers, _ := strconv.Atoi(parts[0])
        chants, _ := strconv.Atoi(parts[1])

        altar := make([][]int, dancers)
        for i := 0; i < dancers; i++ {
            rowLine, _ := reader.ReadString('\n')
            rowParts := strings.Fields(rowLine)
            row := make([]int, chants)
            for j := 0; j < chants; j++ {
                row[j], _ = strconv.Atoi(rowParts[j])
            }
            altar[i] = row
        }

        fmt.Println(minMoves(dancers, chants, altar))
    }
}

Java solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Codechef
{
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) 
    {
        FastScanner fs = new FastScanner();
        int t = fs.nextInt();
        for(int c = 0; c<t; ++c)
        {
            int n = fs.nextInt(), m = fs.nextInt(), matrix[][] = new int[n][m];
            for(int i=0; i<n; ++i)
            {
                for(int j=0; j<m; ++j)
                    matrix[i][j] = fs.nextInt();
            }
            out.println(solve(n, m, matrix));
        }
        
        
        out.close();
    }
    
    private static long solve(int n, int m, int[][] matrix)
    {
        long res = (long) n * m;
        int[][] directions = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

            for (int[] d : directions) 
            {
                int ai = d[0], bi = d[1];
                Map<Long, Integer> freq = new HashMap<Long, Integer>();
                int max = 0;
                for (int i = 0; i < n; i++) 
                {
                    for (int j = 0; j < m; j++) 
                    {
                        long num = matrix[i][j] - (long) i * bi - (long) j * ai;
                        freq.put(num, freq.getOrDefault(num, 0) + 1);
                        max = Math.max(max, freq.get(num));
                    }
                }
                res = Math.min(res, (long) n * m - max);
            }

        return res;
    }
    
    static class FastScanner
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next()
        {
            while(!st.hasMoreTokens())
            {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {}
            }
            return st.nextToken();
        }
        
        int nextInt()
        {
            return Integer.parseInt(next());
        }
        
        long nextLong()
        {
            return Long.parseLong(next());
        }
    }
}

JavaScript solution:
function solve(input) {
    const lines = input.trim().split('\n');
    let idx = 0;
    const t = parseInt(lines[idx++]);

    let results = [];

    for (let test = 0; test < t; test++) {
        const [n, m] = lines[idx++].split(' ').map(Number);
        const a = [];
        for (let i = 0; i < n; i++) {
            a.push(lines[idx++].split(' ').map(Number));
        }

        let minChanges = n * m;
        const d_opts = [1, -1];
        const dp_opts = [1, -1];

        for (let d of d_opts) {
            for (let dp of dp_opts) {
                const freq = new Map();
                let maxFreq = 0;

                for (let i = 0; i < n; i++) {
                    for (let j = 0; j < m; j++) {
                        const k = a[i][j] - i * dp - j * d;
                        const count = (freq.get(k) || 0) + 1;
                        freq.set(k, count);
                        maxFreq = Math.max(maxFreq, count);
                    }
                }

                const currentChanges = n * m - maxFreq;
                minChanges = Math.min(minChanges, currentChanges);
            }
        }

        results.push(minChanges);
    }

    return results.join('\n');
}

// Example usage:
const fs = require('fs');
let input = fs.readFileSync(0, 'utf-8'); // For competitive programming platforms
console.log(solve(input));

Python solution:
def prog():
    t = int(input())
    for i in range(t):
        st = input().split()
        N = int(st[0])
        M = int(st[1])
        A = [[0 for x in range(M)] for y in range(N)]
        for y in range(N):
            st = input().split()
            for x in range(M):
                A[y][x] = int(st[x])
            # endfor x
        # endfor y
        mx = 0
        for k in range(4):
            dx = k%2
            dy = k//2
            if dx == 0:
                dx = -1
            # endif
            if dy == 0:
                dy = -1
            # endif
            D = {}
            for y in range(N):
                v = y*dy
                for x in range(M):
                    w = x*dx + v
                    d = w - A[y][x]
                    if d in D:
                        D[d] += 1
                    else:
                        D[d] = 1
                    # endif
                # endfor x
            # endfor y
            for d in D:
                mx = max(mx,D[d])
            # endfor d
        # endfor k
        r = N*M - mx
        print (r)
    # endfor i
# end fun
prog()

Ruby solution:
def main
  t = gets.to_i
  t.times do
    # Read matrix dimensions
    n, m = gets.split.map(&:to_i)
    
    # Read the matrix
    matrix = []
    n.times do
      matrix << gets.split.map(&:to_i)
    end

    max_matches = 0

    # Check all four possible parity patterns
    [-1, 1].each do |dx|
      [-1, 1].each do |dy|
        pattern_counts = Hash.new(0)
        
        n.times do |i|
          m.times do |j|
            # Calculate expected value for this pattern
            expected = i * dy + j * dx
            difference = expected - matrix[i][j]
            pattern_counts[difference] += 1
          end
        end

        # Find the most common difference for this pattern
        current_max = pattern_counts.values.max || 0
        max_matches = [max_matches, current_max].max
      end
    end

    # Minimum changes = total cells - maximum matching cells
    puts n * m - max_matches
  end
end

main