If the total number of occurrences of some character $$$c$$$ is not a multiple of $$$n$$$, then it is impossible to make all $$$n$$$ strings equal — because then it is impossible for all $$$n$$$ strings to have the same number of $$$c$$$.

On the other hand, if the total number of occurrences of every character $$$c$$$ is a multiple of $$$n$$$, then it is always possible to make all $$$n$$$ strings equal. To achieve this, for every character $$$c$$$ we move exactly ((the total number of occurrences of $$$c$$$) / $$$n$$$) characters $$$c$$$ to the end of each string, and by the end we will have all n strings equal each other.

# it's recommended to use sys.stdin.readline().strip() for faster input processing
import sys
from collections import Counter
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    strings = []
    for i in range(n):
        strings.append(sys.stdin.readline().strip())
    count =Counter()
    for i in range(n):
        for ch in strings[i]:
            count[ch] += 1
    ans = "YES"
    for key in count:
        if count[key] % n:
            ans = "NO"
            break
    print(ans)

To solve this problem efficiently, we can use stack. Here's the step-by-step process:

Initialize an empty stack. Iterate through each character in the input string. If the stack is not empty and the current character is equal to the top of the stack, pop the top character from the stack. Otherwise, push the current character onto the stack. After iterating through all characters, join the characters remaining in the stack to form the final string without adjacent duplicates.

Time Complexity: $$$O(n)$$$, where n is the length of the input string.

Space Complexity: $$$O(n)$$$ This is because the stack can potentially store all characters of the string in the worst case scenario (no adjacent duplicates to remove).

chars = input()
stack = []

for char in chars:
    if stack and stack[-1] == char:
        stack.pop()
    else:
        stack.append(char)
print(''.join(stack))

What's the lower bound for the amount of blocks for the answer to be YES?

Check the predicate for every prefix.

Let's consider the smallest amount of blocks we need to make the first $$$i$$$ heights ascending. As heights are non-negative and ascending the heights should look like $$$0,1,2,3,...,i−1$$$, so the minimum sum is $$$\frac{(i−1) \cdot i}{2}$$$. It turns out that this is the only requirement. If it's not the case for every prefix the answer is NO because we can't make some prefix ascending. Otherwise the answer is YES because you can move the blocks right till there is at least $$$i$$$ blocks in the $$$i$$$-th stack and this would make the heights ascending.

from sys import stdin

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


T = int(input())
for _ in range(T):
    N = int(input())
    a = list(map(int, input().split()))
    need = 0
    have = 0
    ans = True
    for j in range(N):
        need += j
        have += a[j]
        if have < need:
            ans = False
    if ans:
        print("YES")
    else:
        print("NO")

It looks like Tikursew should only reorder the boxes when he has to (i.e. he gets a remove operation on a number which isn't at the top of the stack). The proof is simple: reordering when Tikursew has more boxes is always not worse than reordering when he has less boxes, because Tikursew can sort more boxes into the optimal arrangement. Therefore, our greedy algorithm is as follows: simulate all the steps until we need to reorder, and then we resort the stack in ascending order from top to bottom.

This has complexity $$$O(n^2 log n)$$$. However, we can speed this up if we note that whenever we reorder boxes, any box currently on the stack can be put in an optimal position and we can pretty much forget about it. So whenever we reorder, we can just clear the stack as well and continue. This gives us $$$O(n)$$$ complexity because every element is added and removed exactly once.

# If you use input() to get input, you might encounter TLE (Time Limit Exceeded). Instead,
# it's recommended to use sys.stdin.readline().strip() for faster input processing
import sys
n = int(sys.stdin.readline().strip())
stack = []
ans = 0
cur = 1
for _ in range(2 * n):
    s = list(map(str, sys.stdin.readline().strip().split()))
    if s[0][0] == 'a':
        stack.append(int(s[1]))
    else:
        if stack:
            if cur != stack[-1]:
                ans += 1
                stack = []
            else:
                stack.pop()
        cur += 1
print(ans)

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)    

For each $$$i$$$, find the largest $$$j$$$ that $$$a_j$$$ < $$$a_i$$$ and show it by $$$l_i$$$ (if there is no such $$$j$$$, then $$$l_i = 0$$$).

Also, find the smallest $$$j$$$ that $$$a_j < a_i$$$ and show it by $$$r_i$$$ (if there is no such $$$j$$$, then $$$r_i = n + 1$$$).

This can be done in $$$O(n)$$$ with a stack. Consider that you are asked to print $$$n$$$ integers, $$$ans_1, ans_2, ..., ans_n$$$. Obviously, $$$ans_1 ≥ ans_2 ≥ ... ≥ ans_n$$$.

For each $$$i$$$, we know that $$$a_i$$$ can be minimum element in groups of size $$$1, 2, ..., r_i - l_{i - 1}$$$.

Se we need a data structure for us to do this:

We have array $$$ans_1, ans_2, ..., ans_n$$$ and all its elements are initially equal to $$$0$$$. Also, $$$n$$$ queries. Each query gives $$$x, val$$$ and want us to perform $$$ans_1 = max(ans_1, val), ans_2 = max(ans_2, val), ..., ans_x = max(ans_x, val)$$$. We want the final array.

This can be done in $$$O(n)$$$ with a maximum prefix sum (keeping maximum instead of sum).

Time complexity: $$$\mathcal{O}(n)$$$.

from sys import stdin


def input(): return stdin.readline().strip()

N = int(input())
a = list(map(int, input().split()))

ans = [0]*N

mono_stk = [(0, -1)]
for i, n in enumerate(a):
    while mono_stk[-1][0] >= n:
        prev_n, prev_i = mono_stk.pop()
        prev_prev_i = mono_stk[-1][1]
        prev_window = i - prev_prev_i - 2
        ans[prev_window] = max(ans[prev_window], prev_n)
    cur_window = i - mono_stk[-1][1] - 1
    ans[cur_window] = max(ans[cur_window], n)
    mono_stk.append((n, i))

while len(mono_stk) > 1:
    n, i = mono_stk.pop()
    prev_i = mono_stk[-1][1]
    cur_window = N - prev_i - 2
    ans[cur_window] = max(ans[cur_window], n)

prev = min(a)
for i in range(N - 1, -1, -1):
    ans[i] = max(prev, ans[i])
    prev = ans[i]
print(*ans)