If for all i $$$(1≤i≤n−1)$$$ is true $$$|a_{i}−a_{i+1}|=5$$$ or $$$|a_{i}−a_{i+1}|=7$$$ , the answer to the problem is “YES”, otherwise it is “NO”.

Complexity: O(n)

t = int(input())
for _ in range(t):
    n = int(input())
    notes = list(map(int,input().split()))
    flag = True
    for i in range(1,n):
        diff =abs(notes[i]-notes[i-1])  
        if diff != 7 and diff != 5:
            flag = False
    if flag:
        print('YES')
    else:
        print('NO')

Observation

The position of the maximum value in the array never changes. If an element is the maximum at the start, it will continue to be the maximum after any number of operations.

Why?

• The operations only increment or decrement the elements within a given range.
• If the current maximum is not within the range of an operation, it remains unchanged.
• If the current maximum is within the range, it either increases by 1 (for + l r) or decreases by 1 (for - l r).

Approach

• Initialize:

  • Find the initial maximum value of the array and store it as curr_max.

• Process Each Operation:

  • For each operation, check if curr_max lies within the range [l, r].
  • If curr_max is within the range:
    • If the operation is + l r, increment curr_max by 1.
    • If the operation is - l r, decrement curr_max by 1.
  • If curr_max is not within the range, it remains unchanged.

• Collect Results:

  • Store the current maximum after each operation.

• Output:

  • Print the maximum value after each operation for each test case.

Complexity Analysis:

• Time Complexity: O(n + m) per test case:
• O(n) for finding the initial maximum.
• O(m) for processing the operations.
• Space Complexity: O(m) for storing the result.

import sys 
input = sys.stdin.readline 

def solve():
    n, m = map(int, input().split())
    nums = list(map(int, input().split()))
    result, curr_max = [0] * m, max(nums) 

    for i in range(m):
        op, l, r = map(str, input().split())
        if int(l) <= curr_max <= int(r):
            if op == '+':
                curr_max += 1
                result[i] = curr_max
            else:
                curr_max -= 1
                result[i] = curr_max
            
            continue
        
        result[i] = curr_max

    print(*result)

if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

According to the statement, to the left of the road there should be no less elements ai such that ai=0 than such that ai=1 , and to the right of the road there should be no less elements ai than such that ai=1 than such that ai=0 .

We will consider each position of the road and check the compliance with the road design condition. To do this, we will use the prefix sum method to access the number of 1 's in the suffix in O(1) (the number of such i that i>x and ai=1 for any x ). We will also maintain the count of 0 's among the elements to the left of the road and the optimal answer. If the road position x is suitable and it is closer to the middle than the most optimal answer found before, we will update it (and will not forget to increase the count of 0 if the next element ax+1=0 ).

It is convenient to double the distance to the middle of the village: instead of ∣∣n2−i∣∣ , consider it as 2∣∣n2−i∣∣=|n−2⋅i| . This way, we can get rid of calculations in non-integer numbers.

Complexity: O(n)

for case in range(int(input())):
    n = int(input())
    a = input()
    suf_cnt = [0] * (n + 1)
    for i in range(n — 1, -1, -1):
        suf_cnt[i] = suf_cnt[i + 1] + (a[i] == '1')
    pref_cnt = 0
     
    opt_ans = -1
    opt_dist = n * 2
    threshold = (n + 1) // 2
     
    for i in range(n + 1):
        if pref_cnt >= (i + 1) // 2 and suf_cnt[i] >= (n - i + 1) // 2 and abs(n - 2 * i) < opt_dist:
            opt_dist = abs(n - 2 * i)
            opt_ans = i
        if i != n:
            pref_cnt += (a[i] == '0')
     
    print(opt_ans)

First we determine the overlapping range where all the runners will be present in, we can do this by having a right and a left variable that we shrink based on each runners range.

If there is no range where they overlap, then we return -1 , if the photographer is already within that range, we return 0, if not we return the number of steps it would take him to get to the range.

Time complexity: $$$O(n)$$$

n , x = list(map(int,input().split()))
left, right  = 0, 1000
for _ in range(n):
    a,b = list(map(int,input().split()))
    a,b = min(a,b), max(a,b)
    left,right = max(left,a),min(right,b)
if left > right:
    print(-1)
elif x <= left:
    print(left-x)
elif x>=right:
    print(x-right)
else:
    print(0)

First we figure out how many times we need to iterate through the array or how many layers exist in the array. We can find that the number of layers is $$$\frac{min(n,m)}{2}$$$.

After this we need to define the start and end of each side of the the layer we are iterating on $$$i$$$.

For the top layer we can take: from $$$i$$$ to $$$m-i$$$ as the column where $$$i$$$ is the row

For the right side layer we can take: from $$$i+1$$$ to $$$n-i-1$$$ as the row where the column is $$$m-i-1$$$

For the bottom part of the layer: backwards from $$$m-i-1$$$ to $$$i-1$$$ is the column where $$$n-1-i$$$ is the row

For the left side of the layer: backwards from $$$n-i-2$$$ to $$$i$$$ is the row where $$$i$$$ is the column

As we traverse the above iterations for one layer we keep appending to a list which then we can iterate through normally to figure out if the patter appears. One edge case is when the pattern appears at the end of out traversal and ends at the beginning of out traversal. For this case we can append the first three elements of out layer to the end of out list again.

Time complexity: $$$O(n*m)$$$

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    mat = []
    for i in range(n):
        mat.append(list(input()))
    count = 0
    for i in range (min((n//2),(m//2))):
        curr = []

        for j in range(i, m-i):
            curr.append(mat[i][j])

        for j in range(i+1, n-i-1):
            curr.append(mat[j][m-i-1])

        for j in range(m-i-1, i-1, -1):
            curr.append(mat[n-i-1][j])

        for j in range(n-i-2, i, -1):
            curr.append(mat[j][i])
        
        curr.extend(curr[:3])

        for j in range(len(curr)-3):
            if curr[j:j+4] == ['1','5','4','3']:
                count+=1

    print(count)

Let us describe each cell of the field by four numbers $$$(x_b, y_b, x_s, y_s), 0 ≤ x_b, y_b, x_s, y_s ≤ 2)$$$, where $$$(x_b, y_b)$$$ are coordinates of small field containing the cell, and $$$(xs, ys)$$$ are coordinates of the cell in it's small field. It can be seen that for cell with "usual" coordinates $$$(x, y), 1 ≤ x, y ≤ 9$$$ and our new $$$(x_b, y_b, x_s, y_s)$$$, there are following equalities which give us a key to go between coordinate systems:

In terms of new coordinates, if last move was in cell $$$(x_b, y_b, x_s, y_s)$$$, then next move should be in arbitrary free cell with coordinates $$$(x_s, y_s, x', y')$$$ for some if it's possible; otherwise, next move can be done in arbitrary free cell. To solve the problem, one can go through all such pairs $$$(x', y')$$$ and write "!" in each empty cell $$$(x_s, y_s, x', y');$$$ if there are not such empty cells, write "!" in all empty cells of the field.

grid = []
#taking input
for i in range(11):
    #removing the space inbetween
    line = ''.join(input().split())

    #ignoring empty lines
    if line == "":
        continue

    grid.append(list(line))


x,y  = map(int,input().split())

#calculating the start of the box of the next move using the last input
startr = (((x-1)%3))*3
startc = (((y-1)%3))*3

#iterating through the valid cells inside the box and modifiying if they're available
flag = False
for i in range(startr,startr+3):
    for j in range(startc,startc+3):
        if grid[i][j] =='.':
            flag = True
            grid[i][j] = '!'

# if there were no available cell in the box then we can move anywhere so mark all available spots
if not flag:
    for i in range(9):
        for j in range(9):
            if grid[i][j] == '.':
                grid[i][j] ='!'

# since we removed all the empty spaces that are also required in the final output
# we need to reinsert them in final output 
ans = []
for i in range(11):
    if i == 3 or i == 7:
        ans.append('')
    else:
        curr = []
        for j in range(11):
            if j == 3 or j == 7:
                curr.append(' ')
            else:
                curr.append(grid[i-(i//4)][j-(j//4)])
        ans.append(curr)

#output the answer
for line in ans:
    print(''.join(line))