Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.

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

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


for _ in range(int(input())):
    n, h = map(int, input().split())
   
    rope = 0
    for i in range(n):
        l, w = map(int, input().split())
        rope += max(l, w)
   
    if rope >= h:
        print('YES')
    else:
        print('NO')

Output binary search.

The key insight is that if we have a wagon size greater than or equal to $$$\max(d_1, d_2, \dots, d_n)$$$, we only need to go once for every village. Hence, the sum of all $$$a_i$$$ is the minimum achievable time to deliver the water with any size.

If $$$\sum_{i=1}^{n} a_i$$$ is already greater than $$$k$$$, we can't make Empress Taytu happy with any size. If not, starting from 1 (left) up to $$$\max(d_1, d_2, \dots, d_n)$$$ (right), we can perform a binary search by checking whether it's achievable with a given size within $$$k$$$ hours.

For a single village, we can calculate the number of trips the wagon has to make by ceil dividing its demand by the wagon size. Then, we can calculate the total time needed for one village by multiplying the number of trips with the time it takes for one trip ($$$a_i$$$). After adding the total time for all villages, we will check if it is less than or equal to $$$k$$$. Overall, the complexity of the checker is $$$O(n)$$$.

The complexity of the binary search algorithm used in this solution is $$$O(\log(\max(d_1, d_2, \dots, d_n)))$$$. Since we need to check for each possible size of the wagon, the overall complexity of the algorithm is $$$O(n \log m)$$$, where $$$m = \max(d_1, d_2, \dots, d_n)$$$.

• Space Complexity: $$$O(1)$$$

from math import ceil
from sys import stdin


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

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

    if sum(a) > K:
        print(-1)
        continue

    def checker(size):
        time = 0
        for i in range(N):
            time += ceil(d[i]/size)*a[i]
        return time <= K
    
    left = 1
    right = max(d)
    while left <= right:
        mid = left + (right - left)//2
        if checker(mid):
            right = mid - 1
        else:
            left = mid + 1
    print(left)

Observation: After an increment operation, there is always a corresponding decrement operation.

Let's represent the characters with numerical values, such as their ASCII values. During an increment operation, the ASCII value of that character increases by $$$1$$$, and during a decrement operation, it decreases by $$$1$$$. Importantly, after an increment operation, the total sum of ASCII values of the word decreases by $$$1$$$, and after a decrement operation, the total sum increases by $$$1$$$. However, since one operation combines both increment and decrement, the total ASCII sum remains unchanged.

Therefore, to decrypt the message, we only need to check if there exists a substring with a size equal to the size of the sensitive word (let's denote it as $$$m$$$) and the sum of ASCII values of its characters is equal to that of the sensitive word. For this, we can employ a fixed-size sliding window approach with size $$$m$$$.

• Time Complexity: $$$O(n)$$$ where $$$n$$$ is the size of the decrypted message.
• Space Complexity: $$$O(1)$$$

from sys import stdin


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

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

    target = 0
    window_sum = 0
    for i in range(M):
        target += ord(w[i])
        window_sum += ord(s[i])
    
    found = False
    for i in range(M, N):
        if window_sum == target:
            found = True
            break
        window_sum += ord(s[i])
        window_sum -= ord(s[i - M])
    
    if window_sum == target or found:
        print("YES")
    else:
        print("NO")

In the first round, each group consists of two teams. Then, in the second round, every two consecutive groups are merged, and so on. This problem resembles a typical divide and conquer approach. Now, the question is, given the left group and the right group, how can we merge them and calculate the number of wins for every team efficiently?

One possible solution is to perform a binary search on the right team for each team in the left group, determining the number of players with strength strictly less than the current player's strength. Repeat this process for all players in the right group. Then, combine the two arrays using two pointers. The time complexity for this solution is $$$O(2^n * log^2(2^n))$$$, where $$$2^n$$$ is the size of the array.

Another approach is to use two pointers to calculate the wins. After calculating and updating both arrays, we can merge them together. This approach has a time complexity of $$$O(2^n*log(2^n)))$$$.

• Space Complexity: $$$O(2^n)$$$

def mergeSort(arr,l,r):
    if l == r:
   	 return
    
    # get the mid point of the current array and merge sort it
    mid = (l + r)//2
    mergeSort(arr,l,mid)
    mergeSort(arr,mid + 1, r)
    # merge the two halves after sorting them and calculating the answer
    merge(arr,l,mid,r)
 
def merge(arr,l,mid, r):
    # wins array to hold the number of wins each team have
 
    wins = [0]*(r - l + 1)
    # array to hold merged list
    merged = []
    
    # calculate the wins for the first group
    ptr = mid + 1
 
    # for every element of the first group
    for i in range(l,mid + 1):
   	 # move the second groups point to an element which is greater or equal to it
  	 
   	 while ptr <= r and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
 
   	 # the total numbe of wins for the current element
   	 #is the nubmer of element in the second group
   	 #that is lower than it
   	 wins[i - l] = ptr - (mid + 1)
 
    # same thing for the second group
    ptr = l
    for i in range(mid + 1,r+1):
   	 while ptr <= mid and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
   	 wins[i - l] = ptr - l
 
    # merge the two groups based on the new value
    pt1 = l
    pt2 = mid + 1
 
    while pt1 <= mid or pt2 <= r:
   	 if (pt2 > r) or (pt1 <= mid and arr[pt1][1] + wins[pt1 - l] < arr[pt2][1] + wins[pt2 - l]):
   		 arr[pt1][1] += wins[pt1 - l]
   		 merged.append(arr[pt1])
   		 pt1 += 1
   	 else:
   		 arr[pt2][1] += wins[pt2 - l]
   		 merged.append(arr[pt2])
   		 pt2 += 1
 
    arr[l:r + 1] = merged
 
 
 
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [[i,j] for i,j in enumerate(arr)]
    mergeSort(arr,0,2**n - 1)
    ans = [i[1] for i in sorted(arr,key = lambda x: x[0])]
    
    print(*ans)
 
t = int(input())
for _ in range(t):
    solve()

Find the time each gun explodes then you can take the maximum one.

Use monotonic stack to track the damage a gun receives for a gun behind him.

To determine the time it takes for each gun to explode, we can employ a monotonic stack approach. Starting from the first gun, which we know for sure will explode at infinity, we can represent each gun as a tuple $$$(t_i, p_i)$$$, where $$$t_i$$$ is the life of the $$$i$$$-th gun and $$$p_i$$$ is its power. These tuples are then pushed onto the stack.

For each gun $$$i$$$, we can understand that it receives a hit from the last gun on the stack. The damage it receives can be calculated as stack[-1][-1] * (stack[-1][0] - d), where stack[-1][0] and stack[-1][-1] represent the life and power of the gun at the end of the stack, respectively. Here, $$$d$$$ represents the duration of gun $$$i$$$ before it encounters the gun at the end of the stack. If the gun at the end of the stack cannot reduce the health of gun $$$i$$$ to zero, we decrement the received damage with the gun's health and pop from the stack.

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

import sys
from math import ceil, inf
input = lambda : sys.stdin.readline().strip()


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


    stack = [(inf, power[0])]
    ans = 0
    for i in range(1, n):
        duration = 0
        while health[i] - (stack[-1][0] - duration)*stack[-1][-1] > 0:
            t, p = stack.pop()


            health[i] -= (t-duration)*p
            duration += (t-duration)
       
        duration += ceil(health[i]/stack[-1][-1])
        stack.append((duration, power[i]))
        ans = max(ans, duration)
   
    print(ans)

Topic: Greedy

What is the maximum number of points for the $$$(k + 1)$$$-th team?

If $$$k$$$ equals $$$n$$$ (the last position), the answer is $$$0$$$ since $$$0$$$ points are needed to secure the last position.

Let's calculate for other positions:

Firstly, let's determine the maximum number of points the $$$(k + 1)$$$-th team can have. To maximize this, the first $$$(k + 1)$$$ teams will win all matches against the remaining $$$n - (k + 1)$$$ teams, resulting in the first $$$(k + 1)$$$ teams having points equal to $$$(n - (k + 1)) \cdot 3$$$.

Now, our task is to maximize the points of both the $$$k$$$-th and $$$(k + 1)$$$-th teams. To achieve this, we focus on the remaining matches involving the $$$k$$$ teams (excluding the $$$(k + 1)$$$-th team). Since we aim to maximize the minimum points within these $$$k$$$ teams, we need to maximize the minimum points in the remaining matches.

For $$$k = 2$$$, there is only $$$k - 1 = 1$$$ match remaining for a team. If a team wins, the other team will have $$$0$$$ points, resulting in a minimum of $$$0$$$ points. However, to maximize the minimum points, it's better if the match ends in a draw, resulting in a minimum of $$$1$$$ point. For $$$k = 3$$$, there are $$$k - 1 = 2$$$ matches remaining for a team. If a team wins one and loses one, all teams will have $$$3$$$ points, resulting in a minimum of $$$3$$$ points. However, if one team wins both matches, the minimum points will be $$$0$$$ or $$$1$$$.

We observe that if a match ends in a win or a loss, the overall points are $$$3$$$, whereas if it is a draw, it is $$$2$$$ (with $$$1$$$ point for each team). We aim to avoid losing points in a draw. The issue arises when there is only one match remaining and it's either a win or a loss, resulting in a minimum of $$$0$$$ points. However, with a draw, the minimum is $$$1$$$ point. For two matches, we can achieve an overall of $$$6$$$ points with wins, distributing $$$3$$$ points to each team.

Hence, to maximize the minimum points within the $$$k$$$ teams, we have $$$(k - 1)$$$ matches for each team. If $$$(k - 1)$$$ is even, the team wins $$$\frac{k - 1}{2}$$$ matches and loses $$$\frac{k - 1}{2}$$$ matches. If $$$(k - 1)$$$ is odd, the team wins $$$\frac{k - 2}{2}$$$ matches, loses $$$\frac{k - 2}{2}$$$ matches, and draws $$$1$$$ match. Generally (for even or odd), the points it can obtain is $$$\left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$.

Now, both the $$$k$$$-th and $$$(k + 1)$$$-th teams have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$ points. The only match remaining is between them. We can secure the $$$k$$$-th team in the $$$k$$$-th position by ensuring it wins the match against the $$$(k + 1)$$$-th team. However, if both teams have the same number of points, they will both secure the $$$k$$$-th position. Therefore, to minimize the points required to guarantee the $$$k$$$-th position, the match should end in a draw. Finally, the $$$k$$$-th team will have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2 + 1$$$ point.

• Time Complexity: $$$O(1)$$$
• Space Complexity: $$$O(1)$$$

from sys import stdin


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

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

    if N == K:
        print(0)
        continue

    ans = (N - (K + 1))*3 + ((K - 1)//2)*3 + (K - 1)%2 + 1
    print(ans)

Scan the digits from left to right. Insert the new digit before the first digit smaller than it because placing it before a smaller digit maximizes the overall value by ensuring that the new digit occupies a higher significant position in the resulting number. This positioning ensures that the number formed is as large as possible. If no smaller digit is found, append the new digit at the end.

for i in range(int(input())):
    n, d = list(map(int, input().split()))
    s = input()
 
    flag = True
    for i in range(len(s)):
        if int(s[i]) < d:
            print(s[:i] + str(d) + s[i:])
            flag = False
            break
    
    if flag:
        print(s + str(d))

We can precalculate a prefix sum array $$$sum$$$ over the piles. I.e. $$$sum_{i} = a_{1} + a_{2} + ... + a_{i}$$$. We can now perform a binary search for each query $$$q_{i}$$$ to find the result $$$j$$$ with the properties $$$sum_{j - 1} < q_{i}$$$ and $$$sum_{j} ≥ q_{i}$$$.

Time complexity $$$O(n + m·log(n))$$$

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


prefix_sum = [0]
for pile in a:
    prefix_sum.append(prefix_sum[-1] + pile)


for label in q:
    low = 0
    high = n

    while low <= high:
        mid = low + (high - low)//2
        if prefix_sum[mid] < label:
            low = mid + 1
        
        else:
            high = mid - 1
    
    print(low)

We are given $$$s$$$ spaceships, each with an attacking power $$$a_i$$$, and $$$b$$$ bases, each with a defensive power $$$d_j$$$ and gold $$$g_j$$$.

We are asked to output for each spaceship, the sum of the gold of the bases it can attack, that is: $$$res(i) = \sum g_j, ∀_j : a_i ≥ d_j$$$

An $$$O(sb)$$$ solution would not pass the time limit. Instead the intended solution is to sort the bases by their defensive power, and the ships by their attacking power, in increasing order. Then, we can use the fact that if a weaker ship can attack a base, so can a stronger ship. This way we only have to iterate once over all the bases. The overall complexity reduces to $$$O((s) log (s) + (b) log (b))$$$.

Another solution of that would pass the time limit would be to sort the bases in increasing order of their defensive strength. Then, compute the prefix sum of the gold (that is, $$$prefix[j]$$$ would hold the sum of gold of all the bases from $$$0...j$$$). Finally, for each ship, perform a binary search over the prefix sum and the bases arrays to compute how much gold it could steal.

Overall complexity: $$$O((s) log (b) + (b) log (b))$$$.

from bisect import bisect_right
from sys import stdin


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


S, B = map(int, input().split())
a = list(map(int, input().split()))
dg = []
for _ in range(B):
    d, g = map(int, input().split())
    dg.append((d, g))

dg.sort()
pref_sum = [0]
cur_sum = 0
ds = []
for d, g in dg:
    ds.append(d)
    cur_sum += g
    pref_sum.append(cur_sum)

ans = []
for ai in a:
    idx = bisect_right(ds, ai)
    ans.append(pref_sum[idx])
print(*ans)

Since we are sure that if $$$x$$$ can be the answer to the problem, then every value below $$$x$$$ can be the answer, So we can use binary search on the answer to solve the problem.

To check whether some value $$$x$$$ can be a valid solution, we have to sum all our gains that come from values greater than $$$x$$$. We can calculate the gain for one value by taking its difference with $$$x$$$. Let's say its difference is $$$diff$$$. Our gain will be $$$diff - (diff * k / 100)$$$. We can do the same for all values greater than $$$x$$$ and add the results; that will be our total gain. We also need to calculate the total need. We can do that for values less than $$$x$$$ by taking their difference with $$$x$$$ and adding those values. Then, we can compare if our total gain is greater than or equal to our total need. In that case, it can be considered valid.

import sys
n, k = map(int, sys.stdin.readline().strip().split())
nums = list(map(int, sys.stdin.readline().strip().split()))

def chekcker(x):
    gain = 0
    need = 0
    for num in nums:
        if num > x:
            diff = num - x
            gain += (diff - diff * k / 100)
        if num < x:
            need  += (x - num)
    
    return gain >= need

low = min(nums)
high = max(nums)
while high  - low > 10 ** -7:
    mid = (high + low) / 2
    if chekcker(mid):
        low = mid
    else:
        high = mid
print(high)

We can Break two sections of the wall in three different ways.

1. Break two sections with more than one section between them.i.e., $$$(i, j), i + 2 < j$$$.

2. Break two sections with only one section between them, i.e., $$$(i, i+ 2)$$$.

3. Break two sections with no section between them, i.e., $$$(i, i + 1)$$$.

We can Break two sections of the wall in three different ways.

1. Break two sections with more than one section between them.i.e., $$$(i, j), i + 2 < j$$$.

2. Break two sections with only one section between them, i.e., $$$(i, i+ 2)$$$.

3. Break two sections with no section between them, i.e., $$$(i, i + 1)$$$.

If there is more than one section between the two we want to break, then any shot hits only one of these sections, so each shot should be aimed at one of those sections, and we break them independently. Since one doesn’t affect the other, we could just pick the two minimum and try to break them independently, let's say their strength is $$$a_i$$$ and $$$a_j$$$, the total is going to be $$$\lceil\frac{a_i}{2}\rceil + \lceil\frac{a_j}{2}\rceil$$$.

If there is only one section between them, if we shoot at the section between them, we deal 1 damage to both sections; if we shoot at one of those sections, we deal 2 damage to it and 0 damage to the other section. So, each shot distributes 2 damage between these two sections the way we want to distribute it, and the number of shots required to break these two sections is $$$\lceil\frac{a_i + a_{i+2}}{2}\rceil$$$.

The case when we try to break two adjacent sections is the trickiest one. Let's say that these sections are $$$i$$$ and $$$i+1$$$, $$$x=\max(a_i, a_{i+1})$$$, and $$$y=\min(a_i, a_{i+1})$$$. If we target one of these sections, we deal 2 damage to it and 1 damage to the other section. Let's try to run the following algorithm: shoot at the section with higher durability until both of them break. It can be slow, but we can see that after the first $$$x-y$$$ shots, the durabilities of the sections become equal, and each pair of shots after that deals 3 damage to both sections. So, we can model the first $$$x-y$$$ shots, subtract $$$2(x-y)$$$ from $$$x$$$ and $$$(x-y)$$$ from $$$y$$$, and then we'll need $$$\lceil\frac{x+y}{3}\rceil$$$ shots. The only case when this doesn't work is if we break both sections before we equalize their durabilities; it means that $$$2y \leq x$$$, and we need to do only $$$\lceil\frac{x}{2}\rceil$$$ shots.

from math import ceil
def check(a, mid):
	n = len(a)
	local_min = a[0]

	for i in range(1, n - 1):
    	   x = max(a[i], a[i - 1])
    	   y = min(a[i], a[i - 1])

    	   # case one using the two min values
    	   if (ceil(local_min / 2) + ceil(a[i] / 2)) <= mid:
        	return True

    	   # case two using i, i + 2
    	   elif (ceil((a[i - 1] + a[i + 1]) / 2)) <= mid:
        	return True

    	   # case 3 using i, i + 1
    	   elif max(ceil(x / 2), ceil((x + y) / 3)) <= mid:
        	return True

    	   # update local min
    	   local_min = min(local_min, a[i])

	return False


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	low, high, ans = 1, max(a), float('inf')
	a.append(1e7)
	while low <= high:
    	   mid = low + (high - low) // 2
    	   if check(a, mid):
        	ans = min(ans, mid)
        	high = mid - 1
    	   else:
        	low = mid + 1

	print(ans)


if __name__ == "__main__":
	solve()

To solve this problem you need to understand that friends must meet in the middle point of the given points, so friends who live in the leftmost and in the rightmost points must go to the middle point. Because of that the answer equals to $$$max(x_1, x_2, x_3) - min(x_1, x_2, x_3)$$$.

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

import sys
a,b, c = map(int, sys.stdin.readline().strip().split())
print(max(a,b,c) - min(a, b, c))

Idea is a simple greedy, buy needed meat for i - th day when it's cheapest among days 1, 2, ..., n..

import sys
n = int(sys.stdin.readline().strip())
mi  =  float("inf")
ans= 0
for _ in range(n):
    a, b  = map(int, sys.stdin.readline().strip().split())
    mi = min(mi, b)
    ans += (a*mi)
print(ans)

Since $$$1≤a_i≤10^3$$$ for all $$$i$$$, let set $$$a_0=0$$$ and $$$a_n+1=1001$$$. For every $$$i$$$,$$$j$$$ such that $$$0≤i<j≤n+1$$$, if $$$a_j−j=a_i−i$$$ then we can erase all the elements between $$$i$$$ and $$$j$$$ (not inclusive). \

import sys
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
nums = [0] + nums + [1001]
ans = 0
left = 0
for  i in range(1, n + 2):
    if nums[i] - nums[i - 1]> 1:
        left = i
    ans = max(ans, i - left - 1)
print(ans)

The first observation is that the new Hamming distance may not be less than the old one minus two, since we change only two characters. So the task is to actually determine, if we can attain decrease by two, one or can’t attain decrease at all.

The decrease by two is possible if there are two positions with the same two letters in two strings but that appear in different order (like “double” <-> “bundle”).

If there are no such positions, then we just need to check that we may decrease the distance. This can be done by just “fixing” the character that stands on the wrong position, like in “permanent” <-> “pergament” (here n stands in wrong pair with m, and there is also unmatched m, so we may fix this position).

Otherwise, the answer is to keep everything as it is. Implementation can be done by keeping for each pair (x, y) of symbols position where such pair appears in S and T and then by carefully checking the conditions above.

from sys import stdin


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

N = int(input())
s = input()
t = input()

humming = 0
mismatches = {}
t_mismatches = {}
s_mismatches = {}

two = None
one = None

for i in range(N):
    if s[i] != t[i]:
        if not two:
            if (t[i], s[i]) in mismatches:
                two = (mismatches[(t[i], s[i])], i)
            elif not one:
                if s[i] in s_mismatches:
                    one = (s_mismatches[s[i]], i)
                elif t[i] in t_mismatches:
                    one = (t_mismatches[t[i]], i)
                t_mismatches[s[i]] = i
                s_mismatches[t[i]] = i

            mismatches[(s[i], t[i])] = i
        humming += 1

if two:
    print(humming - 2)
    print(two[0] + 1, two[1] + 1)
elif one:
    print(humming - 1)
    print(one[0] + 1, one[1] + 1)
else:
    print(humming)
    print(-1, -1)

First, let's find the longest regular bracket Substring using a stack. To do that, Let's introduce a variable to store the index of the last unregular substring and let's iterate through the string. If the character is "$$$($$$", we will append its index to the stack. If the character is "$$$)$$$", we have three cases:

1. If the stack is empty, it means the substring up to this point is not regular, and we will update our 'last unregular' variable to this index.
2. After popping the last value from the stack, if the stack is empty, we know the substring that starts from the last unregular $$$index + 1$$$ to this position is regular.
3. After popping the last value from the stack, if there is still a value on the stack, it means the substring that starts from the $$$index$$$ (that is on the top of the stack) $$$+ 1$$$ to this position is regular. So, every time we find a regular sequence, we will take the maximum. The next step is to count how many regular substrings there are with this maximum value, using the same approach again

s = input()
longest = 0
stack = []
last = -1
for i, ch in enumerate(s):
    if ch == "(":
        stack.append(i)
    else:
        if stack:
            stack.pop()
            if stack:
                longest = max(longest, i - stack[-1])
            else:
                longest = max(longest, i - last)
        else:
            last = i
res= 0
last = -1
stack = []
for i, ch in enumerate(s):
    if ch == "(":
        stack.append(i)
    else:
        if stack:
            stack.pop()
            if stack:
                if (i - stack[-1]) == longest:
                    res += 1
            else:
                if i - last == longest:
                    res += 1
        else:
            last = i
if longest == 0:
    print(0, 1)
else:
    print(longest, res)

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

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

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

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

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

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

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

chars = input()
stack = []

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

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

Check the predicate for every prefix.

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

from sys import stdin

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


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

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

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

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

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

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

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

from collections import deque

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

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

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

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

    maxIndex += 1

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

for pair in ans:
    print(*pair)

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

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

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

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

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

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

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

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

from sys import stdin


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

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

ans = [0]*N

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

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

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

Let's sort the numbers in ascending order. It becomes immediately clear that it is not profitable for us to increase the numbers that are equal to the last number (the maximum of the array). It turns out that every time you need to take such a subset of the array, in which all the numbers, except the maximums. And once for each operation, the numbers in the subset are increased by one, then how many times can the operation be performed on the array? Accordingly $$$max(a)−min(a)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    print(max(nums) - min(nums)) 

We can iterate through the elements of $$$a$$$ and $$$b$$$ simultaneously. For each element $$$a_i$$$, we consider the following cases:

1. If $$$a_i = b_i$$$, no operation is needed, and we move on to the next element.

2. If $$$a_i > b_i$$$, we need to decrease $$$a_i$$$ to match $$$b_i$$$. Since the elements of $$$a$$$ can only be $$$-1$$$, $$$0$$$, or $$$1$$$, the only way to decrease $$$a_i$$$ is by finding an element $$$a_j < i$$$ such that $$$a_j = -1$$$. Subtracting $$$1$$$ from $$$a_i$$$ and adding $$$1$$$ to $$$a_j$$$ does not change the sum of $$$a_i$$$ and $$$a_j$$$, but it decreases $$$a_i$$$ by $$$1$$$. If such an element $$$a_j$$$ does not exist, then it's impossible to transform $$$a$$$ into $$$b$$$.

3. If $$$a_i < b_i$$$, we need to increase $$$a_i$$$ to match $$$b_i$$$. Similarly, the only way to increase $$$a_i$$$ is by finding an element $$$a_j < i$$$ such that $$$a_j = 1$$$. Adding $$$1$$$ to $$$a_i$$$ and subtracting $$$1$$$ from $$$a_j$$$ does not change the sum of $$$a_i$$$ and $$$a_j$$$, but it increases $$$a_i$$$ by $$$1$$$. If such an element $$$a_j$$$ does not exist, then it's impossible to transform $$$a$$$ into $$$b$$$.

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
    
	vals = set()
	ans = True
	for i in range(n):
    	if a[i] != b[i]:
        	if b[i] - a[i] > 0:
            	if 1 not in vals:
                	ans = False
                	break
        	else:
            	if -1 not in vals:
                	ans = False
                	break
    	vals.add(a[i])
	print("YES" if ans else "NO")

First, we can filter out the numbers that have appeared at least $$$k$$$ times in the array and sort them in ascending order.

We will keep track of the start and end of the current range as we iterate through the sorted list. Additionally, we keep track of the maximum range found so far.

Next, We maintain a current range while iterating through the sorted list of numbers. If a number $$$a_i$$$​ is consecutive to the previous number $$$a_{i−1}$$$ $$$i.e.$$$ $$$( a_i = a_{i -1} + 1)$$$, it is part of the current range. Otherwise, $$$a_i​$$$ marks the start of a new range. We keep track of the maximum range found so far as we iterate through the list.

But, when using a hash table data structure, there's a risk of encountering test cases deliberately crafted to induce collisions. In such scenarios, the worst-case time complexity for retrieval and insertion operations could O(n), impacting the overall time complexity of the solution, which could become O(n2). To remove this risk ,one possible solution is employing XOR with a random number during both insertion and retrieval from the hash table. By XORing each number with a randomly generated value before inserting it into the hash table, we can create unique hash values for each number. This process helps distribute the numbers evenly across the hash table. Similarly, during retrieval, XORing the search key with the same random number allows us to accurately locate the corresponding entry in the hash table.

from collections import Counter
from random import randint

for _ in range(int(input())):
   n, k = map(int, input().split())
   numbers = list(map(int, input().split()))
   rand = randint(10000, 10**10)
   c = Counter([a ^ rand for a in numbers])
   filtered_numbers = [a ^ rand for a in c.keys() if c[a] >= k]
   filtered_numbers.sort()
 
   max_span = -1
   start = end = None
   current_start = current_end = None

   for num in filtered_numbers:
   	if current_end is None or num != current_end + 1:
       	if current_start is not None and current_end is not None:
           	span = current_end - current_start
           	if span > max_span:
               	max_span = span
               	start = current_start
               	end = current_end

       	current_start = current_end = num
   	else:
       	current_end = num

   if current_start is not None and current_end is not None:
   	span = current_end - current_start
   	if span > max_span:
       	max_span = span
       	start = current_start
       	end = current_end
   if start:
   	print(start, end)
   else:
   	print(-1)

Let's consider two sequences of digits: $$$e_1,e_2,…,e_k$$$ and $$$o_1,o_2,…,o_m$$$, there $$$e_1$$$ is the first even digit in $$$a$$$, $$$e_2$$$ is the second even digit and so on and $$$o_1$$$ is the first odd digit in $$$a$$$, $$$o_2$$$ is the second odd digit and so on.

Since you can't swap digits of same parity, the sequence $$$e$$$ of even digits of $$$a$$$ never changed. Sequence $$$o$$$ of odd digits of $$$a$$$ also never changed. So the first digit in the answer will be equal to $$$e_1$$$ or to $$$o_1$$$. And since we have to minimize the answer, we have to chose the $$$min(e_1,o_1)$$$ as the first digit in answer and them delete it from the corresponding sequence (in this way sequence $$$e$$$ turn into $$$e_2,e_3,…,e_k$$$ or sequence $$$o$$$ turn into $$$o_2,o_3,…,o_m$$$). Second, third and followings digits need to choose in the same way.

from sys import stdin


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

T = int(input())
for _ in range(T):
    num = input()
    evens = []
    odds = []
    for digit in num:
        if int(digit)%2 == 1:
            odds.append(digit)
        else:
            evens.append(digit)
    
    ans = []
    p1 = p2 = 0
    len_evens = len(evens)
    len_odds = len(odds)
    while p1 < len_evens and p2 < len_odds:
        if evens[p1] < odds[p2]:
            ans.append(evens[p1])
            p1 += 1
        else:
            ans.append(odds[p2])
            p2 += 1
    ans.extend(evens[p1:])
    ans.extend(odds[p2:])
    
    print(*ans, sep="")

To ensure that all rows and columns form palindromes, each cell $$$a_{i,j}$$$ should be equal to $$$a_{n−i−1,j}$$$, $$$a_{n−i−1,j}$$$​, $$$a_{i,m−j−1}$$$, as well as $$$a_{n−i−1,m−j−1}$$$.

so the problem is reduced to finding the optimal number for each four of numbers (maybe less for some positions in the matrix). This number is the median of these numbers (the average of the sorted set). This can be proved by induction. Here is the link for the proof. The answer will be the sum of the differences between the median of the "four" and each number in the "four" for all "fours".

for _ in range(int(input())):
   n,m = map(int,input().split())
   mat = [list(map(int,input().split())) for i in range(n)]
   tot = 0
   for i in range(n):
   	for j in range(m):
       	mid_point = sorted([mat[i][j],mat[i][m-j-1],mat[n-i-1][j],mat[n-i-1][m-j-1]])[2]
       	tot += abs(mat[i][j]-mid_point)
   print(tot)    

Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i≠t_1$$$, we should output $$$s_i−t_1$$$. Otherwise, output $$$s_i−t_2$$$ — the second highest strength, which is the next best person.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    t = sorted(s)
    for i in range(n):
        if s[i] != t[-1]:
            s[i] = s[i] - t[-1]
        else:
            s[i] = s[i] - t[-2]
    print(*s)

We precalculate some array $$$A_{i}$$$, that $$$A_{i} = 1$$$, if $$$s_{i} = s_{i + 1}$$$, else $$$A_{i} = 0$$$. Now for any query ($$$l$$$, $r$), we need to find sum of $$$A_{i}$$$, such that $$$(l ≤ i < r)$$$. It has not become a range sum query problem. To solve this problem, we can precalculate a prefix sum array $$$Sum$$$, where $$$Sum_{i} = A_{1} + A_{2} + ... + A_{i}$$$. Then the sum of the interval ($$$l$$$, $$$r$$$) is $$$Sum_{r} — Sum_{l-1}$$$.

s = input()
m = int(input())
queries = []

for _ in range(m):
    queries.append(list(map(int, input().split())))

pref = [0]
for indx in range(len(s) - 1):
    if s[indx] == s[indx + 1]:
        pref.append(pref[-1] + 1)
    
    else:
        pref.append(pref[-1])


for left, right in queries:
    print(pref[right - 1] - pref[left - 1])

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the given input array in ascending order.
2. It iterates through the sorted array. For each value, check if the current serving time is greater than the total waiting time of the current person (the sum of the previous satisfied customer's serving time ) . If it is, it means the person is satisfied. Otherwise, the person is not satisfied and will leave the queue automatically.

Time Complexity: O(n), n is the size of the queue.

Space Complexity: O(1)

    n = int(input())
    time = sorted(map(int, input().split()))

    ans = waitTime = 0
    for i in range(n):
        if waitTime <= time[i]:
            ans += 1
            waitTime += time[i]
    
    print(ans)

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum $$$≥$$$ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Aman can choose will have a sum $$$<$$$ than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Time complexity: O(n)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = 0
    for num in a:
        total_sum += num
        if total_sum <= 0:
            return False
    total_sum = 0
    for i in range(n - 1, -1, -1):
        total_sum += a[i]
        if total_sum <= 0:
            return False
    return True

T = int(input())
for _ in range(T):
    if solve():
        print("YES")
    else:
        print("NO")

Let's prove that for an array $$$a$$$ that was created by using a number of operations, with a sum of elements $$$s$$$ we can add into $$$a$$$ any number $$$x$$$ $$$(1≤x≤s)$$$.

Suppose that it is true that in the array $$$a$$$ with some length $$$l$$$ we introduce a number $$$x$$$ $$$(1≤x≤suma)$$$. Then after introducing we can create using the initial elements of the array any number $$$b$$$ $$$(1≤b≤suma)$$$ and using the element $$$x$$$ and some subset of the initial elements we can create any number $$$b$$$ $$$(x≤b≤suma+x)$$$, and because $$$x≤suma$$$ we proved that for the new array of length $$$l+1$$$ we can still create any number between $$$1$$$ and $$$suma+x$$$.

So we just need to verify if our array satisfies the above condition. We sort the array and check for every element whether the total sum so far is less than the current element. If that is the case for any of the elements our answer is ‘NO’ otherwise ‘YES’.

t = int(input())
for i in range(t):
    n = int(input())
    nums = list(map(int,input().split()))
    nums.sort()
    pos = 1
    if nums[0] != 1:
        pos = 0
    total = 1
    for i in range(1,n):
        if nums[i] > total:
            pos = 0
            break
        total += nums[i]
    if pos:
        print("YES")
    else:
        print("NO")

How would you solve count subarrays with sum equal to $$$k$$$ optimally using the concept of prefix sum?

We will keep track of the prefix product.

Lets call the current prefix product $$$currentPrefix$$$.
If $$$currentPrefix$$$ is positive,

1. If we have seen another positive prefix before, it means that the segment of the currentPrefix excluding the previous prefix would give us a positive product, because $$$(+)*(+) = (+)$$$. The amount of previous positive prefixes tells us how many segments with positive product we can have at the current prefix.
2. Similarly, if we have seen a negative prefix before, it means that the remaining part of the current segment has to be negative, because $$$(-)*(-) = (+)$$$.

In the same manner, if $$$currentPrefix$$$ is negative,

1. We increment the negative product segments by the number of previous positive prefixes, because $$$(+)*(-) = (-)$$$.
2. We increment the positive product segments by the number of previous negative prefixes, because $$$(-)*(+) = (-)$$$.

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

pos_prefixes = 1 # as an identity, to take into account a whole prefix
neg_prefixes = 0

pos_seg_count = 0
neg_seg_count = 0

prefix = 1

for num in a:
    prefix *= (num//abs(num)) # we only want the sign, not the magnitude

    if prefix > 0:
        pos_seg_count += pos_prefixes
        neg_seg_count += neg_prefixes
        pos_prefixes += 1
        
    else:
        pos_seg_count += neg_prefixes
        neg_seg_count += pos_prefixes
        neg_prefixes += 1

print(neg_seg_count, pos_seg_count)

Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i≠t_1$$$, we should output $$$s_i−t_1$$$. Otherwise, output $$$s_i−t_2$$$ — the second highest strength, which is the next best person.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    t = sorted(s)
    for i in range(n):
        if s[i] != t[-1]:
            s[i] = s[i] - t[-1]
        else:
            s[i] = s[i] - t[-2]
    print(*s)

We precalculate some array $$$A_{i}$$$, that $$$A_{i} = 1$$$, if $$$s_{i} = s_{i + 1}$$$, else $$$A_{i} = 0$$$. Now for any query ($$$l$$$, $r$), we need to find sum of $$$A_{i}$$$, such that $$$(l ≤ i < r)$$$. It has not become a range sum query problem. To solve this problem, we can precalculate a prefix sum array $$$Sum$$$, where $$$Sum_{i} = A_{1} + A_{2} + ... + A_{i}$$$. Then the sum of the interval ($$$l$$$, $$$r$$$) is $$$Sum_{r} — Sum_{l-1}$$$.

s = input()
m = int(input())
queries = []

for _ in range(m):
    queries.append(list(map(int, input().split())))

pref = [0]
for indx in range(len(s) - 1):
    if s[indx] == s[indx + 1]:
        pref.append(pref[-1] + 1)
    
    else:
        pref.append(pref[-1])


for left, right in queries:
    print(pref[right - 1] - pref[left - 1])

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the given input array in ascending order.
2. It iterates through the sorted array. For each value, check if the current serving time is greater than the total waiting time of the current person (the sum of the previous satisfied customer's serving time ) . If it is, it means the person is satisfied. Otherwise, the person is not satisfied and will leave the queue automatically.

Time Complexity: O(n), n is the size of the queue.

Space Complexity: O(1)

    n = int(input())
    time = sorted(map(int, input().split()))

    ans = waitTime = 0
    for i in range(n):
        if waitTime <= time[i]:
            ans += 1
            waitTime += time[i]
    
    print(ans)

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum $$$≥$$$ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Aman can choose will have a sum $$$<$$$ than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Time complexity: O(n)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = 0
    for num in a:
        total_sum += num
        if total_sum <= 0:
            return False
    total_sum = 0
    for i in range(n - 1, -1, -1):
        total_sum += a[i]
        if total_sum <= 0:
            return False
    return True

T = int(input())
for _ in range(T):
    if solve():
        print("YES")
    else:
        print("NO")

Track the maximum value encountered.

Initializes the answer $$$ans$$$ as $$$YES$$$ assuming initially that it's possible to reach every position. Iterates over the given input array in the sequence (except the last one) using a loop. At each position, update the maximum value encountered so far $$$currMax$$$ among the first $$$i$$$ elements. If $$$currMax$$$ becomes greater than $$$(i + 1)$$$ (indicating there's a gap between the maximum reachable position and the current position), and the corresponding rule for that position is $$$0$$$, update the answer to $$$NO$$$ and break out of the loop.

Time Complexity: O(n), n is the size of the input array. Space Complexity: O(1)

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

    ans = 'YES'
    currMax = 0
    for i in range(n - 1):
        currMax = max(currMax, nums[i])
        if currMax > i + 1 and rules[i] == '0':
            ans = 'NO'
            break

    print(ans)

How would you solve count subarrays with sum equal to $$$k$$$ optimally using the concept of prefix sum?

We will keep track of the prefix product.

Lets call the current prefix product $$$currentPrefix$$$.
If $$$currentPrefix$$$ is positive,

1. If we have seen another positive prefix before, it means that the segment of the currentPrefix excluding the previous prefix would give us a positive product, because $$$(+)*(+) = (+)$$$. The amount of previous positive prefixes tells us how many segments with positive product we can have at the current prefix.
2. Similarly, if we have seen a negative prefix before, it means that the remaining part of the current segment has to be negative, because $$$(-)*(-) = (+)$$$.

In the same manner, if $$$currentPrefix$$$ is negative,

1. We increment the negative product segments by the number of previous positive prefixes, because $$$(+)*(-) = (-)$$$.
2. We increment the positive product segments by the number of previous negative prefixes, because $$$(-)*(+) = (-)$$$.

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

pos_prefixes = 1 # as an identity, to take into account a whole prefix
neg_prefixes = 0

pos_seg_count = 0
neg_seg_count = 0

prefix = 1

for num in a:
    prefix *= (num//abs(num)) # we only want the sign, not the magnitude

    if prefix > 0:
        pos_seg_count += pos_prefixes
        neg_seg_count += neg_prefixes
        pos_prefixes += 1
        
    else:
        pos_seg_count += neg_prefixes
        neg_seg_count += pos_prefixes
        neg_prefixes += 1

print(neg_seg_count, pos_seg_count)

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)

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the list of programming skills in ascending order.
2. Initialize two pointers, $$$start$$$ and $$$end$$$, both pointing to the beginning of the sorted list.
3. Iterate over the list using pointer $$$start$$$, and for each student skill $$$(skills[start])$$$, move pointer $$$(end)$$$ forward until the difference between the current skill `$$$(skills[end])$$$ and $$$(skills[start])$$$ exceeds 5.
4. At each iteration, update the maximum number of students in a balanced team $$$(maxNum)$$$ by taking the maximum between the current value of $$$maxNum$$$ and the difference between $$$end$$$ and $$$start$$$.
5. Finally, output the maximum number of students in a balanced team $$$(maxNum)$$$.

Time Complexity: Sorting the list takes O(n log n) time. The iteration over the sorted list takes O(n) time. Thus, the overall time complexity is O(n log n).

Space Complexity: Sorting requires O(1)

    n = int(input())
    skills = sorted(map(int, input().split()))

    maxNum = 0
    end = 0

    for start in range(n):

        while end < n and skills[end] - skills[start] <= 5:
            end += 1
        maxNum = max(maxNum, end - start)

    print(maxNum)

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)

Think about small substrings.

What are the strings that satisfy the given conditions?

If you got Wrong Answer on test $$$2$$$, then you're probably not checking $$$7$$$ length strings.

The following are all the possible minimal substrings (there aren't that many) which satisfy the given conditions: "aa", "aba", "aca", "abca", "acba", "abbacca", "accabba". Any other string that satisfies the condition contains at least one of these as a substring, and hence is not the optimal substring for the answer.

Claim: If a substring exists which satisfies the given conditions, then the length of the shortest such substring is at most $$$7$$$. Otherwise the solution does not exist.

Proof: Let us consider that the solution exists. We will try to prove this by breaking this into the following cases:

Case 1: There exist two such "a" whose distance is less than or equal to $$$2$$$, where distance is the absolute difference of their indices.

• In this case where there are two such "a" whose distance is less than $$$2$$$, then either these two "a" are present consecutive or there is only one single letter between these two "a". All these minimal substrings are "aa", "aba" and "aca" which satisfies all the given conditions. Hence we can say that the shortest length of such substring that satisfies the given conditions is at most $$$3$$$ in this case.

Case 2: There exists no two such "a" whose distance is less than or equal to $$$2$$$.

• In this case all the consecutive occurrences of "a" are present at a distance at least $$$3$$$. Then in order for the number of "a" to be bigger than that of "b" and "c" the string must look like "a??a??a??a??a".
• Let us define "??" as a block. Now if there is any block consisting of different characters $$$i.e$$$ "bc" or "cb" then the substring "a??a" will satisfy all the given conditions and hence the minimal length will be $$$4$$$.
• Notice that there must be at least one block of "bb" and at least one block of "cc", otherwise "a" will not be in a majority. Hence, there must exist 2 consecutive blocks equal to "bb" and "cc" or "cc" and "bb" in the string (otherwise all blocks would be of the same character). Hence we can pick the substring "abbacca" or "accabba" which satisfies the given conditions. The minimal length is, therefore, $$$7$$$ in this case.

Therefore we can say that the shortest length of such substring that satisfies the given conditions is at most $$$7$$$ in this case.

Thus, it suffices to only check all substrings of length up to $$$7$$$ and find the smallest among them that satisfies the given conditions (or report that it does not exist).

Time Complexity: $$$\mathcal{O}(7⋅n)$$$

from sys import stdin


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


T = int(input())

for _ in range(T):
    N = int(input())
    s = input()

    if "aa" in s:
        print(2)
    elif "aba" in s or "aca" in s:
        print(3)
    elif "abca" in s or "acba" in s:
        print(4)
    elif "abbacca" in s or "accabba" in s:
        print(7)
    else:
        print(-1)

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")