You should count the number of parentheses at the end of the string, suppose there are $$$x$$$ such parentheses. Then if $$$X$$$ is greater than $$$n - X$$$ the answer is “Yes”, otherwise “No”.

testcase = int(input())
for _ in range(testcase):
    n = int(input())
    S = input()
    count = 0
    for i in range(n-1,-1,-1):
        if S[i] != ')':
            break
        count += 1
    if count > n - count:
        print("Yes")
    else:
        print("No")

Consider two cases:

The array is already sorted. THe array is not sorted.

In the first case, sorting any prefix and any suffix does not change the array. So the array will always remain sorted so the answer is "NO".

In the second case, it is guaranteed that there will be two elements with indexes $$$i$$$ and $$$j$$$, such that $$$i < j$$$ and $$$ai > aj$$$. So choose len so that these two elements will be in different parts. For example — $$$len = i$$$. Note that after operation $$$ai$$$ will remain to the left of $$$aj$$$, which means the array will not be sorted. So the answer is "YES".

Then the solution is to check if the array is sorted, which can be done in O(n), or O(nlogn) by sorting a copy of the array using built-in sorting algorithms.
.

testcase = int(input())

for _ in range(testcase):
    n = int(input())
    nums = list(map(int, input().split()))
    
    for i in range(1, n):
        if nums[i] < nums[i-1]:
            print("YES")
            break
    else:
        print("NO")

n will always be beautiful because we can take the entire given array. What must happen for n — 1 to be beautiful?

Either the first n — 1 elements should be a permutation of n — 1 or the last n — 1.

Doesn’t that mean the maximum of the first and the last element should be n?

Can we extend this for n — 1, n — 2, … 1 ?

We can use the deque data structure to solve this problem. Initially we know that n is always beautiful. To check if n — 1 is beautiful, we compare the first and the last elements in our deque, and remove the maximum of the two. We pop from the left or right accordingly. Then all the numbers from 1 uo to n — 1 must be present in the deque. For that to be the case the minimum element we have popped so far must be strictly greater than n — 1. We do the same thing for n — 2 as well. We pop the maximum of the first and the last elements from the leftover elements in our deque, and keep track of the minimum element we have popped so far. That element should be strictly greater than n — 2 for n — 2 to be beautiful. If that is not the case, it means some number in the range 1 to n — 2 (inclusive) was popped. Therefore our deque is not a permutation of n — 2 as we need all the numbers from 1 to n — 2 to say so.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

from collections import deque

t = int(input())
for _ in range(t):

    n = int(input())
    permutation = deque(map(int, input().split()))

    is_beautiful = ['0'] * n
    is_beautiful[n - 1] = '1' # n(n - 1 for 0 - indexed) is beautiful
    
    min_popped = float('inf')
    for num in range(n - 2, -1, -1):

        if permutation[0] > permutation[-1]:
            min_popped = min(min_popped, permutation.popleft())
        else:
            min_popped = min(min_popped, permutation.pop())
        
        if min_popped > num + 1: # num is 0-indexed so we need num + 1 for 1-indexed
            is_beautiful[num] = '1'
    
    print(''.join(is_beautiful))
    

1 will always be beautiful. What must happen for 2 to be beautiful?

2 must be present right after 1 or just before 1.

How can we extend this for 3, 4, 5, … n ?

Let’s first have the indices of each number stored in a dictionary. Let’s also have two pointers l, r. Initially we will assign the index of 1 for both. r — l + 1 indicates the size of the subarray that starts at l and ends at r. Now to check if 2 is beautiful, we first update l and r to include both $$$1$$$ and $$$2$$$. To do this we replace l with min(l, index of 2) and r with max(r, index of 2). After the updates we know both 1 and 2 are included in the subarray that starts at l and ends at r, and that subarray is the smallest sized subarray to do so. So if r — l + 1 is equal to 2, then 2 is beautiful, but if that’s not the case r — l + 1 is greater than 2 which indicates that there is no subarray of size two that includes both 1 and 2 assuring us that a permutation of 2 is not present in the given array as a subarray. We keep doing this for all the other numbers.

Time and space complexities

• Time Complexity: O(n)
• Space Complexity: O(n)

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))

    indices = {}
    for i in range(n):
        indices[arr[i]] = i
    
    l, r = indices[1], indices[1]
    is_beautiful = ['0'] * n
    is_beautiful[0] = '1' # 1 is beautiful

    for i in range(2, n + 1):
        
        l = min(l, indices[i])
        r = max(r, indices[i])

        if r - l + 1 == i: 
            is_beautiful[i - 1] = '1' 
    
    print(''.join(is_beautiful))

    

To efficiently determine the minimum number of moves, consider how to group elements based on their remainders when divided by ( k ) and track how many elements need to be adjusted to the same remainder.

The problem requires modifying an array such that all elements become divisible by ( k ) using two types of operations. A naive approach would involve brute-force testing every possible modification, leading to inefficiency. Instead, we can use the following optimized strategy:

• For each element ( a_i ), compute its remainder when divided by ( k ) (i.e., ( r = a_i \mod k )). If ( r = 0 ), the element is already valid.
• For all elements where ( r \neq 0 ), calculate the required increment ( k — r ) to make them divisible by ( k ).
• Use a hashmap to count how many times each increment value appears since we can only apply each increment once per element.
• The key observation is that for each unique remainder value, we must adjust multiple elements in steps of ( k ). The maximum time required is given by the highest calculated increment considering the repeated occurrences.
• Thus, for each unique remainder ( r ), the maximum move count is determined by ( k — r + (count — 1) \times k ), where ( count ) is the frequency of that remainder in the array.

Finally, the answer for each test case is the maximum move count among all remainder groups plus one (to account for the starting move).

from collections import defaultdict
def solve():
    n, k = map(int, input().split())
    table = defaultdict(int)
    nums = list(map(int, input().split()))
    for num in nums:  
                r = num % k  
                if r:  
                    table[k - r] += 1  

    ans = 0  
    for key, val in table.items():  
            ans = max(ans, key + (val - 1) * k)  

    print(ans + 1 if ans else 0)  
for _ in range(int(input())):
 	solve()

Let's consider three offsets of string "RGB": "RGB", "GBR" and "BRG".

Let's compare our string s with infinite concatenation of each offsets of "RGB". However, we don't need an infinite string to compare. n-sized string could be enough. We don't either need to create n-sized string. We can observe that in the concatenated string the first character of the offset will always be on an index which is a multiple of 3 (whose modulo 3 is 0), the second character will be on an index whose modulo 3 is 1, the third character will be on an index whose modulo 3 is 2.

We can use fixed sliding window and compare the character in that window. While comparing we will count the matches and keep track of the maximum matches in k -sized window. We can then find the minimum number of changes we need to make by subtracting the number of maximum matches from k .

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    s = input()

    offsets = ["RGB", "GBR", "BRG"]
    ans = float('inf')

    for offset in offsets:
        matches = 0
        for right in range(K): # Calculate the matches for first K elements
            if offset[right%3] == s[right]:
                matches += 1
        
        max_matches = matches
        for right in range(K, N):
            left = right - K
            if offset[right%3] == s[right]:
                matches += 1
            if offset[left%3] == s[left]:
                matches -= 1
            
            max_matches = max(matches, max_matches)
        
        ans = min(ans, K - max_matches)
    
    print(ans)

Polycarpus has two circular sequences of hieroglyphs $$$a$$$ and $$$b$$$. Since a computer stores sequences linearly, he must flatten each circle into a string. However, the cut position (where the circle is broken) can vary, affecting the order of hieroglyphs in the resulting string.

Our goal is to determine the longest contiguous substring of the first sequence that appears as a subsequence in the second sequence, considering the optimal way to "cut" the circle.

We can first create a set to store the position of each element in the $$$b$$$. This allows us to quickly check if an element from $$$a$$$ exists in $$$b$$$ and retrieve its position in constant time.

We maintain two pointers. A left_pointer that marks the start of the current valid substring of $$$a$$$. And a right_pointer expands the substring to find the longest valid one. We also track the sum of index differences in $$$b$$$ to ensure the substring respects the order of the $$$b$$$ and doesn't exceed its length ($$$b$$$'s length).

We extend right_pointer while ensuring that the next element exists in $$$b$$$, the order in $$$b$$$ is maintained and the total shift does not exceed the length of $$$b$$$.

When the left_pointer moves, we update the sum of index differences to maintain correctness. This ensures that we explore all possible valid substrings efficiently.

The time complexity is going to be $$$O(l_a + l_b)$$$ because it processes both sequences linearly using a sliding window approach, ensuring efficient substring exploration.The space complexity is $$$O(l_b)$$$ because we store the positions of elements from $$$b$$$ in a set.

import sys

input = lambda: sys.stdin.readline().strip()

# Read input values
len_a, len_b = map(int, input().split())
arr_a = list(map(int, input().split()))
arr_b = list(map(int, input().split()))

# Store positions of elements in arr_b
position = {}
for index in range(len_b):
    position[arr_b[index]] = index

max_subarray_length = 0
current_sum = 0
right_pointer = 0

for left_pointer in range(len_a):
    if right_pointer < left_pointer:
        right_pointer = left_pointer
        current_sum = 0
    elif left_pointer > 0:
        difference = position[arr_a[left_pointer]] - position[arr_a[left_pointer - 1]]

        if difference < 0:
            difference += len_b

        current_sum -= difference

    if arr_a[left_pointer] not in position:
        continue

    while right_pointer < left_pointer + len_a - 1:
        value = arr_a[(right_pointer + 1) % len_a]
        if value not in position:
            break

        difference = (
            position[arr_a[(right_pointer + 1) % len_a]]
            - position[arr_a[right_pointer % len_a]]
        )

        if difference < 0:
            difference += len_b

        if current_sum + difference >= len_b:
            break

        right_pointer += 1
        current_sum += difference

    sub_array_length = right_pointer - left_pointer + 1
    max_subarray_length = max(sub_array_length, max_subarray_length)

print(max_subarray_length)