Let's sort the array in nonincreasing order. Now the answer is some of the first flash-drives. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem. Complexity: $$$O(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

The goal is to find a greater element for each element in our array. So, consider sorting the array to achieve this.

If our array consists of unique elements, the answer will always be $$$N - 1$$$ (where $$$N$$$ is the size of our array).

Preserve the larger numbers to represent their preceding larger numbers.

As mentioned in the hints, If our array consisted of unique elements, the answer would always be N — 1, where N is the size of our array. Here’s why:

• After sorting the array, for every number in our array, the next number can always replace it because it will always be greater than it, except for the last (maximum) number.
• So, we can safely replace all elements except the largest one.

Handling Duplicates:

To handle duplicates, we’ll use two pointers: left and right. Left represents the current smaller number that needs to be replaced. Right represents the current immediate larger element compared to the first number. We’ll greedily choose the next immediate larger element for the smaller number. This ensures that we have a larger number greater than the smaller one to replace it.

N = int(input())
arr = list(map(int, input().split()))
arr.sort()
left = 0

for right in range(N):
    if arr[right] > arr[left]:
        left += 1
       
print(left)

Suppose we have an array $$$a$$$ that we want to construct, with elements $$$a_{1},a_{2},…,a_{n}$$$. To simplify the process, let's assume that the elements of a are sorted in non-decreasing order, meaning $$$a_{1}≤a_{2}≤⋯≤a_{n}$$$.

Let's start with $$$a_{1}$$$. Since the elements of $$$a$$$ are sorted, the pairs $$$(a_{1},a_{2}),(a_{1},a_{3}),…,(a_{1},a_{n})$$$ will have $$$a_{1}$$$ as the smallest element in each pair. Therefore, the number of occurrences of $$$a_{1}$$$ in array b will be $$$n−1$$$.

Moving on to $$$a_{2}$$$, we already know that $$$a_{1}$$$ appears $$$n−1$$$ times in $$$b$$$. Since the elements of $$$a$$$ are sorted, all pairs involving $$$a_{2}$$$ will have $$$a_{2}$$$ as the second smallest element. This means $$$a_{2}$$$ will appear $$$n−2$$$ times in array $$$b$$$.

We continue this process for each element $$$a_{i}$$$ in $$$a$$$. The number of occurrences of $$$a_{i}$$$ in array $$$b$$$ will be $$$n−i$$$.

We can't determine the exact value of $$$a_{n}$$$, because it won't be written to array $$$b$$$. Therefore, for an we can choose any number in the range $$$[a_{n−1};10^9]$$$.

In case there are multiple elements $$$b_{i}$$$ in array $$$b$$$ that satisfy the condition for a particular $$$a_{i}$$$, we choose the smallest $$$b_{i}$$$. This greedy approach works, because we are constructing $$$a$$$ in non-decreasing order.

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int,input().split()))
    nums.sort()
    ans = []
    c = n - 1
    i = 0
    while i < len(nums):
     
        ans.append(nums[i])
        i += c
        c -= 1
 
    ans.append(10**9)
    print(*ans)

For every number in a sequence, we can store the sum of the sequence with that number removed in a hashmap.

Storing a sum with a number removed is computed for every number, so the space complexity will be linear. As a value for each difference we will store the index of the sequence and the index of the sum within the sequence. This way if we find the same sum in another sequence, we will have access to the required answer.

k = int(input())
sequences = []
for _ in range(k):
    n = int(input())
    a = list(map(int, input().split()))
    sequences.append(a)

encountered_sums = {}

for j in range(k):
    sequence = sequences[j]
    seq_tot = sum(sequence)

    for y in range(len(sequence)):
        dif = seq_tot - sequence[y]

        # if the difference exists it shouldn't be in the same sequence
        if dif in encountered_sums and encountered_sums[dif][0] != j:
            # i = the sequence index where we saw this dif before, x the index of the number removed to get this sum in sequence i
            i, x = encountered_sums[dif] 
            print('YES')
            print(i + 1, x + 1)
            print(j + 1, y + 1)
            exit()

        # store the sequence sum with the current number excluded
        encountered_sums[dif] = (j, y)

print('NO')

To determine the order of removals, we start from the end of the string. The last character represents the latest removed character. Moving backward, when encountering a character not seen before, it implies that this character was removed in the next step. Thus, we initiate the process from the last character, and each new character encountered denotes the one removed prior. Once we establish this order, we need to reverse it. Now that we have the removal order, the next step is to verify whether the resulting string could have originated from that order. To check this, we first need to assess whether the character counts are valid. If a character was removed first, its actual occurrence in the original string should match its count in the given string. If removed second, the real occurrence in the original string is the count in the given string divided by 2, and so on. After obtaining the counts for each character in the original string, if the sum yields a non-integer number, the given string is invalid. However, if it results in an integer, we proceed to check if the given string can be derived from the first $$$k$$$ characters of the original string $$$k$$$ representing the sum of the counts. To do this, we perform the same operations on the word containing the first $$$k$$$ characters of the given string. After obtaining the result, we compare it with the given string. If they match, we can confidently print the obtained removal order and the original string (which is the first $$$k$$$ characters of the given string). If not, we print $$$-1$$$ as the given string is not valid.

t = int(input())
for _ in range(t):
   s = input()
  
   arr = []
   got = set()
   count = Counter(s)
   for i in s[::-1]:
       if i not in got:
           arr.append(i)
       got.add(i)
   arr.reverse()
   occur = []
   pos = 1
   for i in range(len(arr)):
       occur.append(count[arr[i]] / (i + 1))
   left = 0
   if math.ceil(sum(occur)) != int(sum(occur)):
       pos = 0
 
   if pos:
       ans = ""
       cur = s[:int(sum(occur))]
       j = 0
  
       while cur:
           ans += cur
           stk = ""
           for i in cur:
               if i != arr[j]:
                   stk += i
           cur = stk
           j += 1
       if ans != s:
           pos = 0
   if pos:
       print(s[:int(sum(occur))],"".join(arr))
   else:
       print(-1)

To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $$$O(n)$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ma = 0
    for ch in s:
        ma = max(ma, ord(ch))
    print(ma - 96)
  

What if we use a fixed size sliding window?

To obtain a segment of $$$k$$$ cells with black color, we must paint all the white cells within that segment black. We then consider all segments of length $$$k$$$ (there are only $$$n - k$$$ such segments) and choose the one with the fewest white cells on it. Implementing this involves using a sliding window of size $$$k$$$. Since we have only two colors, we can simplify our implementation by only using two pointers.

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


    recolored = n
    black_count = 0
    left = 0
   
    for right, color in enumerate(s):
        black_count += (color == 'B')


        if right - left + 1 == k:
            recolored = min(recolored, k - black_count)
            black_count -= (s[left] == 'B')
            left += 1


    print(recolored)

Underline every letter $$$w$$$, so that it can't be mistaken with $$$vv$$$. The string splits into segments of letters $$$v$$$. Out of each pair of consecutive letters $$$v$$$ at least one should be underlined. So for the minimum amount you can underline either all the odd positions of the segment or all the even ones. Thus, if the length of the segment is $$$len$$$ , then $$$⌊len/2⌋$$$ underlined letters is enough.

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

    left = 0
    underline = 0

    for right in range(len(s)):
        if s[right] == 'w':
            if s[left] == 'w':
                underline += 1
                
            else:
                underline += 1 + (right - left)//2

            left = right + 1
        
    if left < len(s):
        underline += (len(s) - left)//2
    
    print(underline)

Because the constraints are small, brute forcing it is possible. So, check if every number inside your array can be expressed as a subarray sum.

Use two pointers technique to efficiently find subarrays with sums equal to the current element.

We're given an array of numbers and we're trying to find out how many special numbers are there in the array. A special number is one that can be expressed as the sum of two or more consecutive numbers in the array. To solve this, we'll go through each number in the array one by one and check if it satisfies the condition of being special. We'll do this by considering it as a potential sum of consecutive numbers starting from the beginning of the array. We'll keep track of the sum of these consecutive numbers as we move through the array.

Here's how it works: Imagine we're at a certain number in the array. We start considering it as the sum of consecutive numbers starting from the first number in the array. As we move forward, we add each number to our running sum. If at any point our running sum equals the current number, and we've considered at least two numbers in the subarray (because a single number by itself doesn't count as a sum of consecutive numbers), then we've found a special number. We'll count this and move on to the next number in the array.

By repeating this process for each number in the array, we'll be able to count all the special numbers. This approach allows us to efficiently find special numbers without needing to store all the possible consecutive sums separately. It's a straightforward method that checks each number individually to determine if it's special.

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


    count = 0
    for num in a:
        left = 0
        run_sum = 0
        for right in range(n):
            run_sum += a[right]
            while run_sum > num:
                run_sum -= a[left]
                left += 1           
            if run_sum == num and left < right:
                count += 1
                break
   
    print(count)

Consider sorting the array.

A sliding window where the right most number minus the left most number is $$$<= 2$$$ could tell us a lot of information.

For a window size $$$m$$$, where $$$m >= 3$$$, if the right most number minus the left most number is $$$<= 2$$$, how many triples can we form if we take the current right element as the maximum value? Lets label the numbers in the window as $$$w_{1}, w_{2}, w_{3}, ..., w_{m - 2}, w_{m - 1}, w_{m}$$$. Now if we fix the maximum value to be $$$w_{m}$$$:

• For $$$w_{m - 1}$$$ as the middle value, we can take the remaining $$$m - 2$$$ numbers, $$$w_{1}, w_{2}, w_{3}, ..., w_{m - 2}$$$, to be the minimum number.
• For $$$w_{m - 2}$$$ as the middle value, we can take the remaining $$$m - 3$$$ numbers, $$$w_{1}, w_{2}, w_{3}, ..., w_{m - 3}$$$, to be the minimum number.

.
.
.
• For $$$w_{2}$$$ as the middle value, we can take the remaining number $$$w_{1}$$$ to be the minimum number.

From the above possible middle values, in total, we can form $$$(m - 2) + (m - 3) + ... + 1$$$ triples.

Hence, with the current right value we can form $$$(m - 2)*(m - 1)/2$$$ triples.

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

    left = 0
    triples = 0

    for right in range(n):
        num = a[right]
        while num - a[left] > 2:
            left += 1

        win_size = right - left + 1            
        if win_size >= 3:
            triples += (win_size - 2)*(win_size - 1)//2

    print(triples)

Let's see how to check if all digits of $$$x$$$ are different. Since there can be only $$$10$$$ different numbers($$$0$$$ to $$$9$$$) in single digit, you can count the occurrences of $$$10$$$ numbers by looking all digits of $$$x$$$. You can count all digits by using modulo $$$10$$$ or changing whole number to string.

For example, if $$$x = 1217$$$, then occurrence of each number will be $$$[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$$$, because there are two $$$1$$$s, single $$$2$$$ and single $$$7$$$ in $$$x$$$. So $$$1217$$$ is invalid number.

Now do the same thing for all $$$x$$$ where $$$l \le x \le r$$$. If you find any valid number then print it. Otherwise print $$$-1$$$.

Time complexity is $$$O((r-l) \log r)$$$.

# Return if given number's digits are distinct.
def is_distinct(x):
    return len(set(str(x))) == len(str(x))

L, R = map(int, input().split())

found = False
for i in range(L, R+1):
    if is_distinct(i):
        found = True
        print(i)
        break
    
if not found:
    print(-1)

If s is palindromic initially, we can operate on the interval [1,n], the answer is $$$Yes$$$.

Let's consider the other case. In a palindrome s, for each $$$i$$$ in $$$[1,⌊n/2⌋]$$$, $$$s_i=s_{n−i+1}$$$ must hold. For those $$$i$$$, we may check whether $$$s_i=s_{n−i+1}$$$ is true in the initial string. For all the illegal positions $$$i$$$, the operation must contain either $$$i$$$ or $$$n+1−i$$$, but not both. For the legal positions, the operation must contain neither of $$$i$$$ nor $$$n+1−i$$$, or both of them.

If the illegal positions is continuous (which means that they are $$$l,l+1,…,r−1,r$$$ for some $$$l$$$ and $$$r$$$), we may operate on the interval $$$[l,r]$$$ (or $$$[n+1−r,n+1−l]$$$), making the string palindromic. The answer is $$$Yes$$$.

Otherwise, there must be some legal positions that lie between the illegal ones. Suppose the illegal positions range between $$$[l,r]$$$ (but not continuous). This interval covers all the legal positions that lie between the illegal ones but does not cover their symmetrical positions. Thus, such kind of operation will produce new illegal positions. In other words, there are no valid operations in this situation. The answer is $$$No$$$.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    found = False
    last = None
    ans = "Yes"
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            if not found:
                found = True
            else:
                if i - 1 != last:
                    ans = "No"
                    break
            last = i
            
    print(ans)

Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness.to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. Total complexity: $$$O(n)$$$

from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
count = Counter(nums)
ans = 0
while len(count) > 0:
    ans += (len(count) - 1)
    keys = list(count.keys())
    for key in keys:
        count[key] -= 1
        if count[key] == 0:
            del count[key]
print(ans)

On the constraints, the size of the array cannot be larger than 2000.

We can use two pointers (non-linearly). One starts from the zero, and stores the numbers in a set (left set) to mark them as seen. For every position on the left, as long as the items in the left set are unique, we use a right pointer and move backwards as long as the number on the right pointer satisfies following conditions:

• It is not in the left set.
• The number is not repeated on the right (we can use a right set for every left).

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

min_segment = float('inf')
left_seen = set()
a.append(0) # appended to handle edge cases (to avoid writing if conditions) 

for left in range(n):

    num = a[left]
    right_seen = set()

    for right in range(n, left - 1, -1):
        if a[right] in left_seen or a[right] in right_seen:
            break

        right_seen.add(a[right])
        min_segment = min(min_segment, right - left)
    
    if num in left_seen:
        break

    left_seen.add(num)
    

print(min_segment)

What can we say about the position of the maximum elements relative to $$$[l,r]$$$?

Iterate over the middle maximum element and choose $$$[l,r]$$$ greedily.

First we need to notice, that two of the maximums are at the ends of $$$[l,r]$$$, otherwise we can move one of the boundaries closer to the other and improve the answer.

Using this observation we can reduce the problem to the following: choose three indices $$$l<m<r$$$, such that $$$b_l+b_m+b_r−(r−l)$$$ is maximum.

Now, let's iterate over the middle index $$$m$$$ and rewrite the function as $$$b_m+(b_l+l)+(b_r−r)$$$. We can see, that values in the braces are pretty much independent — on of them depends only on the index $$$l$$$ and the second one depends only on the index $$$r$$$ . So, for a given $$$m$$$ we can choose the numbers $$$l$$$ and $$$r$$$ greedily! To make it fast enough we can pre calculate the prefix maximum for the array $$$b_l+l$$$ and the suffix maximum for array $$$b_r−r$$$.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    prefix = []
    suffix = []
    for i in range(n):
        prefix.append(nums[i] + i)
        suffix.append(nums[i] - i)
    for i in range(1, n):
        prefix[i] = max(prefix[i], prefix[i - 1])
        suffix[n - i - 1] = max(suffix[n - i - 1], suffix[n - i])
    ans = float("-inf")
    for i in range(1, n - 1):
        ans  = max(ans, prefix[i - 1] + nums[i] + suffix[i + 1])
    print(ans)

Let's sort the array in nonincreasing order. Now the answer is some of the first containers. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: $$$\mathcal{O}(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

Note that for each question, the resulting array is

So, the sum of the elements of the new array after each question is

We can compute $$$a_1+⋯+a_{l−1}$$$ and $$$a_{r+1}+⋯+a_n$$$ in $$$\mathcal{O}(1)$$$ time by precomputing the sum of all prefixes and suffixes, or alternatively by using the prefix sums technique. So we can find the sum each time in $$$\mathcal{O}(1)$$$ per question, and just check if it's odd or not. The time complexity is $$$\mathcal{O}(n+q)$$$.

from itertools import accumulate
from sys import stdin


# Fast input for python. Note that it gives you the input with the newline character, '\n'
# This may cause a problem on string problems. In that case, use stdin.readline()[:-1] to strip the last character('\n')
def input(): return stdin.readline()


T = int(input())
for _ in range(T):
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))

    pref_sum = list(accumulate(a, initial=0))

    for __ in range(Q):
        l, r, k = map(int, input().split())
        left_sum = pref_sum[l - 1]
        right_sum = pref_sum[-1] - pref_sum[r]
        middle_sum = k*(r - l + 1)
        total_sum = left_sum + middle_sum + right_sum

        if total_sum%2 == 1:
            print("YES")
        else:
            print("NO")  

The key observation is that to choose an element $$$b_i$$$, we need to consider all elements $$$b_j$$$ where $$$j < i$$$. The objective is to select consecutive elements starting from the first element to maximize the cumulative sum. This principle applies to both the $$$r$$$ and $$$b$$$ sequences.

we can compute the prefix sum for both $$$r$$$ and $$$b$$$. To determine the optimal reconstruction of the original sequence $$$a$$$, we add the maximum prefix sum values from both the $$$r$$$ and $$$b$$$ sequences.

import itertools

t = int(input())

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

    r = list(itertools.accumulate(r))
    b = list(itertools.accumulate(b))

    result = max(0, max(r)) + max(0, max(b))
    print(result)

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use normal line sweep to store cumulative sums. Finally sort both arrays (the prefix sum array and the main array) and sum the product of the elements on the same index from both arrays.

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

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

from itertools import accumulate
from sys import stdin


def input(): return stdin.readline()


N, Q = map(int, input().split())
nums = sorted(map(int, input().split()))

line = [0]*(N + 1)
for _ in range(Q):
    l, r = map(int, input().split())
    line[l - 1] += 1
    line[r] -= 1

counts = sorted(accumulate(line[:-1]))

ans = 0
for i in range(N):
    ans += counts[i]*nums[i]

print(ans)

To determine the order of removals, we start from the end of the string. The last character represents the latest removed character. Moving backward, when encountering a character not seen before, it implies that this character was removed in the next step. Thus, we initiate the process from the last character, and each new character encountered denotes the one removed prior. Once we establish this order, we need to reverse it.

Now that we have the removal order, the next step is to verify whether the resulting string could have originated from that order. To check this, we first need to assess whether the character counts are valid. If a character was removed first, its actual occurrence in the original string should match its count in the given string. If removed second, the real occurrence in the original string is the count in the given string divided by 2, and so on. After obtaining the counts for each character in the original string, if the sum yields a non-integer number, the given string is invalid. However, if it results in an integer, we proceed to check if the given string can be derived from the first $$$k$$$ characters of the original string $$$k$$$ representing the sum of the counts.

To do this, we perform the same operations on the word containing the first $$$k$$$ characters of the given string. After obtaining the result, we compare it with the given string. If they match, we can confidently print the obtained removal order and the original string (which is the first $$$k$$$ characters of the given string). If not, we print $$$-1$$$ as the given string is not valid.

t = int(input())
for _ in range(t):
   s = input()
  
   arr = []
   got = set()
   count = Counter(s)
   for i in s[::-1]:
       if i not in got:
           arr.append(i)
       got.add(i)
   arr.reverse()
   occur = []
   pos = 1
   for i in range(len(arr)):
       occur.append(count[arr[i]] / (i + 1))
   left = 0
   if math.ceil(sum(occur)) != int(sum(occur)):
       pos = 0
 
   if pos:
       ans = ""
       cur = s[:int(sum(occur))]
       j = 0
  
       while cur:
           ans += cur
           stk = ""
           for i in cur:
               if i != arr[j]:
                   stk += i
           cur = stk
           j += 1
       if ans != s:
           pos = 0
   if pos:
       print(s[:int(sum(occur))],"".join(arr))
   else:
       print(-1)

To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $$$O(n)$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ma = 0
    for ch in s:
        ma = max(ma, ord(ch))
    print(ma - 96)
  

We are interested in the sum of a interval of a given sequence. This can be done by calculating the prefix sum of the sequence beforehand. That is,$$$sv_i = \sum_{j=1}^{i} (v_j)$$$ let . The sum of numbers in the interval $$$[l, r]$$$ would then be $$$sv_r - sv_{l - 1}$$$. we can sort sequence $$$v$$$ to obtain sequence $$$u$$$. We can deal with sequence $$$u$$$ likewise.

Preprocessing takes $$$O(n)$$$ time, and answering a query is only $$$O(1)$$$. The total complexity would be $$$O(nlogn + q)$$$.

n = int(input()) 
nums = list(map(int, input().split()))
q = int(input()) 

def calc_prefix(arr):
    res = [arr[0]]
    for i in range(1, len(arr)):
        res.append(res[-1] + arr[i])
    return res
sorted_nums = sorted(nums)
arr1 = calc_prefix(nums)
arr2 = calc_prefix(sorted(nums))
for _ in range(q):
    a, l, r = map(int, input().split())
    if a == 1:
        print(arr1[r - 1] - arr1[l - 1] + nums[l - 1])
    else:
        print(arr2[r - 1] - arr2[l - 1] + sorted_nums[l - 1])
  

First, we need to determine how many times each operation will be performed. For instance, if our query is $$$1, 3$$$, and $$$2, 5$$$ then $$$2$$$ and $$$3$$$ will be done twice since they fall within two ranges, while the rest will be done once. To calculate this, we can use a prefix sum with range updates.

Next, for each operation $$$l, r, d, and$$$ $$$v$$$ (where $$$v$$$ represents the number of times it will be performed), we'll increment all elements from $$$l$$$ to $$$r$$$ inclusive by $$$d*v$$$. This can also be efficiently computed using a prefix sum with range updates.

prefix sum with range updates: Let's think about a somewhat easier problem first. What if we were asked to add a constant value to the suffix of the array starting at index l, for multiple queries? Instead of updating the whole suffix for each query, we can only increment the first index of the suffix for each query, $$$i.e a[l]+=k$$$. Then after all queries, we take the prefix sum of the whole array. This will "propagate" our increments till the end of the array and thus our task of updating the whole suffix is accomplished at the end, after taking prefix sums. Now, what about updating the range $$$[l…r]$$$? Can you decompose this range update as $2 suffix updates? It can be decomposed as such:

if you need to increment the range $$$[l…r]$$$ by $$$k$$$, you can increment the suffix starting at index $$$l$$$ by $$$k$$$ and decrement the suffix starting at index $$$r+1$$$ by $$$k$$$, i.e perform the operations $$$a[l]+=k$$$ and $$$a[r+1]−=k$$$ for each query and then take the prefix sum of the array as before.

A visual summary:

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
 
op = []
for _ in range(m):
    op.append(list(map(int, input().split())))
    
q = [0]*(m+1)
for _ in range(k):
    l, r = (map(int, input().split()))
    q[l-1] += 1
    q[r] -= 1
    
for i in range(m-1):
    q[i+1] += q[i]
 
update = [0]*(n+1)
for query in range(m):
    l,r,d = op[query]
    update[l - 1] += d*q[query]
    update[r] -= d*q[query]
for i in range(n-1):
    update[i+1] += update[i]
for i in range(n):
    a[i] += update[i]
print(*a)	

There is always one sheep that shouldn't move.

Let's denote by k the number of sheep in the string, and by $$$x_1,x_2,…,x_k$$$ $$$(1≤x_1<x_2<…<x_k≤n)$$$ their positions in the string. Note that in the optimal solution the sheep with the number $$$m=⌈n/2⌉$$$ will not make moves. This can be proved by considering the optimal solution in which the sheep with the number m makes at least one move. if it moves to the right all sheep that are to the left of $$$x_m$$$( $$$x_1,x_2,…,x_{m-1}$$$) will move by one to the right but not all the sheep that are on the left side of $$$x_m$$$( $$$x_{m+1},x{m+2},…,x_k$$$) will decrease their movement by one and same thing if the $$$m-th$$$ sheep move to the left. So we can conclude that this solution is not optimal. Consider sheep with numbers from i=1 to n

Then the final position of the $$$i-th$$$ sheep will be $$$x_m−m+i$$$, and the answer will be $$$\sum\limits_{k = 0}^n |xi−(xm−m+i)|$$$, since all the sheep have to move from $$$x_i$$$ to $$$x_m-m+i$$$.

testcases = int(input())
for _ in range(testcases)
    n = int(input())
    s = input().strip()
    cnt = s.count('*') # total count of sheeps
    pos = -1 # hold the position of the mth sheep
    cur = -1 
    for i in range(n):
        if s[i] == '*':
            cur += 1
            if cur == cnt // 2:
                pos = i

    ans = 0
    # pos -> xm cnt//2-> and i =-> 0
    cur = pos - cnt // 2
    for i in range(n):
        if s[i] == '*':
            ans += abs(cur - i)
            cur += 1

    print(ans)

Let the sum of elements from the beginning be $$$p_i$$$. $$$[l,r]$$$ is bad if the sum of all the elements between that range equals $$$r - l + 1$$$. so $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$.

Rewrite the formula $$$pr−pl + 1 = r−l + 1$$$.

Let's precalculate the array $$$p$$$, where $$$pi=\sum\limits_{j = 0}^{i - 1} a_j$$$(so $$$p_x$$$ is the sum of the first $$$x$$$ elements of $$$a$$$). Then subarray $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$, so $$$pr−r=pl−l$$$.

Thus, we have to group all prefixes by value $$$pi−i$$$ for $$$i$$$ from $$$0$$$ to $$$n$$$. And if x indexes have a prefix with the same value of $$$pi−i$$$ then we have to add $$$x(x−1)/2$$$ to the answer.

from collections import defaultdict
testcases = int(input())
for _ in range(testcases):
    n = int(input())
    a = input()
    d = defaultdict(int)
    d[0] = 1
    res, s = 0, 0
    
    for i in range(n):
        s += int(a[i])
        x = s - i - 1
        d[x] += 1
        
        res += d[x] - 1
        
    print(res)

Here are two solutions.

Solution 1. Iterate through the string character by character. If $$$s_i=R$$$, then $$$t_i=R;$$$ otherwise, if $$$s_i=G$$$ or $$$B$$$, then $$$t_i=G$$$ or $$$B$$$. If the statement is false for any $$$i$$$, the answer is $$$NO$$$. Otherwise it is $$$YES$$$.

Solution 2. Replace all $$$B$$$ with $$$G$$$, since they are the same anyway. Then just check if the two strings are equal. In either case the complexity is $$$O(n)$$$ per testcase.

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    t = input()
    flag = True
    for i in range(n):
        if (s[i] == "R" and t[i] != "R") or (s[i] != "R" and t[i] == "R"):
            flag = False
            break
    if flag:
        print("YES")
    else:
        print("NO")
  

We can delete all zeros from the array, and it won't affect on answer. Maximum sum is $$$\sum_{i=1}^{n} (a_i)$$$. Minimum number of operations we should do is the number of subarrays with negative values of elements.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    
    total_sum = 0
    count = 0
    neg_found = False
    for num in nums:
        total_sum += abs(num)
        if num < 0 and not neg_found:
            neg_found = True
            count += 1
        if num > 0:
            neg_found = False
 
    print(total_sum, count)
  

In a valid substring, all characters must be the same. The objective is to change every character in the substring to the one that appears most frequently, using at most K changes. If the required changes exceed K, the substring isn't valid. Utilizing a dynamic sliding window approach, we begin with two pointers: a right pointer that increments while staying within K changes and a left pointer that moves right when the substring becomes invalid. During this process, we change the character with the minimum frequency to the character with the maximum frequency with an operation that equals the minimum frequency. We keep track of the largest valid substring size encountered.

n,k = list(map(int,input().split()))
s  = input()
count = {"a":0,"b":0}
ans = 0
left = 0

for right in range(n):

   count[s[right]]+=1
   while min(count.values()) > k:
       count[s[left]]-=1
       left+=1
   ans = max(ans,right - left + 1)

print(ans)

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)

Calculate the total number of participants that can join the contest for hour 1.

Use the sliding window algorithm to calculate the rest.

For hour 1 at the first timezone, it will be hour 2 for the second, and so forth. participants from timezone $$$s$$$ to timezone $$$f - 1$$$ are eligible to join the contest. For the second hour, it becomes $$$s - 1 - f - 2$$$, and so forth. If we have the count of contestants participating in the first hour, we can use a sliding window technique to compute the rest. Our answer is updated only when we discover a larger sum.

$$$Note$$$ Since the array is circular and our pointer might be out of bound we have to use mod to correct it

n = int(input())
arr = list(map(int , input().split()))
s , f = map(int , input().split())
 
ans = 1
# The window when time = 1 at first timezone
cur_total = sum(arr[s - 1:f - 1])


left = s - 1 # the leftmost element in our window
right = f - 2 # the rightmost element in our window


max_value = cur_total


for i in range(2 , n + 2):
   
   cur_total -= arr[right]
   right -= 1
   left -= 1  
   # When left and right < 0 that means they start iterating from the back    
   cur_total += arr[left]


   if cur_total > max_value:
       ans = i
       max_value = cur_total
print(ans if ans else n)	

In the context of maximizing earnings by adding at most $$$(m)$$$ negative elements, the optimal solution involves sorting the array in non-decreasing order and summing up the first at most $$$m$$$ (possibly zero) negative numbers.

Time complexity: O($$$(nlogn)$$$) where $$$n$$$ is the number of TV Sets we have Space complexity: O(1)

n, m = map(int, input().split())
tvSets = list(map(int, input().split()))    
tvSets.sort()
ans = 0
# iterate over tv sets m time
for i in range(m):
    # sum up negative numbers only
    if tvSets[i] < 0:
        ans += tvSets[i]
    else:
        break
print(-ans)

We can delete all zeros from the array, and it won't affect the answer.

The maximum sum is Σ (from i=1 to n) |ai|. The minimum number of operations we should do is the number of continuous subsequences with negative values of elements.

Total complexity: O(n) Space complexity: O(1)

T = int(input())

for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    total_sum = 0
    negative_subsequences = 0
    is_negative_subsequence = False
    
    for element in a:
        total_sum += abs(element)
        
        if element < 0 and not is_negative_subsequence:
            is_negative_subsequence = True
            negative_subsequences += 1
        
        if element > 0:
            is_negative_subsequence = False
 
    print(total_sum, negative_subsequences)

Let’s calculate the maximum number of problems we can take, and the answer will be n subtracted by that count.

An arrangement that always minimizes the absolute difference between adjacent pairs is the array in sorted order. What we notice, is that if the array is sorted, we will always take a subarray (all taken elements will be consecutive).

So, the problem converts to finding the largest element subarray for which ai — ai — 1 <= k. It’s easy to see that all the subarrays are totally different (don’t share any intersection of elements), thus, we can maintain a count variable of the current number of elements in the current subarray, and iterate through array elements from left to right. If we currently are at i and ai — ai — 1 > k then we just set the count to 1 since we know a new subarray starts, otherwise, we just increase our count by 1. The answer will be n subtracted by the largest value that our count has achieved.

Time complexity: O(nlogn) Space complexity: O(1)

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    a.sort()
    
    cnt = 1
    ans = 1
    
    for i in range(1, n):
        if a[i] - a[i - 1] > k:
            cnt = 1
        else:
            cnt += 1
        ans = max(ans, cnt)
    
    print(n - ans)

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

Iterates through the array, starting from the second index, comparing each element to its leftmost minimum and right neighbor. If at any point the current element is greater than both its leftmost minimum elements and right neighbors, the answer is 'NO', indicating the absence of a valid valley. Otherwise, the answer remains 'YES' and we will update the leftmost minimum element.

Time complexity: O(n), n is length of the array Space complexity: O(1)

# iterating over the test cases
 for _ in range(int(input())):
    n = int(input())
    nums = list(map(int, input().split()))
    indx = 1
    ans = 'YES'
    leftMin = nums[0]
    # iterate over the array starting from the second index
    while indx <= n - 2:
        # compare current element with leftmost minimum elements and right neighbors
        if leftMin < nums[indx] > nums[indx + 1]:
            ans = 'NO'
            break
        leftMin = min(leftMin, nums[indx])
        indx += 1
    print(ans)

The problem can be efficiently solved using the two-pointer technique. Let's denote the first pointer as left (l) and the second pointer as right (r). For each position of left, we move the right end right until, on the substring s[l, l+1, ..., r], it is possible to make no more than k swaps to transform this substring into a beautiful one. We then update the answer with the length of this substring and move left to the right.

Time complexity: O(n) Space complexity: O(1)

n, k = map(int, input().split())
s = input()

left = 0
b = 0
max_length = 1

# Handling 'b' characters
for right in range(n):
    if s[right] == 'b':
        b += 1

    # Move the left pointer until it's possible to make no more than k swaps
    while b > k:
        if s[left] == 'b':
            b -= 1
        left += 1

    max_length = max(max_length, right - left + 1)

# Reset pointers and handle 'a' characters
left = 0
a = 0

for right in range(n):
    if s[right] == 'a':
        a += 1

    # Move the left pointer until it's possible to make no more than k swaps
    while a > k:
        if s[left] == 'a':
            a -= 1
        left += 1

    max_length = max(max_length, right - left + 1)

print(max_length)

One way to solve the problem is by iterating through the grid and, when a letter is found, continuing downwards until the entire word is obtained.

However, there is a faster coding approach: simply input each character and output it if it is not a dot. This method works because the characters are inputted in the same top-to-bottom order. The time complexity remains constant, denoted as O(1), regardless of the approach used.

tc = int(input())
 
for _ in range(tc):
    result = []
    for i in range(8):
        result += [char for char in input() if char.isalpha()] 

    print("".join(result))

It is apparent that we can perform a z-sort on any given array, denoted as $$$(nums)$$$ Let's define $$$(k)$$$ as the count of even positions within $$$(nums)$$$ We can assign the maximum $$$(k)$$$ elements to those even positions, and distribute the remaining $$$(n-k)$$$ elements to the odd positions. It's clear that the resulting array will be z-sorted.

n = int(input())
nums = list(map(int,input().split()))

result = [0]*n

nums.sort()

k = n-1
for i in range(1, n, 2):
    result[i] = nums[k]
    k-= 1

for i in range(0, n, 2):
    result[i] = nums[k]
    k-= 1

print(*result)

We will do the following steps inorder to solve it Sort the given sequence in non-decreasing order. The first $$$(k)$$$ elements of the sorted sequence will be the smallest $$$(k)$$$ elements. Any number smaller than or equal to $$$(a[k-1])$$$' will have exactly $$$(k)$$$ elements less than or equal to it. If is $$$(k)$$$ is 0 , the smallest possible value is 1.

n, k = list(map(int, input().split()))
 
nums = list(map(int, input().split()))
 
nums.sort()

if n==k:
	print(nums[k-1])
elif n > k and nums[k] > nums[k-1]:
	print(nums[k-1])
elif k == 0 and nums[0] > 1:
	print(1)
else:
	print(-1)

For each element $$$a_{ij}$$$ , if it lies on the main diagonal $$$(i - j = 0)$$$, secondary diagonal $$$(i + j = n - 1)$$$, middle row $$$(i = n/2)$$$, or middle column $$$(j = n/2)$$$, it is added to the total sum; otherwise, it is skipped.

Consider a line represented by the string "LRRLL". If the ith person turns around, the value of the line will change by specific amounts for each person. For example, if the second person turns around, they will see 3 people before and 1 person after, so the value of the line changes by -2.

Now, to solve this problem efficiently, we can follow these steps:

1. Calculate the change in value for each person in the line if they were to turn around. This will create an array or list of values representing the change in value for each person.
2. Sort this array or list of values in decreasing order. This will help us determine which person turning around will yield the maximum increase in the overall value.
3. Calculate the total values of each person in the line as they were in their original position.
4. Create a result array
5. Traverse through the sorted list of values I. assign the sum of total values and each values in the sorted array to the total sum II. append this result to the result array

This approach, based on sorting the value changes and then greedily selecting the individuals whose turning around increases the overall value, ensures a time complexity of O(n log n) per test case, where 'n' represents the number of people in the line.

for _ in range(int(input())):
    n = int(input())
    lines = input()
    values = []
    totCount = 0
    # getting the total counts of each person in current line
    # and getting the maximized count of each persons by swapping the persons view direction
    for i, line in enumerate(lines):
        if line == 'L':
            totCount += i
            values.append(max(i, n - i - 1) - i)
        else:
            totCount += (n - i - 1)
            values.append(max(i, n - i - 1) - (n - i - 1))
    
    # sort values in decreasing order to maximize the counts
    values.sort(reverse=True)
    for i in range(len(values)):
        totCount += values[i]
        values[i] = totCount
    
    print(*values)

For each element $$$a_{ij}$$$ , if it lies on the main diagonal $$$(i - j = 0)$$$, secondary diagonal $$$(i + j = n - 1)$$$, middle row $$$(i = n/2)$$$, or middle column $$$(j = n/2)$$$, it is added to the total sum; otherwise, it is skipped.

Create a separate matrix with the same dimension and size and Initially, set all all values of this newly created matrix to $(1).

If any corresponding cell in the given matrix is $$$(0) make all the rows and columns of that corresponding cell in the newly created matrix to $$$(0).

Examine this newly created matrix if it can generate the given matrix. If it cannot produce the given matrix, the answer is clearly “NO”.

    n, m = map(int, input().split())
    matrix = []
    for _ in range(n):
        matrix.append(list(map(int, input().split())))
    
    # reconstructing the original matrix
    original = [[1 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                for k in range(n):
                    original[k][j] = 0
                for t in range(m):
                    original[i][t] = 0
    # perform the OR operation on the original matrix
    newMatrix = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            newMatrix[i][j] |= int(any(original[i] + [original[k][j] for k in range(n)]))
    
    # compare the new matrix with the given matrix
    if newMatrix == matrix:
        print('YES')
        for i in range(n):
            print(*original[i])
    else:
        print('NO')

For this problem you just need to implement what it asks you. To be able to implement it you need to know about the "if" statement.

t  = int(input())
for _ in range(t):
    rating = int(input())
    if rating >= 1900:
        print("Division 1")
    elif 1600 <= rating <= 1899:
        print("Division 2")
    elif 1400 <= rating <= 1599:
        print("Division 3")
    else:
        print("Division 4")

Note that during encryption, only characters different from $$$c$$$ are added after the character $$$c$$$. However, when the character $$$c$$$ is encrypted with different characters, another $$$c$$$ character is added to the string.

This means that for decryption, we only need to read the characters of the string after $$$c$$$ until we find the first character equal to $$$c$$$. It signals the end of the block of characters that will be converted to the character $$$c$$$ during decryption.

To decrypt the entire string, we decrypt the first character $$$s1$$$. Let the next occurrence of the character $$$s1$$$ be at position $$$pos1$$$. Then the next character of the original string is $$$s_{pos1+1}$$$. We apply the same algorithm to find the next paired character and so on.

T = int(input())
for _ in range(T):
    n = int(input())
    s = input()
    new_string = []
    l = 0
    r = 0
    while r < len(s):
        if s[l] == s[r] and l != r:
            new_string.append(s[l])
            r += 1
            l = r
        else:
            r += 1
    ans = "".join(new_string)
    print(ans)	

Let's sort AASTUs and AAiTs by skill. If AASTU with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use AAiT with lowest skill to match.

N = int(input())
aastu = sorted(map(int, input().split()))

M = int(input())
aait = sorted(map(int, input().split()))

pairs = 0
p1 = 0 # pointer of aastu array
p2 = 0 # pointer of aait array

while p1 < N and p2 < M:
    if abs(aastu[p1] - aait[p2]) <= 1:
        pairs += 1
        p1 += 1
        p2 += 1
    elif aastu[p1] < aait[p2]:
        p1 += 1
    else:
        p2 += 1
        
print(pairs)

Note that if the second operation were free, we would need $$$\lceil \frac{\text{sum}}{2} \rceil$$$ operations to get rid of all the aliens. Indeed, when we kill one alien, we can kill a second alien for free with a second operation. But the second operation is not free. So we need to use the second operation as little as possible.

To do this, we need to apply ultimates (second attack) on the current largest horde by number of aliens, when the combo counter reaches the size of the largest horde. And we apply the first attack on the smallest hordes. This is so because the combo counter allows us to defeat $$$\lceil \frac{\text{sum}}{2} \rceil$$$ aliens. But since we can't apply this operation on several hordes at once, we need to keep the number of hordes on which we apply these attacks of the second type as small as possible. Then we can use the greedy algorithm described above. Formally, we need to keep a sorted array and store two pointers: pointer $$$i$$$ — to the smallest horde, $$$j$$$— to the largest horde. Until $$$i$$$ is equal to $$$j$$$: if after destroying all horde $$$i$$$ we can't kill horde $$$j$$$ with ultimates, we destroy horde $$$i$$$, increase pointer $$$i$$$ by $$$1$$$ and increase combo counter $$$x$$$ by $$$a[i]$$$. Otherwise, hit the horde $$$i$$$ so many times that the combo counter $$$x$$$ becomes $$$a[j]$$$. Then apply a second attack on horde $$$j$$$, reduce horde $$$j$$$'s counter by $$$1$$$, reduce $$$a[i]$$$, and nullify the combo counter. When $$$i$$$ becomes equal to $$$j$$$, you just need to apply the first attack the right number of times to finish with ultimates (or not if $$$a[i] =1$$$).

Total complexity $$$O(nlogn)$$$.

from math import ceil
t = int(input())
for _ in range(t):
    n = int(input())
    nums = sorted(map(int, input().split()))
    ans = 0
    cur = 0
    left = 0
    right = n - 1
    while left < right:
        cur += nums[left]
        if cur >= nums[right]:
            ans += nums[right] + 1
            cur -= nums[right]
            right -= 1
        left += 1
    if left == right:
        cur += nums[right]
    ans += (ceil(cur / 2) + 1) if cur > 1 else cur
    print(ans)

Calculate the minimum segment size so that a number can be found in all such segments. Do this for every number.

For two segment sizes $$$a$$$ and $$$b$$$ where $$$a < b$$$. If $$$u$$$ is the minimum number found in all segments with size $$$a$$$, and $$$v$$$ is the minimum number found in all segments with size $$$b$$$, then $$$v <= u$$$.

Let's fix some arbitrary number $$$x$$$ and calculate the minimum value of $$$k$$$ such that $$$x$$$ occurs in all segments of length $$$k$$$. Let $$$p_{1}<p_{2}<⋯<p_{m}$$$ be the indices of entries of $$$x$$$ in the array. Then, for each $$$1≤i<m$$$ it is clear that $$$k$$$ should be at least the value of $$$p_{i+1}−p_{i}$$$. Also, $$$k≥p_{1}$$$ and $$$k≥n−p_{m}+1$$$. The maximum of these values is the minimum segment size $$$k$$$ where $$$x$$$ can possibly be the minimum value in. We do this for every number, and then take the minimum of those numbers for a segment size.

Finally for a segment size $$$a > 1$$$, we take the minimum of the value already there or the minimum value we had for the previous size $$$a - 1$$$.

from collections import defaultdict


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


    last_indx = defaultdict(lambda :-1) # stores the last occurence of a given number
    max_dist = defaultdict(int) # stores maximum distance between instances of a given number
    ans = [float('inf')]*n

    # calculate the minimum size segment so that a number can be found in all such segments
    # and take the minimum of those numbers for the segment size
    for indx, num in enumerate(a):
        prev = last_indx[num]
        max_dist[num] = max(max_dist[num], indx - prev)
        
        min_segment_covered = max(max_dist[num], n - indx) - 1
        ans[min_segment_covered] = min(ans[min_segment_covered], num)
        last_indx[num] = indx
    
    # minimum number propagation to larger segment sizes
    for indx in range(1, n):
        ans[indx] = min(ans[indx], ans[indx - 1])
    
    # replace the inf's by -1
    for indx in range(n):
        if ans[indx] == float('inf'):
            ans[indx] = -1
    
    print(*ans)
        

To identify the unique element, this solution counts the occurrences of each number in the array. Then, it locates its index in the array.

from collections import Counter

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    count = Counter(nums)
    for key in count:
        if count[key] == 1:
            mynum = key
    for i in range(len(nums)):
        if nums[i] == mynum:
            print(i + 1)
            break

To solve the problem quickly, we can maintain two stacks: one for uppercase letters and one for lowercase letters. When deleting, we need to mark that the character at a specific position should be skipped. Alternatively, we can reverse the original string and skip characters instead of deleting them.

tc = int(input())
 
for _ in range(tc):
    word = input()
    res = []
    cap_pos = []
    sm_pos = []
    for i in word:
        if i == "B":
            if cap_pos:
                res[cap_pos.pop()] = ""
        elif i == 'b':
            if sm_pos:
                res[sm_pos.pop()] = ""
        else:
            if i.islower():
                sm_pos.append(len(res))
            else:
                cap_pos.append(len(res))
            res.append(i)
    print("".join(res[:-1]))

Initialize $$$(rows)$$$ and $$$(cols)$$$ dictionaries to track the frequency of each element in the matrix rowwise and columnwise.

For each element $$$a_{ij}$$$, update the counts of these elements in the corresponding $$$(rows)$$$ and $$$(cols)$$$ dictionaries for that row and column.

Check if the count of the current element in both the $$$(rows)$$$ dictionary of its row and the $$$(cols)$$$ dictionaries of its column is equal to $$$(1)$$$. If so, the element is considered unique and updates the $$$(result)$$$ list.

from collections import defaultdict
n, m = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(input()))

rows = [defaultdict(int) for i in range(n)]
cols = [defaultdict(int) for i in range(m)]
for i in range(n):
    for j in range(m):
        rows[i][grid[i][j]] += 1
        cols[j][grid[i][j]] += 1

result = []
for i in range(n):
    for j in range(m):
        if rows[i][grid[i][j]] == 1 and cols[j][grid[i][j]] == 1:
            result.append(grid[i][j])

print(''.join(result))

The equation $$$c_i = d \cdot a_i + b_i$$$ is given, and the objective is to maximize the number of zeros in the resulting array $$$c$$$. To achieve this goal, the strategy is to identify values of $$$d$$$ that satisfy the condition $$$0 = d \cdot a_i + b_i$$$, which leads to the expression $$$d = (-b_i) / a_i$$$.

The approach involves iterating through the elements in arrays $$$a_i$$$ and $$$b_i$$$ to track the frequency of occurrences of $$$((-b_i) / a_i)$$$ in a dictionary. To avoid potential inaccuracies stemming from floating-point precision problems when using decimal numbers as dictionary keys, the code represents these fractions in their simplest form. For instance, for values $$$a_i = 6$$$ and $$$b_i = 9$$$, simplification yields $$$(-9/6 => -3/2)$$$, and the simplified fraction $$$(-3, 2)$$$ is used as a key in the dictionary.

from collections import defaultdict
from fractions import Fraction

def main():
    n = int(input()) 
    a = list(map(int, input().split()))
    b = list(map(int, input().split())) 
    c = defaultdict(int) 
    d = 0   
    for i in range(n):
        if b[i] == 0 and a[i] == 0:
            d += 1
        elif a[i]:
            fraction = Fraction(-b[i], a[i])
            c[fraction] += 1
    
    d += max(c.values()) if c else 0
    print(d)

if __name__ == '__main__':
    main()

This problem can be solved using a dictionary to track the count of each number in the array. By iterating through the array and incrementing the count of each number in the dictionary, we calculate the current count (current_count) for each number. Additionally, we utilize another dictionary (appearance_dict) to monitor the total size of the numbers for each frequency count (calculated as frequency_count * frequency = the total size). This calculation allows us to understand the array's total size if the frequency is set as C.

After traversing through the array, we determine the maximum value in the appearance_dict dictionary. This value signifies the maximum size capable of accommodating numbers. The key retrieved from the dictionary indicates the maximum frequency for each unique number, necessary to make the array beautiful. Our goal is to ensure each number appears either zero or C times. Hence, we must eliminate all elements except those appearing C times. Consequently, the number of elements to remove equals the total number of elements minus the maximum value found in the appearance_dict dictionary.

from collections import defaultdict

test_cases = int(input())
for _ in range(test_cases):
    array_length = int(input())
    array = list(map(int, input().split()))

    count_dict = defaultdict(int)
    appearance_dict = defaultdict(int)

    for element in array:
        count_dict[element] += 1
        current_count = count_dict[element]
        appearance_dict[current_count] += current_count

    max_appearance = max(appearance_dict.values())

    print(array_length - max_appearance)

First identify the unique element by counting the occurrences of the numbers and then find it's index in the array.

from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int,input().split()))
    count = Counter(nums)
    for key in count:
        if count[key] == 1:
            mynum = key
    for i in range(len(nums)):
        if nums[i] == mynum:
            print(i + 1)
            break

For each element $$$a_{ij}$$$ , if it lies on the main diagonal $$$(i - j = 0)$$$, secondary diagonal $$$(i + j = n - 1)$$$, middle row $$$(i = n/2)$$$, or middle column $$$(j = n/2)$$$, it is added to the total sum; otherwise, it is skipped.

n = int(input())
a = [[*map(int, input().split())] for _ in range(n)]
total = 0
for i in range(n):
    for j in range(n):
        if i - j == 0 or i + j == n - 1 or i == n//2 or j == n//2:
            total += a[i][j]
print(total)

If there is no one between the $$$i$$$-th and $$$j$$$-th person then $$$max(a_i,a_j)$$$ free chairs should be between them.

If there is no one between the $$$i$$$-th and $$$j$$$-th person then $$$max(a_i,a_j)$$$ free chairs should be between them. So we should find a permutation $$$p$$$ of the array $$$a$$$, when $$$max(p_1,p_2)$$$ + $$$max(p_2,p_3)$$$ $$$+...$$$ + $$$max(p_{n-1},p_n)$$$ + $$$max(p_n,p_1)$$$ is minimal.

We can assume that the array is non-decreasing $$$(a_i ≤ a_i +1)$$$. So $$$max(p_1,p_2)$$$ + $$$max(p_2,p_3)$$$ $$$+...$$$ + $$$max(p_{n-1},p_n)$$$ + $$$max(p_n,p_1)$$$ will be minimal if the permutation of $$$p$$$ is sorted. $$$max(p_1,p_2)$$$ = $$$p_2$$$, $$$max(p_2,p_3)$$$=$$$p_3$$$, ... $$$max(p_{n−1},p_n)$$$=$$$p_n$$$, and $$$max(p_n,p_1)$$$=$$$p_n$$$.

They also sit on $$$n$$$ chairs. If we add all of these, we get that the answer is YES if: $$$n$$$+ $$$\sum_{i=1}^{n} (a_i)$$$ $$$-$$$ $$$min(a_i)$$$ + $$$max(a_i)$$$ $$$ ≤m $$$ . ( $$$a_i$$$ = {$$$a_1$$$,$$$a_2$$$,...$$$a_n$$$} )

t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    nums = list(map(int, input().split()))
    if max(nums) - min(nums) + sum(nums) + n > m:
        print("NO")
    else:
        print("YES")

For a string $$$a$$$ to be a substring of another string $$$b$$$, the length of $$$a$$$ should be less or equal to that of $$$b$$$.

Sort all the strings by their lengths. Then, for each $$$i ∈ [0...n−2]$$$ check that $$$s_{i}$$$ is a substring of $$$s_{i + 1}$$$. If it doesn't hold for some $$$i$$$ then the answer is "NO". Otherwise, the answer is "YES", and the sorted array is the correct order of the strings.

If there are several strings of the same length, their order does not matter, because if the answer is "YES", then all the strings of the same length should be equal.

n = int(input())
strings = []

for _ in range(n):
    strings.append(input())

strings.sort(key=len)

for indx in range(n - 1):
    if strings[indx] not in strings[indx + 1]:
        print('NO')
        exit()

print('YES')
for string in strings:
    print(string)

Since the words only contain five characters $$$(a, b, c, d, e)$$$, we can approach the problem by maximizing the story for each character individually.

How can we quantify a word's impact on the overall story?

For a given character in a word, the word's contribution is expressed as $$$x - ( len(word) - x)$$$, with $$$x$$$ denoting the character's occurrences and $$$(len(word) - x)$$$ representing the rest of the letters in the word.

1.Calculate Contributions: For each word and for each character from ‘a’ to ‘e’, calculate the word’s contribution towards that character.

2.Sort Contributions: For each character, sort the words based on their contributions towards that character. Words with higher contributions are sorted higher.

3.Select Words: For each character, select the words in the order of their sorted contributions until the sum of the contributions becomes non-positive. This gives us the maximum number of words that can make an interesting story with that character as the majority character.

4.Find the Maximum: Repeat the above steps for all characters and keep track of the maximum number of words found. This will be the maximum number of words that can make an interesting story.

t = int(input())
for _ in range(t):
    n = int(input())
    arr = []
    
    for i in range(n):
        arr.append(input())
        
    ans = 0
    
    #for each character(a,b,c,d,e)
    for j in range(5):
        char_count = []
        char = chr(ord('a') + j)
    
        for word in arr:
            char_count.append(2*(word.count(char)) - len(word))
        
        char_count.sort(reverse=True)
  
        if char_count[0] <= 0:
            continue
        
        total = char_count[0]
        i = 1
        while i < len(char_count) and total + char_count[i] > 0:
            total += char_count[i]
            i += 1
        
        ans = max(ans,i)
    print(ans)

First, let's check whether the given grid is good. If it is, we can swap the first column with itself and print $$$1 1$$$ as an answer. If it is not, there is a row that has elements that should be swapped.

Let's say this row is $$$a$$$, and let $$$b$$$ be the sorted version of $$$a$$$. After having these, let's find the set of indices $$$i$$$ where $$$a_{i} ≠ b_{i}$$$. If there are 3 or more such positions, the answer is $$$−1$$$, because by making a single swap we can only correct at most 2 of them.

But if there are no more than 2 such positions where $$$a_{i} ≠ b_{i}$$$, then let's swap the corresponding columns and check whether each row is sorted. If the grid is now good, we have found the answer. If not, the answer is $$$−1$$$ because we can not sort $$$a$$$ in any other way and get a good grid after that.

t = int(input())
for _ in range(t):
    
    grid = []
    n, m = map(int, input().split())
    
    for row in range(n):
        grid.append(list(map(int, input().split())))


    unsorted_row = None
    # check if every row is sorted
    for row in range(n):
        for col in range(1, m):
            if grid[row][col - 1] > grid[row][col]:
                unsorted_row = grid[row]
                break
        
        if unsorted_row != None:
            break
    
    # if all rows are already sorted we can swap the first column with itself as an answer
    if unsorted_row == None:
        print(1, 1)
        continue
    

    sorted_version = sorted(unsorted_row)
    disordered_columns = []
    can_be_good = True

    # identify the indices whose values are not in their sorted positions in the unsorted row
    for indx in range(m):
        if unsorted_row[indx] != sorted_version[indx]:
            disordered_columns.append(indx)

            if len(disordered_columns) >= 3:
                can_be_good = False
                break
        
    # if those indices are more than 3, we can't make it sorted with a single swap
    if not can_be_good:
        print(-1)
        continue

    # swap the corresponding columns of those indices
    for row in range(n):
        col1, col2 = disordered_columns
        grid[row][col1], grid[row][col2] = grid[row][col2], grid[row][col1]

    # check if all rows are sorted after the swap
    for row in range(n):
        for col in range(1, m):
            if grid[row][col - 1] > grid[row][col]:
                can_be_good = False
                break
        
        if not can_be_good:
            break
    
    if not can_be_good:
        print(-1)
    
    else:
        print(disordered_columns[0] + 1, disordered_columns[1] + 1)

for a sequence to be strictly increasing, no two elements can be equal. Therefore, if there are any duplicate elements in the array, it is impossible to rearrange the array to make it strictly increasing.

Use a set to keep track of unique elements while iterating through the array. If, at any point during the iteration, an element is found to already exist in the set, it means there is a duplicate, and the answer is "NO." If the iteration completes without finding any duplicates, the answer is "YES."

t = int(input())


for _ in range(t):
   
    nums = list(map(int,input().split()))
    seen = set()
    possible = True
    for i in nums:
        if i in seen:
            possible = False
        seen.add(i)
   
    if possible:
        print("YES")
    else:
        print("NO")
   
   

Consider using a hashmap to store the count of change requests made by a given username.

We can use a hashmap to store the usernames along with their change counts. It also makes it easier to check if a username exists in the database, and to access the count of changes made for a person.

If a person is not registered we store $$$0$$$ as a value for the username. Afterwards we increment this value if a change request is made again with this username.

n = int(input())
database = {}


for _ in range(n):
    username = input()

    if username in database:
        database[username] += 1
        print(username + str(database[username]))

    else:
        database[username] = 0
        print('OK')

Let's denote the position of the bishop as $$$(i, j)$$$. The cells that the bishop can attack lie along diagonals that either ascend from left to right or descend from right to left. In the case of the left-to-right diagonal, the sum of the column numbers for all cells $$$(i, j)$$$ on the same diagonal is constant $$$( i + j = c )$$$ for some constant $$$c$$$.

For the right-to-left diagonal, the difference of the coordinates remains constant $$$(i - j = c)$$$ for some constant $$$c$$$.

We can store the values of the left-to-right diagonal sums and right-to-left diagonal sums and later calculate the total sum for each cell based on these precomputed values.

from collections import defaultdict
T = int(input())

for _ in range(T):
   
    n,m = map(int,input().split())
    mat = [list(map(int,input().split())) for i in range(n)]
   
    front_diagonal = defaultdict(int)
    back_diagonal = defaultdict(int)

    for r, row in enumerate(mat):
        for c, val in enumerate(row):
            front_diagonal[r + c] += val
            back_diagonal[r - c] += val
   
    ans = 0

    for r in range(n):
        for c in range(m):
            cur_total =  front_diagonal[r + c] + back_diagonal[r - c] - mat[r][c]
            ans = max(ans,cur_total)
   
   print(ans)

	

Let's rotate the grid by 0∘, 90∘, 180∘, and 270∘, and mark all cells that map to each other under these rotations. For example, for 4×4 and 5×5 grids, the grid must have the following patterns, the same letters denoting equal values:

In general, we can rotate the grid by 0∘, 90∘, 180∘, and 270∘ and see which cells need to have equal values by seeing the positions which each cell maps to.

Now to solve the problem, we consider each equal value (each of the letters a, b, c, ... in the above figures) independently, and consider the minimum number of moves to make them all 0 or all 1. The answer is the total across all values.

The time complexity is O($$$ n^2 $$$). And the space complexity is O($$$ 1 $$$).

Let's consider the upper triangular quarter of the grid. If we are at $$$(i, j)$$$, after rotating it by 0∘, 90∘, 180∘, and 270∘, the bit at this position is replaced by the one at $$$(j, n - i - 1)$$$, $$$(n - i - 1, n - j - 1)$$$, $$$(n - j - 1, i)$$$ respectively. From these four positions we count the numbers of zeros and ones and take the minimum. We sum those minimums for all positions in the upper triangular quarter of the grid.

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

    n = int(input())
    
    grid = []
    for i in range(n):
        grid.append(input())
    

    min_ops = 0

    for row in range(n//2):
        for col in range(row, n - row - 1):
            
            zero_one_count = [0, 0]

            zero_one_count[int(grid[row][col])] += 1
            zero_one_count[int(grid[col][n - row - 1])] += 1
            zero_one_count[int(grid[n - row - 1][n - col - 1])] += 1
            zero_one_count[int(grid[n - col - 1][row])] += 1

            min_ops += min(zero_one_count)

    print(min_ops)

It doesn't matter if we start from S or T. How many cases are there?

Mark all the points where you can go horizontally/vertically without any turn starting from both S and T.

Basically, there are three cases: 1. When there is no turn. 2. When the first turn is vertical. 3. When the first turn is horizontal.

We can mark all the horizontal dots that we can reach with out any turn starting from both S and T. If we get S or T while we are marking, it means case 1 (we can reach with no turn). If not, we will check if there are vertically consecutive dots that connect two marked cells (including S and T). If we found one it means case 2. We can check case 3 by transposing the matrix and doing the same technique. If we can't find any of the three cases it means we can't reach there with at most two turns.

rows, cols = map(int, input().split())

grid = []
for _ in range(rows):
    row = list(input())
    grid.append(row)

def solve(grid, rows, cols):
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] in "TS":
                # mark the left until we get '*', 'T' or 'S', or we reach the end
                i = c - 1
                while i >= 0 and grid[r][i] == ".":
                    grid[r][i] = 'M'
                    i -= 1
                if i >= 0 and grid[r][i] in "TS": # Case 1: check if we can reach with no turn
                    return True
                
                # mark the right until we get '*', 'T' or 'S', or we reach the end
                i = c + 1
                while i < cols and grid[r][i] == ".":
                    grid[r][i] = 'M'
                    i += 1
                if i < cols and grid[r][i] in "TS": # Case 1: check if we can reach with no turn
                    return True

    for c in range(cols):
        r = 0
        while r < rows:
            if grid[r][c] in "TSM":
                r += 1
                while r < rows and grid[r][c] == ".":
                    r += 1
                if r < rows and grid[r][c] in "TSM":
                    return True
            r += 1
    return False


# transpose the grid for the second case 
transposed_grid = [[""]*rows for _ in range(cols)]
for r in range(rows):
    for c in range(cols):
        transposed_grid[c][r] = grid[r][c]

# Case 2: Vertical turn
is_found = solve(grid, rows, cols)
if is_found:
    print("YES")
    exit()

# Case 3: Horizontal turn
if solve(transposed_grid, cols, rows):
    print("YES")
else:
    print("NO")

Count how many of b, c, d are greater than a.

If b > a, we count 1. If c > a we add 1, and the same for d.

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

    a, b, c, d = map(int, input().split())
    infront = (b > a) + (c > a) + (d > a)
    print(infront)

Think of the order of characters in 'Yes'.

Order of characters: 'e' should follow 'Y', 's' should follow 'e', and 'Y' should follow 's'. For every character other than the first one, we check if it is found in 'Yes' and check if the current character can follow the previous one. Handle the first character with an if condition.

t = int(input())
next_char = {
            'Y': 'e',
            'e': 's',
            's':'Y'
            }

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

    if s[0] not in next_char:
        print('NO')
        continue

    yes = True
    for index in range(1, len(s)):
        prev = s[index - 1]
        cur = s[index]

        if cur not in next_char or next_char[prev] != cur:
            yes = False
            break

    print('YES' if yes else 'NO')
    

if any appropriate substring exists, an appropriate substring of length 2 also exists.

Why does the problem ask us only to check if we can do less than n operations instead of just asking the minimum amount? That must be making the problem easier, so let's focus our attention on that.

What if it was ≤n instead of <n ? Well, then the problem would be trivial. You can type the word letter by letter and be done in n operations. So we only have to save one operation. In order to save at least one operation, we have to use the copy operation and copy more than one character in that.

Let's think further. Imagine we found a substring that works. Let it have length k . Notice how you can remove its last character, obtaining a substring of length k−1 , and it will still occur in the same set of positions (possibly, even more occurrences will be found). Remove characters until the substring has length 2 . Thus, if any appropriate substring exists, an appropriate substring of length 2 also exists.

Finally, we can check if there exists a substring of length 2 that appears at least twice in the string so that the occurrences are at least 2 apart. That can be done with a set or a dictionary. Some implementations might require careful handling of the substrings of kind "aa", "bb" and similar.

from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    set_ = set()
    flag = False
    for i in range(2, n - 1):
        set_.add(s[i - 2:i])
        if s[i:i+2] in set_:
            flag = True
            break
    print("YES" if flag else "NO")

Consider The cases where n is even and odd

Let's assume that 1 to 2n is paired and each sum of pair is k,k+1,⋯,k+n−1 . Sum from 1 to 2n should equal to the sum of k to k+n−1 . So we obtain n(2n+1)=(2k+n−1)n/2 , which leads to 4n+2=2k+n−1 . Since 4n+2 is even, 2k+n−1 should be even. So if n is even, we cannot find such pairing.

If n is odd, there are various ways to make such pairing. Let's see one of them, If all the sums of the pairs are consecutive, it is possible to find the middle element by dividing the total sum of the pairs by n. From that, we can determine all the sums of the pairs, such as k, k+1, k+2, ..., k+n-1. We can then separate the sums into odd and even categories. For example, let the first sum (k) be even; we can start with 1 and k-1. By incrementing both numbers by 1, we can find the next even number. So, the first odd pair sum is k + 1. We can use the numbers (ceil(n/2) + 1) and (k + 1 — ceil(n/2) + 1) to obtain k + 1. By continuing to add 1 to both numbers, we can generate the next odd number.

from math import ceil
t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        print("NO")
    else:
        print("YES")
        total = 2 * n
        total_sum = total* (total + 1) // 2
        middle_element = total_sum // n
        starting_number_one = middle_element - n // 2 - 1
        starting_number_two = middle_element - n // 2 + 1 - (ceil(n / 2) + 1)
        i = 1
        for _ in range(ceil(n / 2)):
            print(i, starting_number_one)
            i += 1
            starting_number_one += 1
        for _ in range(n // 2):
            print(i, starting_number_two)
            i += 1
            starting_number_two += 1

Consider when there is $$$0, 1,$$$ and more than $$$1$$$ occurrence of "$$$abacaba$$$" in string $$$s$$$.

Once we have exactly one occurrence of "$$$abacaba$$$" in $$$s$$$, we can replace all remaining '$$$?$$$' with a character that does not exist in "$$$abacaba$$$".

At first, we will count the occurrences of "$$$abacaba$$$" within the given string $$$s$$$. If the count is exactly one, it means there is a unique occurrence of "$$$abacaba$$$" in $$$s$$$. We can then replace all the '$$$?$$$' characters with a small letter character that doesn't exist in "$$$abacaba$$$" so that our final string still contains a unique occurrence of "$$$abacaba$$$$.

If the count is zero for every $$$i$$$ such that $$$1 <= i <= n − 6$$$, we can choose a substring $$$s[i:i+7]$$$ and attempt to convert it into the string "$$$abacaba$$$". If that is possible, we will then replace the remaining '$$$?$$$' characters with a character that doesn't exist in "$$$abacaba$$$" and check the final string to ensure there is only one occurrence of "$$$abacaba$$$".

If the count is more than one, it implies there are multiple occurrences of "$$$abacaba$$$" in $$$s$$$. In this case, replacing question marks to achieve a unique occurrence is impossible.

def count_sub_str(s,v):
    ans = 0
    for i in range(len(s)-6):
        if s[i:i+7] == v: ans += 1
    return ans
 
def solve():
    n = int(input())
    s = input()
    sub_str = "abacaba"

    if count_sub_str(s,sub_str) == 1:
        s = s.replace('?','x')
        print("YES")
        print(s)
        return
   
    for i in range(n-6):
        cur = list(s)

        for x in range(i,i+7):
            if cur[x] == '?':
                cur[x] = sub_str[x - i]

        cur = "".join(cur)
        if count_sub_str(cur,sub_str) == 1:
            cur = cur.replace('?','x')
            print("YES")
            print(cur)
            return
       
    print("NO")
 
T = int(input())
for _ in range(T):
    solve()
	

Given that the length of the provided string is 10, the approach involves iterating through the string and comparing each character at position i with the corresponding character at position i in "codeforces."

t = int(input())
c = "codeforces"
for _ in range(t):
    s = input()
    res = 0
    for i in range(10):
        if s[i] != c[i]:
             res += 1
    print(res)	

Consider the first character in each pair.

Take every other character starting from the first one. Since the last character can not be a starting letter for a pair, add it to 'a' last.

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


    a = [] # Storing the characters in a list and appending gives a better time complexity compared to string concatenation
    for index in range(0, len(b), 2):
        a.append(b[index])
   
    a.append(b[-1])
    a = "".join(a)
    print(a)

Any palindrome subsequence with length ≥ 3 also contains a palindrome with length = 3 as its subsequence.

The first observation is that we can always try to find the palindrome of length 3 (otherwise, we can remove some numbers from the middle until its length becomes 3).

The second observation is that the palindrome of length 3 is two equal numbers and some other (maybe, the same) number between them. For each number, we only need to consider its left and right occurrences (if there is any number between them).

t = int(input())

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

    left_occurrence = {}
    found = False
    
    for i, n in enumerate(nums):
        if n in left_occurrence:
            if i - left_occurrence[n] >= 2:
                found = True
                break                
        else:
            left_occurrence[n] = i
    
    if found:
        print("YES")
    else:
        print("NO")

Can you rewrite the formula?

The equation $$$a_j - a_i = j - i$$$ can be transformed into $$$a_j - j = a_i - i$$$, and let $$$b_i = a_i - i$$$. Then we need to count the number of pairs $$$(i, j)$$$ where $$$b_i = b_j$$$. We can use a dictionary(hash map) to count occurrences of each difference $$$(b_i)$$$.

T = int(input())
for _ in range(T):
    N = int(input())
    a = list(map(int,input().split()))
    difference_count = {}
    pair_count = 0  

    for i in range(N):
        difference = a[i] - i
        pair_count += difference_count.get(difference, 0)
        difference_count[difference] = difference_count.get(difference, 0) + 1
    print(pair_count)

What does it mean for an array $$$a_1, a_2, \ldots, a_n$$$ to be sorted? It means $$$a_1 \leq a_2$$$ and $$$a_2 \leq a_3$$$, and so on. For each pair of adjacent elements, let's deduce which values of $$$x$$$ put them in the correct order. Any value of $$$x$$$ that satisfies all pairs will be the answer.

Consider any $$$a_i$$$ and $$$a_{i+1}$$$ and solve the inequality $$$|a_i - x| \leq |a_{i+1} - x|$$$. If $$$a_i = a_{i+1}$$$, then any value of $$$x$$$ works. Let $$$a_i$$$ be smaller than $$$a_{i+1}$$$. If $$$x$$$ is smaller than or equal to $$$a_i$$$, then the inequality becomes $$$a_i - x \leq a_{i+1} - x$$$ implies $$$a_i \leq a_{i+1}$$$. Thus, they don't change their order, and any $$$x \leq a_i$$$ works.

If $$$a_i > a_{i+1}$$$ and we want to change their order, $$$x$$$ should be $$$\geq \lceil \frac{a_i + a_{i+1}}{2} \rceil$$$. For this pair, we want $$$x$$$ to be the minimum, which is $$$\lceil \frac{a_i + a_{i+1}}{2} \rceil$$$. This number doesn't have to change the pairs that are already in the correct order. For all pairs $$$i$$$ and $$$i+1$$$ where $$$a_i > a_{i+1}$$$, to satisfy all pairs, we have to take the maximum. To check if that maximum number satisfies all the conditions, we can construct the array using this number and check if it's non-decreasing. If it is, then it's valid; otherwise, return -1.

from math import ceil
t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    maximum = 0
    for i in range(n - 1):
        if nums[i] > nums[i + 1]:
            maximum = max(maximum, ceil((nums[i] + nums[i + 1]) / 2))    
    for i, num in enumerate(nums):
        nums[i] = abs(num - maximum)
    flag = True
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            flag = False
            break
    if flag:
        print(maximum)
    else:
        print(-1)

For every character given check if that character appears inside "codeforces".

t = int(input())
for _ in range(t):
    char = input()
    if char in "codeforces":
	print("YES")
    else:
	print("NO")

Get the numbers a, b, and c from the console. If the result of subtracting b from a is equal to c, output '-'; otherwise, output '+'.

t = int(input())
for _ in range(t):
    a, b, c = list(map(int, input().split()))
    if a - b == c:
        print("-")
    else:
        print("+")

For a given word if the length is less than or equal to 10 print the word back, else print "firstletter + length of the word minus 2 + lastword".

t = int(input())
for _ in range(t):
    word = input()
    if len(word) > 10:
        print(word[0] + str(len(word) - 2) + word[-1])
    else:
        print(word)

We have to remove at most one number.

First, if the sum of all the numbers is already even, then we do nothing. Otherwise, we remove the smallest odd number. Since, if the sum is odd, we need to remove a number with the same parity to make the sum even. Notice it's always bad to remove more odd numbers, and it does nothing to remove even numbers.

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

total = sum(nums)

if total%2 == 0:
    print(total)
else:
    min_odd = float('inf')
    for num in nums:
        if num%2 == 1 and num < min_odd:
            min_odd = num
    print(total - min_odd)

Consider when there is "??".

In how many ways can we paint "C?C"?

Consider when there is "?" at the end or beginning.

What causes the answer to be "Yes"? Of course, there cannot be adjacent segments that already have the same colour; but what else? We can figure out that whenever two consecutive question marks appear, there are at least two ways to fill them. But the samples lead us to ponder over cases with one single question mark: a question mark can be coloured in two different colours if it lies on the boundary of the canvas, or is between two adjacent segments of the same colour. Putting it all together, we get a simple but correct solution.

N = int(input())

s = input()

if ("CC" in s) or ("YY" in s) or ("MM" in s):
    print("No")
elif ("??" in s) or ("C?C" in s) or ("Y?Y" in s) or ("M?M" in s) or (s[0] == "?") or (s[-1] == "?"):
    print("Yes")
else:
    print("No")