Considering an array a of n (n≥2) positive integers, the following inequality holds for 2≤i≤n: gcd($$$a_1$$$,$$$a_2$$$,⋯,$$$a_i$$$)≤gcd($$$a_1$$$,$$$a_2$$$)≤2

Therefore, when the prefix [$a_1$,$$$a_2$$$] of a is good, we can show that all the prefixes of a whose length is no less than 2 are good, then a is beautiful. It is obvious that [$$$a_1$$$,$$$a_2$$$] is good when a is beautiful. So we get the conclusion that a is beautiful if and only if the prefix [$$$a_1$$$,$a_2$] is good.

We can check if there exist $$$a_i$$$,$$$a_j$$$ (i≠j) such that gcd($$$a_i$$$,$$$a_j$$$)≤2. If so, we can move $$$a_i$$$,$$$a_j$$$ to the front of a to make it beautiful, then the answer is Yes. If not, the answer is No.

Time complexity: O($$$n^2$$$log$$$10^6$$$).

import math

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

    for i in range(n):
        for j in range(i + 1, n):
            if math.gcd(a[i], a[j]) <= 2:
                print("Yes")
                return
    print("No")

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

if __name__ == "__main__":
    main()

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), and the operation is [$o_1$,$$$o_2$$$]. Without loss of generality, let the operation lies in the left part of the string. Then $$$o_1$$$≤l,r≤$$$o_2$$$<n+1−r must hold to correct all the illegal positions. 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.

Time complexity: O(n).

def solve():
    n = int(input())
    s = input()

    l = 0
    r = n
    while l < r and s[l] == s[r - 1]:
        l += 1
        r -= 1
    if l >= r:
        print("Yes")
        return
    while l < r and s[l] != s[r - 1]:
        l += 1
        r -= 1
    while l < r and s[l] == s[r - 1]:
        l += 1
        r -= 1
    if l >= r:
        print("Yes")
    else:
        print("No")

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

if __name__ == "__main__":
    main()

Put the negative elements into an array, sort them, and find the sum of m largest modulus.

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    
    ans = 0
    for i in range(m):
        ans += max(0, -a[i])
    
    print(ans)

if __name__ == "__main__":
    main()

Let's iterate over the length of the first segment of the split. Having fixed it, we actually fixed the sum that needs to be collected on all other segments. Since each element must belong to exactly one segment, we can build other segments greedily. If we have found a solution, we will remember the length of the longest segment in it and try to update the answer. We have n possible lengths of the first segment, for each of which we greedily built the answer for n.

Thus, the asymptotics of the solution will be O($$$n^2$$$).

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0] * (n + 1)
    
    for i in range(n):
        s[i + 1] = s[i] + a[i]
    
    ans = n
    for i in range(1, n + 1):
        res = i
        k = i
        for j in range(i + 1, n + 1):
            if s[j] == s[k] + s[i]:
                res = max(res, j - k)
                k = j
        if k == n:
            ans = min(ans, res)
    
    print(ans)

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

if __name__ == "__main__":
    main()

We can easily calculate the sum of money that we need to buy all the bananas that we want, let's name it req.

If n >= req the answer is 0, because we don't need to borrow anything.

Otherwise the answer is req - n.

k, n, w = map(int, input().split())
tot = (w * (w + 1)) // 2
req = tot * k
print(max(req - n, 0))

Let's perform the process in reverse: we will remove the first and last character of the string, if these two characters are different. We should do this as long as possible, since we need to find the shortest initial string.

So the algorithm is straightforward: keep track of the left and right characters, and if they are different, remove both. Otherwise, output the length of the current string (or output 0 if the string became empty).

There are a few ways to implement this. For example, you can keep two pointers, one at the beginning of the string and one at the end, say, l=1 and r=n, and check if $$$s_l$$$=$$$s_r$$$. If it's true, then we increment l and decrement r. Otherwise, we output r−l+1. We stop when l≥r.

The time complexity is O(n).

def solve():
    n = int(input())
    s = input().strip()
    l, r, ans = 0, n - 1, n
    while s[l] != s[r] and ans > 0:
        l += 1
        r -= 1
        ans -= 2
    print(ans)

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

if __name__ == "__main__":
    main()

Let's sort boys and girls by skill. If boy with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use girl with lowest skill to match.

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    m = int(input())
    b = list(map(int, input().split()))
    b.sort()

    boy, girl = 0, 0
    ans = 0
    while boy < n and girl < m:
        diff = abs(a[boy] - b[girl])
        if diff <= 1:
            boy += 1
            girl += 1
            ans += 1
        elif a[boy] < b[girl]:
            boy += 1
        else:
            girl += 1

    print(ans)

if __name__ == "__main__":
    main()

At first we sort all friends in money ascending order. Now the answer is some array subsegment. Next, we use the method of two pointers for finding the required subsegment.

Time complexity — O(n log n).

def main():
    n, d = map(int, input().split())
    v = []
    for i in range(n):
        a, b = map(int, input().split())
        v.append((a, b))
    v.sort()
    sum_val = 0
    ans = 0
    j = 0
    for i in range(n):
        sum_val += v[i][1]
        while j <= i and v[j][0] + d <= v[i][0]:
            sum_val -= v[j][1]
            j += 1
        ans = max(ans, sum_val)
    print(ans)

if __name__ == "__main__":
    main()

First, there exists an optimal answer, in which there are no more than two elements of each color.

Proof: let there exist an optimal answer, in which there are more elements of some color than 2. Then, take the median among the elements of this color and paint in another new color in which no other elements are painted. Then the maximum and minimum among the original color will not change, and in the new color the answer is 0, so the answer remains the same.

Also, if there are two colors with one element each, they can be combined into one, and the answer will not decrease.

It turns out that the numbers are paired (probably except for one; we'll assume it's paired with itself). Sort the array, and then the answer is $$$∑_{pairi<i}$$$$$$a_i$$$−$$$∑_{i<pairi}$$$$$$a_i$$$ ($$$pair_i$$$ is the number that is paired with i-th). Therefore, in the first summand you should take ⌊n/2⌋ the largest, and in the second ⌊n/2⌋ of the smallest elements of the array.

Total complexity: O(nlogn) for sorting.

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    ans = 0
    for i in range(n // 2):
        ans += a[-i-1] - a[i]
    print(ans)
    
    
t = int(input())
for _ in range(t):
    solve()

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

Maximum sum is $$$∑^n_{i=1}|ai|$$$. Minimum number of operations we should do — number of continuous subsequences with negative values of elements.

Total complexity: O(n)

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    sum = 0
    cnt = 0
    open = False
    for x in a:
        sum += abs(x)
        if x < 0 and not open:
            open = True
            cnt += 1
        if x > 0:
            open = False
 
    print(sum, cnt)

One possible solution is to represent a range of equal element as a single element with that value. Construct this array b and loop through it and check how many element bi satisfy the conditions i=0 or $$$b_{i−1}$$$<$$$b_i$$$ and i=n−1 or $$$b_i$$$>$$$b_{i+1}$$$. If exactly one index satisfies these conditions, print "YES" and othewise "NO".

Complexity: O(n)

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    a = []
    for x in arr:
        if not arr or arr[-1] != x:
            a.append(x)

    cnt = 0
    for i in range(len(a)):
        if ((i == 0 or a[i] < a[i - 1]) and (i == len(a) - 1 or a[i] < a[i + 1])):
            cnt += 1

    print("YES" if cnt == 1 else "NO")
 
def main():
    t = int(input())

    for _ in range(t):
        solve()


if __name__ == "__main__":
    main()

Let's note that for each second of color c in the traffic light, we need to find the rightmost green time, and then find the largest distance between color c and the nearest green. Also, let's not forget that traffic light states are cyclical.

To get rid of cyclicity, you can write the string s twice and for each cell of color c from the first half, find the nearest green color (thus we solved the problem with cyclicity). And now we can just follow this line from right to left and maintain the index of the last occurrence of green. If we encounter color c, then we try to update our answer ans=max(ans,last−i), where ans is our answer, last is the nearest time that green was on color, i — current time.

t = int(input())

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

    ans = 0
    last = 0
    for i in range(2 * n - 1, -1, -1):
        j = i % n
        if s[j] == 'g':
            last = i
        if s[j] == c:
            ans = max(ans, last - i)

    print(ans)

Let's rewrite the inequality from $$$a_i$$$+$$$a_j$$$>$$$b_i$$$+$$$b_j$$$ to ($$$a_i$$$−$$$b_i$$$)+($$$a_j$$$−$$$b_j$$$)>0. This looks much simpler. Let's build the array c where $$$c_i$$$=$$$a_i$$$−$$$b_i$$$ and sort this array. Now our problem is to find the number of pairs i<j such that $$$c_i$$$+$$$c_j$$$>0.

Let's iterate over all elements of c from left to right. For simplicity, we consider only "greater" summands. Because our sum ($$$c_i$$$+$$$c_j$$$) must be greater than 0, then at least one of these summands will be positive. So, if $$$c_i$$$≤0, just skip it. Now $$$c_i$$$>0 and we need to calculate the number of such j that $$$c_i$$$+$$$c_j$$$>0 and j<i. It means that each $$$c_j$$$≥−$$$c_{i+1}$$$ (for some j<i) will be okay. Such leftmost position j can be found with bisect_left or binary search. Then add the value i−j to the answer and consider the next element.

Time complexity: O(nlogn).

n = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
diff = [0] * n

for i in range(n):
    diff[i] = A[i] - B[i]

diff.sort()

# find pairs which give diff[i] + diff[j] > 0

total = 0
beg = 0
end = n - 1

while end >= beg:
    while beg < end and diff[beg] + diff[end] <= 0:
        beg += 1
    total += max(0, end - beg)
    end -= 1

print(total)

By the triangle inequality, for all real numbers x, y, z, we have: |x − y| + |y − z| ≥ |x − z| with equality if and only if min(x, z) ≤ y ≤ max(x, z).

Now, take indices i and j such that $$$a_i$$$ and $$$a_j$$$ are the maximum and minimum values of the array, respectively. Then, for each index k, we have $$$a_i$$$≥$$$a_k$$$≥$$$a_j$$$, meaning that |$$$a_i$$$−$$$a_k$$$| + |$$$a_k$$$−$$$a_j$$$| = $$$a_i$$$−$$$a_k$$$+$$$a_k$$$−$$$a_j$$$ = $$$ai$$$−$$$aj$$$ = |$$$ai$$$−$$$aj$$$|, as we desired.

t = int(input())
for _ in range(t):
    n = int(input())
    minv, maxv = 1e9 + 1, -1
    mini = maxi = 0

    for i in range(n):
        a = int(input())
        if a > maxv:
            maxi = i + 1
            maxv = a
        if a < minv:
            mini = i + 1
            minv = a
    print(mini, maxi)

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())
    a = list(map(int, input().split()))
    b = sorted(a)
    for i in range(n):
        if a[i] == b[n - 1]:
            print(a[i] - b[n - 2], end=" ")
        else:
            print(a[i] - b[n - 1], end=" ")
    print()

To solve the problem, it was enough to count the number of planets with the same orbits $$$cnt_i$$$ and sum up the answers for the orbits separately. For one orbit, it is advantageous either to use the second machine once and get the cost c, or to use only the first one and get the cost equal to $$$cnt_i$$$.

from collections import defaultdict

t = int(input())

for _ in range(t):
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = defaultdict(int)
    ans = 0
    for i in range(n):
        cnt[a[i]] += 1
        if cnt[a[i]] <= c:
            ans += 1
    print(ans)
}

Let's sort the arrays first.

Let's check the two smallest elements in the arrays and investigate their behavior. First, obviously, if $$$a_1$$$+1<$$$b_1$$$ (as nothing can be matched with $$$a_1$$$) or $$$a_1$$$>$$$b_1$$$ (as nothing can be matched with $$$b_1$$$) the answer is No. Then, it's possible that $$$a_1$$$=$$$b_1$$$=x. In this case, we have to have at least one x in the array a at the end. Hence, we can leave $$$a_1$$$ untouched, as it already suits to $$$b_1$$$. It's also possible that $$$a_1$$$+1=$b_1$. Here we have to increase $$$a_1$$$ by 1. In both cases, the task is reduced to the smallest one.

Going to the exact solution from this logic, we just have to sort both arrays and check that for each 1≤i≤n it's $$$a_i$$$=$$$b_i$$$ or $$$a_i$$$+1=$b_i$.

The complexity of the solution is O(nlog(n)).

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort()
    ok = True
    for i in range(n):
        if a[i] + 1 != b[i] and a[i] != b[i]:
            ok = False
            break
    print("YES" if ok else "NO")

Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights.

Solution complexity: O(n), since we can sort by counting.

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

a.sort()

for i in a:
    print(i, end=' ')