Consider the substring of $$$s$$$ from the second character to the last, or $$$s_2s_3⋯s_n$$$. If it's not palindrome, then the answer must be $$$n−1$$$. What if it's palindrome? This implies that $$$s_2=s_n, s_3=s_{n−1}$$$, and so on. Meanwhile, the fact that $$$s$$$ is palindrome implies $$$s_1=s_n, s_2=s_{n−1}$$$, etc. So we get $$$s_1=s_n=s_2=s_{n−1}=⋯$$$ or that all characters in $$$s$$$ is the same. In this situation, every subsequence of $$$s$$$ is palindrome of course, so the answer should be $$$−1$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    s = sys.stdin.readline().strip()
    if len(set(list(s))) == 1:
        print(- 1)
    else:
        print(len(s) - 1)

Every number can be represented as a product of prime numbers.

The only even prime number is 2.

We divide the given number by 2 until we can't. If the number that we get at the end is 1, that means the number doesn't have an odd divisor except 1. Otherwise, the number we found is either a prime number itself or divisible by another prime number other than 2, which is an odd number.

t = int(input())

for _ in range(t):
    n = int(input())
    while n > 1:
        n /= 2
    
    if n  == 1:
        print("NO")
    else:
        print("YES")
   

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

For each index $$$i∈[1,n]$$$ let's try to find which $$$d$$$ we should use in order to make $$$i-th$$$ element of $$$c$$$ equal to zero. If $$$a_i=0$$$, then $$$c_i=b_i$$$ no matter which $$$d$$$ we choose. So we should just ignore this index and add $$$1$$$ to the answer if $$$b_i=0$$$.

Otherwise, we should choose $$$d=−b_i/a_i$$$. Let's calculate the required fraction for each index, and among all fractions find one that fits most indices (this can be done, for example, by storing all fractions in a dictionary).

The only thing that's left to analyze is how to compare the fractions, because floating-point numbers may be not precise enough. Let's store each fraction as a pair of integers $$$(x,y)$$$, where $$$x$$$ is the numenator and $$$y$$$ is the denominator. We should normalize each fraction as follows: firstly, we reduce it by finding the greatest common divisor of $$$x$$$ and $$$y$$$, and then dividing both numbers by this divisor. Secondly, we should ensure that numenator is non-negative, and if numenator is zero, then denominator should also be non-negative (this can be achieved by multiplying both numbers by −1).

import sys
from collections import Counter
from math import gcd
n = int(sys.stdin.readline().strip())
a =list(map(int, sys.stdin.readline().strip().split()))
b =list(map(int, sys.stdin.readline().strip().split()))
count = Counter()
ans = 0
for i in range(n):
    if a[i] == 0:
        if b[i] == 0:
            ans += 1
    else:
        x = b[i] // (gcd(abs(a[i]), abs(b[i])))
        y = a[i] // (gcd(abs(a[i]), abs(b[i])))
        if b[i] < 0:
            x *=  -1
            y *= -1
        elif b[i] == 0 and a[i] < 0:
            y *=  -1
        count[(x, y)] += 1
if len(count) == 0:
    print(ans)
else:
    print(ans + max(count.values()))
    

When is the answer $$$-1$$$?

What Happens when if we want to change all elements to $$$x$$$ and:

1. If $$$a_i > k$$$ and $$$x \leq k$$$:

2. If $$$a_i < k$$$ and $$$x \geq k$$$:

3. If $$$a_i = k$$$ and $$$x \neq k$$$:

Imagine we want to transform every number on the blackboard into $$$x$$$. For each $$$a_i$$$, until $$$a_i$$$ becomes $$$x$$$, we will split $$$a_i$$$ into two parts: $$$a_i + k = x$$$ and $$$a_i + k - x$$$. In other words, $$$a_i = a_i + k - x$$$, and we add $$$x$$$ at the end of the blackboard. For subsequent operations, we focus only on $$$a_i$$$.

We can observe three cases:

1. If $$$a_i > k$$$ and $$$x \leq k$$$: $$$a_i + k - x < a_i$$$, so $$$a_i$$$ keeps increasing, making it unsolvable.
2. If $$$a_i < k$$$ and $$$x \geq k$$$: $$$a_i + k - x > a_i$$$, so $$$a_i$$$ keeps decreasing and won't reach $$$x$$$, also unsolvable.
3. If $$$a_i = k$$$ and $$$x \neq k$$$: if $$$x < k$$$, $$$a_i$$$ keeps increasing. And if $$$x > k$$$, $$$a_i$$$ keeps decreasing and won’t reach $$$x$$$, so it’s unsolvable.

Therefore, for all $$$i, 1 \leq i \leq n$$$ if $$$a_i = k$$$, $$$x$$$ should be $$$k$$$; if $$$a_i > k$$$, $$$x$$$ should be $$$> k$$$; if $$$a_i < k$$$, $$$x$$$ should be $$$< k$$$; otherwise, we won’t have an answer and print $$$-1$$$.

Now, to make the solution efficient, we aim to minimize the number of operations required.

You have to split each $$$a_i$$$ into $$$p_i$$$ pieces equal to $$$x$$$, and their sum must be equal to $$$a_i + k(p_i - 1) = a_i + k \cdot p_i - k $$$

$$$ a_i + k \cdot p_i - k = (a_i - k) + k \cdot p_i $$$

$$$(a_i - k) + k \cdot p_i = x \cdot p_i$$$.

Then, $$$(a_i - k) = (x - k) \cdot p_i$$$, so $$$x - k$$$ must be a divisor of every $$$ a_i - k$$$.

Since we want to minimize the number of operations (i.e., $$$p_i$$$), and since $$$p_i = (a_i - k) / (m - k)$$$, we want to make $$$m - k$$$ the largest number that divides all $$$a_i - k$$$.

import math, sys


def solve():
    n, k = map(int, sys.stdin.readline().strip().split())
    a = list(map(int, sys.stdin.readline().strip().split()))
    
    if a.count(a[0]) == n:
        return 0

    for x in a:
        if (x >= k and a[0] <= k) or (x <= k and a[0] >= k):
            return -1
    gcd = abs(k - a[0])
    for i in a:
   	gcd = math.gcd(gcd, abs(k - i))
    
    ans = 0
    for i in a:
   	ans += (abs(k - i) // gcd - 1)
    
    return ans

if __name__ == "__main__":
    t = int(sys.stdin.readline().strip())
    for _ in range(t):
   	print(solve())