Here is the link to the contest.
A. Longest Non-Palindromic Subsequence
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)
B. Seeking the Odd
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")
C. Casino
If you use LCM function on all numbers, you might get TLE (as the number might get big).
Any positive integer number can be factorized and written as $$$2^a·3^b·5^c·7^d·...$$$
We can multiply given numbers by $$$2$$$ and $$$3$$$ so we can increase $$$a$$$ and $$$b$$$ for them. So we can make all $$$a$$$ and $$$b$$$ equal by increasing them to the same big value (e.g. $$$100$$$). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal.
Alternative solution is to calculate GCD of given numbers. Answer is "YES" if and only if we can get each number by multiplying GCD by $$$2$$$ and $$$3$$$. Otherwise, some number had different power of prime number other than $$$2$$$ and $$$3$$$.
from sys import stdin
def input(): return stdin.readline().strip()
N = int(input())
a = list(map(int, input().split()))
for i in range(N):
while a[i]%2 == 0:
a[i] //= 2
while a[i]%3 == 0:
a[i] //= 3
for i in range(1, N):
if a[i] != a[0]:
print("No")
exit()
print("Yes")
D. Maximum Number of Zeroes
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()))
E. Numbers on the Blackboard
When is the answer $$$-1$$$?
What Happens when if we want to change all elements to $$$x$$$ and:
If $$$a_i > k$$$ and $$$x \leq k$$$:
If $$$a_i < k$$$ and $$$x \geq k$$$:
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:
- If $$$a_i > k$$$ and $$$x \leq k$$$: $$$a_i + k - x > a_i$$$, so $$$a_i$$$ keeps increasing, making it unsolvable.
- 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.
- 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) / (x - k)$$$, we want to make $$$x - 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())