798A - Mike and palindrome

Let cnt be the number of such that s_i ≠ s_{n - i + 1}.

If cnt ≥ 2 then the answer is NO since we must change more than 1 character.

If cnt = 1 then the answer is YES.

If cnt = 0 and n is odd answer is YES since we can change the character in the middle, otherwise if n is even the answer is NO because we must change at least one character.

Complexity is O(|s|).

798B - Mike and strings

First of all, you must notice that the operation of removing the first character and appending it to the left is equivalent to cyclically shifting the string one position to the left.

Let's denote by dp_i, j the smallest number of operations for making the first i strings equal to string s_i moved j times.

Let f(i, j) be the the string s_i moved j times,then .

The answer is min(dp_n, 0, dp_n, 1, ..., dp_{n, |sn| - 1}).

The complexity is O(|S|³ × n).

798C - Mike and gcd problem

First of all, the answer is always YES.

If then the answer is 0.

Now suppose that the gcd of the sequence is 1. After we perform one operation on a_i and a_i + 1, the new gcd d must satisfy d|a_i - a_i + 1 and d|a_i + a_i + 1 d|2a_i and d|2a_i + 1. Similarly, because d is the gcd of the new sequence, it must satisfy d|a_j, j ≠ i, i + 1.

Using the above observations we can conclude that , so the gcd of the sequence can become at most 2 times bigger after an operation. This means that in order to make the gcd of the sequence bigger than 1 we need to make all numbers even. Now the problem is reduced to the following problem:

Given a sequence v₁, v₂, ... , v_n of zero or one,in one move we can change numbers v_i, v_i + 1 with 2 numbers equal to . Find the minimal number of moves to make the whole sequence equal to 0.

It can be proved that it is optimal to solve the task for consecutive ones independently so we divide the array into the minimal number of subarrays full of ones, if their lengths are s₁, s₂, ... , s_t,the answer is .

Complexity is .