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)

What if the maximum number is at the front of the deque?

It can be noted that if the deque has the largest element of the deque in the first position, then during the next operations it will remain in the first position, and the second one will be written to the end each time, that is, all the elements of the deque starting from the second will move cyclically left.

• Let's go over the deque and find the largest element by value. We will perform the operation described in the statements until the maximum position is in the first position and save the elements in the first and second positions by the operation number. In order to pre-calculate all pairs until the moment when the maximum position is found, it is enough to make no more than one pass through the deque, since in the worst case, the maximum element can be located at the end of the deque.
• Denote as $$$maxIndex$$$ the position of the maximum element. Then if $$$m_{j} \lt maxIndex$$$, simply return a pair of numbers from the pre-calculated array.
• Otherwise $$$A$$$ is equal to the maximum element, and $$$B$$$ is equal to the deque element with the index $$$((m_{j} − (maxIndex + 1)) \mod{(n−1)}) + 1$$$ in $$$0-indexing$$$ (since we performed the operations until the moment when the maximum position is in the first position, this maximum element is now recorded in the first position).

from collections import deque

n, q = map(int, input().split())
a = deque(map(int, input().split()))
if not q:
    exit()

queries = []
for _ in range(q):
    queries.append(int(input()))

# precalc stores the pre-calculated values of A and B until the maximum number is fixed at the first position
precalc = [[0, 0] for _ in range(n + 1)]
_max = max(a)
maxIndex = 0 

while a[0] != _max:
    A, B = a.popleft(), a.popleft()
    precalc[maxIndex + 1] = [A, B]
    if A > B:
        a.appendleft(A)
        a.append(B)
    else:
        a.appendleft(B)
        a.append(A)

    maxIndex += 1

ans = []
for m in queries:
    if m > maxIndex:
        ans.append([_max, a[(m - (maxIndex + 1))%(n - 1) + 1]])
    else:
        ans.append(precalc[m])
    

for pair in ans:
    print(*pair)

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  \lt  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)