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