We can re-write the formula as $$$b_i = a_i + (b_{i + 1} - b_{i + 2} + \dots)$$$. Then, we can reduce $$$(b_{i + 1} - b_{i + 2} + \dots)$$$ to $$$a_{i + 1}$$$. So, $$$b_i = a_i + a_{i + 1}$$$.

n = int(input())
arr = list(map(int, input().split()))
arr.append(0)
ans = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    ans[i] = arr[i] + arr[i + 1]
print(*ans[:n])

If $$$n$$$ is greater than 26 or the length of the word is less than $$$n$$$, it's impossible to reach $$$n$$$ distinct characters. Otherwise, we can count how many characters are left to reach $$$n$$$ distinct characters.

word = input()
n = int(input())

if n > 26 or len(word) < n:
    print("impossible")
else:
    print(max(0, n - len(set(word))))

The solution to preventing "trygub" from being a subsequence involves disrupting the specific order of its characters. Since "trygub" requires the characters 't', 'r', 'y', 'g', 'u', and 'b' to appear in that precise sequence, the approach is to rearrange the string so that this order cannot be maintained. The simplest way to achieve this is by sorting the string, which effectively disturbs the positions and prevents the sequence from forming. However, a more efficient solution is to start the rearranged string with any character that is not 't' from "trygub." By beginning with a different character and appending the others afterward, we ensure that the required sequence is broken, thus preventing "trygub" from appearing as a subsequence.

Time complexity = $$$O(n)$$$. Space complexity = $$$O(1)$$$.

import sys

input = lambda: sys.stdin.readline().rstrip()
t = int(input())

for _ in range(t):
    N = int(input())
    s = input()
    ans = ["b"] * s.count("b")
    
    for char in s:
        if char != "b":
            ans.append(char)
    
    print("".join(ans))

What if the given number $$$n$$$ cannot be represented as $$$2^{cnt2}⋅3^{cnt3}⋅5^{cnt5}$$$? It means that the answer is $$$-1$$$ because all actions we can do are: remove one power of two, remove one power of three and add one power of two, and remove one power of five and add two powers of two. So if the answer is not $$$-1$$$ then it is $$$cnt2+2.cnt3+3.cnt5$$$. If this formula isn't pretty clear for you, you can just simulate the process, performing actions from third to first.

import sys
t = int(sys.stdin.readline().strip())

for _ in range(t):

    n = int(sys.stdin.readline().strip())
    cnt2, cnt3, cnt5 = 0, 0, 0

    while n % 2 == 0:
        n //= 2
        cnt2 += 1

    while n % 3 == 0:
        n //= 3
        cnt3 += 1

    while n % 5 == 0:
        n //= 5
        cnt5 += 1
        
    if n != 1:
        print(-1)
    else:
        print(cnt2 + 2 * cnt3 + 3 * cnt5)

This problem can be solved in a straightforward way. The key observation is that the order in which the letters are called out does not matter in this game. We only need to know how many times each letter is called out in order to go from the initial word $$$s$$$ to the final word $$$t$$$.

So first, let us compute the number of occurrences of each letter from 'A' to 'Z' in both words $$$s$$$ and $$$t$$$. Let’s call them $$$s_a$$$ and $$$t_a$$$ for each letter $$$a$$$. Using these numbers, we can calculate how many times each letter shall be called in order to get a chance of getting to $$$t$$$. That is $$$s_a − t_a$$$ times for each letter $$$a$$$.

If $$$s_a − t_a < 0$$$ for any letter $$$a$$$, then the answer is 'NO'. Otherwise, there is a chance for a positive answer. However, we also need to verify that the order of the letters in $$$t$$$ is correct. The easy way to verify it is to simulate the game, dropping the first $$$s_a − t_a$$$ occurrences of each letter $$$a$$$, and then compare the result with $$$t$$$.

from collections import Counter
from sys import stdin


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

T = int(input())

for _ in range(T):
    s, t = input().split()
    s_cnt = Counter(s)
    t_cnt = Counter(t)

    remove_cnt = {}
    ok = True
    for ch in s_cnt:
        remove_cnt[ch] = s_cnt[ch] - t_cnt[ch]
        if remove_cnt[ch] < 0:
            ok = False
    
    if not ok:
        print("NO")
        continue
    
    new_s = []
    for ch in s:
        if remove_cnt[ch] > 0:
            remove_cnt[ch] -= 1
        else:
            new_s.append(ch)
    
    if "".join(new_s) == t:
        print("YES")
    else:
        print("NO")

Think of each bit independently.

Solution:

Initially, we set all $$$a_i=2^{30}−1$$$ (all bits on).

You can go through every $$$i$$$,$$$j$$$ such that $$$i≠j$$$ and do $$$a_i$$$ &= $$$M_{i,j}$$$ and $$$a_j$$$ &= $$$M_{i,j}$$$.

Then we check if $$$M_{i,j}=a_i|a_j$$$ for all pairs. If this holds you found the array else the answer is $$$NO$$$.

Proof:

Initially, all elements have all their bits set on and we remove only the bits that affect our answer. If $$$M_{i,j}$$$ doesn't have a specific bit then definitely neither $$$a_i$$$ nor $$$a_j$$$ should have it. If $$$M_{i,j}$$$ has a specific bit on then we don't have to remove anything (in the end we want at least one of $$$a_i$$$ and $$$a_j$$$ to have the bit on).

import sys


def solve():
    n = int(sys.stdin.readline().strip())
    matrix = []

    for _ in range(n):
        row = list(map(int, sys.stdin.readline().strip().split()))
        matrix.append(row)

    a = [2**30 - 1] * n
    
    for i in range(n):
        for j in range(n):
            if i != j:
                a[i] &= matrix[i][j]
                a[j] &= matrix[i][j]

    for i in range(n):
        for j in range(n):
            if i != j and a[i] | a[j] != matrix[i][j]:
                print("NO")
                return
            
    print("YES")
    print(*a)
    
t = int(sys.stdin.readline().strip())

for _ in range(t):
    solve()

To solve this problem, we use binary search on the minimum possible maximum waiting time, denoted as x.

A. Binary Search on x: Perform a binary search to find the smallest x such that all customers can be assigned to three or fewer carvers with each having a maximum waiting time of x.

B. Sorting: First, sort the array of customers' pattern requests to facilitate efficient grouping.

C. Assigning Carvers: Start assigning customers to carvers from the beginning of the sorted list. For each carver, choose a range [l, r] of customers and set the optimal pattern as (r + l) // 2 to minimize the maximum waiting time. If the difference between this average pattern and the range limits exceeds x, start a new range for the next carver. Continue until all customers are assigned or more than three carvers are needed.

D. Adjust x: If three or fewer carvers suffice, reduce x to find a smaller maximum waiting time. If more than three carvers are needed, increase x and retry.

Time Complexity

The time complexity is O(n * log(m)), where n is the number of customers, and m is the difference between the maximum and minimum possible waiting times.

def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()

    def is_valid_waiting_time(waiting_time):
        start = nums[0]
        count = 1

        for i in range(1, n):
            if (nums[i] - start + 1) // 2 > waiting_time:
                count += 1
                start = nums[i]

        return count <= 3

    l = 0
    r = max(nums)

    while l <= r:
        mid = (l + r) // 2
        if is_valid_waiting_time(mid):
            r = mid - 1
        else:
            l = mid + 1

    print(l)

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

First, check the parity of $$$k$$$. If $$$k$$$ is odd, there is no solution because the cycle described in the task must have an even length. Otherwise, proceed as follows: Use the breadth-first search (BFS) algorithm to find the shortest distance from the starting cell to all other free cells. Next, move through the grid. Before each move, determine the next cell to go to. Consider the directions in the order $$$( "D", "L", "R", "U")$$$. The current direction is $$$c$$$. If the cell $$$x$$$ corresponding to a move in direction $$$c$$$ is empty and the distance from it to the starting cell does not exceed the remaining number of steps, then move in direction $$$c$$$, add the corresponding letter to the answer, and proceed to the next step. If at any step it is impossible to move the Robot, a cycle of length $$$k$$$ does not exist. Otherwise, once the Robot has completed $$$k$$$ steps, simply print the answer.

from collections import deque

n, m, k = map(int, input().split())
if k % 2:
    print("IMPOSSIBLE")
    exit(0)

maze = []
direc = {  (1, 0): 'D', (0, -1): 'L', (0, 1): 'R', (-1, 0): 'U' }
src = None 
for i in range(n):
    maze.append(input())
    for j in range(m):
        if maze[i][j] == 'X':
            src = (i, j)
            break
        
#bfs
track = [[float('inf') for _ in range(m)] for _ in range(n)]
track[src[0]][src[1]] = 0
queue = deque([(src, 0)])
visited = set([src])
while queue:
    loc, step = queue.popleft()
    for dx, dy in direc:
        x, y = loc[0] + dx, loc[1] + dy
        if 0 <= x < n and 0 <= y < m and maze[x][y] != '*' and (x, y) not in visited:
            track[x][y] = min(track[x][y], step + 1)
            queue.append(((x, y), step + 1))
            visited.add((x, y))

#dfs
stack = [src]
ans = []
while stack:
    loc = stack.pop()
    if len(ans) == k:
        print("".join(ans))
        exit(0)
    for dx, dy in direc:
        x, y = loc[0] + dx, loc[1] + dy
        if 0 <= x < n and 0 <= y < m and track[x][y] <= k &mdash; len(ans):
            ans.append(direc[(dx, dy)])
            stack.append((x, y))
            break

print("IMPOSSIBLE")

Since it is counting pairs, we can use divide and conquer approach.

Let's assume we have divided the original string in half, getting $$$substring1$$$ and $$$substring2$$$. Let's have a segment $$$(l, r)$$$ to be inverted where $$$l$$$ lies in $$$substring1$$$ and $$$r$$$ lies in $$$substring2$$$. We can now invert some suffix of $$$substring1$$$ and invert some prefix of $$$substring2$$$ and try to balance the brackets.

There is one fact to create a balanced sequence. Because the original string is balanced:

• For $$$substring1$$$: All the closing brackets must have opening pairs. And, there could be zero or more unbalanced opening brackets.
• For $$$substring2$$$: All the opening brackets must have closing pairs. And, there could zero or more unbalanced closing brackets.

For instance, after some inversion, if we have $$$Y$$$ amount opening brackets that didn't get a closing match in the fist substring, we should find $$$Y$$$ amount of excess closing brackets in the second substring.

Now, with the same logic we can further divide the two substrings, and account for every $$$(l, r)$$$ pair.

Let's divide $$$substring1$$$ into halves, $$$a$$$ and $$$b$$$. After some $$$(l, r)$$$ inversion, where $$$l$$$ lies in $$$a$$$ and $$$r$$$ lies in $$$b$$$, let's say we have $$$X$$$ amount of excess opening brackets in $$$a$$$, the $$$X$$$ closing matches could come from not just $$$b$$$, but the whole suffix starting from and including $$$b$$$. The same applies if we have some subsegment before $$$a$$$. So, to handle that case, we do some preprocessing and count excess prefix openings and excess suffix closings.

Time complexity: $$$nlog(n)$$$
Make sure to use $$$PyPy 3-64$$$.

import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

def conquer(l1, r1, l2, r2):

    excess_opening = defaultdict(int)
    inverted_open = 0
    unpaired_closing = 0
    # all closing brackets must have an opening pair on the left subarray
    # invert some suffix of substring 1
    for indx in range(r1, l1 - 1, -1):
        if s[indx] == ')':
            inverted_open += 1
            # follow kadan's algorithm to find opening matches for the closings
            # if we have an excess opening, it is no use for a closing that comes before it
            # so we don't make the unpaired_closing negative
            unpaired_closing = max(unpaired_closing - 1, 0) 
            
        else:
            unpaired_closing += 1
            inverted_open -= 1
        
        # uninverted prefix of this index must provide opening pairs for the unpaired closings
        if pref[indx - 1] >= unpaired_closing:
            excess_opening[pref[indx - 1] + inverted_open] += 1


    unpaired_opening = 0
    inverted_close = 0
    count = 0 # (l, r) matches 

    # invert some prefix of substring 2
    for indx in range(l2, r2 + 1):
        if s[indx] == '(':
            inverted_close += 1
            unpaired_opening = max(unpaired_opening - 1, 0)

        else:
            unpaired_opening += 1
            inverted_close -= 1

        # uninverted suffix of this index must provide closing pairs for the unpaired openings
        if suf[indx + 1] >= unpaired_opening:
            # match 'y' amount of excess opening in the first substring
            # with 'y' amount of closing in the second substring
            count += excess_opening[suf[indx + 1] + inverted_close]

    return count

def divide(l, r):
    if l >= r:
        return 0

    mid = (r + l)//2
    left_count = divide(l, mid)
    right_count = divide(mid + 1, r)
    cur_count = conquer(l, mid, mid + 1, r)
    return left_count + right_count + cur_count

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

    pref = [0]*(n + 1)
    suf = [0]*(n + 1)

    openning_pref = 0
    closing_suf = 0
    for i in range(n):
        openning_pref += 1 if s[i] == '(' else -1
        closing_suf += 1 if s[n - i - 1] == ')' else -1

        pref[i] = openning_pref
        suf[n - i - 1] = closing_suf
    
    ans = divide(0, n - 1)
    print(ans)