Let's sort the numbers in ascending order. It becomes immediately clear that it is not profitable for us to increase the numbers that are equal to the last number (the maximum of the array). It turns out that every time you need to take such a subset of the array, in which all the numbers, except the maximums. And once for each operation, the numbers in the subset are increased by one, then how many times can the operation be performed on the array? Accordingly $$$max(a)−min(a)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    print(max(nums) - min(nums)) 

We can iterate through the elements of $$$a$$$ and $$$b$$$ simultaneously. For each element $$$a_i$$$, we consider the following cases:

1. If $$$a_i = b_i$$$, no operation is needed, and we move on to the next element.

2. If $$$a_i > b_i$$$, we need to decrease $$$a_i$$$ to match $$$b_i$$$. Since the elements of $$$a$$$ can only be $$$-1$$$, $$$0$$$, or $$$1$$$, the only way to decrease $$$a_i$$$ is by finding an element $$$a_j < i$$$ such that $$$a_j = -1$$$. Subtracting $$$1$$$ from $$$a_i$$$ and adding $$$1$$$ to $$$a_j$$$ does not change the sum of $$$a_i$$$ and $$$a_j$$$, but it decreases $$$a_i$$$ by $$$1$$$. If such an element $$$a_j$$$ does not exist, then it's impossible to transform $$$a$$$ into $$$b$$$.

3. If $$$a_i < b_i$$$, we need to increase $$$a_i$$$ to match $$$b_i$$$. Similarly, the only way to increase $$$a_i$$$ is by finding an element $$$a_j < i$$$ such that $$$a_j = 1$$$. Adding $$$1$$$ to $$$a_i$$$ and subtracting $$$1$$$ from $$$a_j$$$ does not change the sum of $$$a_i$$$ and $$$a_j$$$, but it increases $$$a_i$$$ by $$$1$$$. If such an element $$$a_j$$$ does not exist, then it's impossible to transform $$$a$$$ into $$$b$$$.

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
    
	vals = set()
	ans = True
	for i in range(n):
    	if a[i] != b[i]:
        	if b[i] - a[i] > 0:
            	if 1 not in vals:
                	ans = False
                	break
        	else:
            	if -1 not in vals:
                	ans = False
                	break
    	vals.add(a[i])
	print("YES" if ans else "NO")

First, we can filter out the numbers that have appeared at least $$$k$$$ times in the array and sort them in ascending order.

We will keep track of the start and end of the current range as we iterate through the sorted list. Additionally, we keep track of the maximum range found so far.

Next, We maintain a current range while iterating through the sorted list of numbers. If a number $a_i$​ is consecutive to the previous number $a_{i−1} ie( a_i = a_{i -1} + 1)$​, it is part of the current range. Otherwise, a_i​ marks the start of a new range. We keep track of the maximum range found so far as we iterate through the list.

But, when using a hash table data structure, there's a risk of encountering test cases deliberately crafted to induce collisions. In such scenarios, the worst-case time complexity for retrieval and insertion operations could O(n), impacting the overall time complexity of the solution, which could become O(n2). To remove this risk ,one possible solution is employing XOR with a random number during both insertion and retrieval from the hash table. By XORing each number with a randomly generated value before inserting it into the hash table, we can create unique hash values for each number. This process helps distribute the numbers evenly across the hash table. Similarly, during retrieval, XORing the search key with the same random number allows us to accurately locate the corresponding entry in the hash table.

from collections import Counter
from random import randint

for _ in range(int(input())):
   n, k = map(int, input().split())
   numbers = list(map(int, input().split()))
   rand = randint(10000, 10**10)
   c = Counter([a ^ rand for a in numbers])
   filtered_numbers = [a ^ rand for a in c.keys() if c[a] >= k]
   filtered_numbers.sort()
 
   max_span = -1
   start = end = None
   current_start = current_end = None

   for num in filtered_numbers:
   	if current_end is None or num != current_end + 1:
       	if current_start is not None and current_end is not None:
           	span = current_end - current_start
           	if span > max_span:
               	max_span = span
               	start = current_start
               	end = current_end

       	current_start = current_end = num
   	else:
       	current_end = num

   if current_start is not None and current_end is not None:
   	span = current_end - current_start
   	if span > max_span:
       	max_span = span
       	start = current_start
       	end = current_end
   if start:
   	print(start, end)
   else:
   	print(-1)

Let's consider two sequences of digits: $$$e_1,e_2,…,e_k$$$ and $$$o_1,o_2,…,o_m$$$, there $$$e_1$$$ is the first even digit in $$$a$$$, $$$e_2$$$ is the second even digit and so on and $$$o_1$$$ is the first odd digit in $$$a$$$, $$$o_2$$$ is the second odd digit and so on.

Since you can't swap digits of same parity, the sequence $$$e$$$ of even digits of $$$a$$$ never changed. Sequence $$$o$$$ of odd digits of $$$a$$$ also never changed. So the first digit in the answer will be equal to $$$e_1$$$ or to $$$o_1$$$. And since we have to minimize the answer, we have to chose the $$$min(e_1,o_1)$$$ as the first digit in answer and them delete it from the corresponding sequence (in this way sequence $$$e$$$ turn into $$$e_2,e_3,…,e_k$$$ or sequence $$$o$$$ turn into $$$o_2,o_3,…,o_m$$$). Second, third and followings digits need to choose in the same way.

from sys import stdin


def input(): return stdin.readline()[:-1]

T = int(input())
for _ in range(T):
    num = input()
    evens = []
    odds = []
    for digit in num:
        if int(digit)%2 == 1:
            odds.append(digit)
        else:
            evens.append(digit)
    
    ans = []
    p1 = p2 = 0
    len_evens = len(evens)
    len_odds = len(odds)
    while p1 < len_evens and p2 < len_odds:
        if evens[p1] < odds[p2]:
            ans.append(evens[p1])
            p1 += 1
        else:
            ans.append(odds[p2])
            p2 += 1
    ans.extend(evens[p1:])
    ans.extend(odds[p2:])
    
    print(*ans, sep="")

To ensure that all rows and columns form palindromes, each cell $$$a_{i,j}$$$ should be equal to $$$a_{n−i−1,j}$$$, a_{n−i−1,j}​ , a_{i,m−j−1}, as well as $a_{n−i−1,m−j−1}$​.

so the problem is reduced to finding the optimal number for each four of numbers (maybe less for some positions in the matrix). This number is the median of these numbers (the average of the sorted set). This can be proved by induction. Here is the link for the proof. The answer will be the sum of the differences between the median of the "four" and each number in the "four" for all "fours".

for _ in range(int(input())):
   n,m = map(int,input().split())
   mat = [list(map(int,input().split())) for i in range(n)]
   tot = 0
   for i in range(n):
   	for j in range(m):
       	mid_point = sorted([mat[i][j],mat[i][m-j-1],mat[n-i-1][j],mat[n-i-1][m-j-1]])[2]
       	tot += abs(mat[i][j]-mid_point)
   print(tot)