# 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*|).

Solution: Link

# 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*|^{3} × *n*).

Solution: Link

# 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*|2*a*_{i} and *d*|2*a*_{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*_{1}, *v*_{2}, ... , *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*_{1}, *s*_{2}, ... , *s*_{t},the answer is .

Complexity is .

Solution: Link

# 798D - Mike and distribution

In the beginning, it's quite easy to notice that the condition " 2·(*a*_{p1} + ... + *a*_{pk}) is greater than the sum of all elements in *A* " is equivalent to " *a*_{p1} + ... + *a*_{pk} is greater than the sum of the remaining elements in *A* ".

Now, let's store an array of indices *C* with *C*_{i} = *i* and then sort it in decreasing order according to array *A*, that is we must have *A*_{Ci} ≥ *A*_{Ci + 1}.

Our answer will always have size . First suppose that *N* is odd. Add the first index to our set, that is make *p*_{1} = *C*_{1}. Now, for the remaining elements, we will consider them consecutively in pairs. Suppose we are at the moment inspecting *A*_{C2k} and *A*_{C2k + 1}. If *B*_{C2k} ≥ *B*_{C2k + 1} we make *p*_{k + 1} = *C*_{2k}, else we make *p*_{k + 1} = *C*_{2k + 1}.

Why does this subset work? Well, it satisfies the condition for *B* because each time for consecutive non-intersecting pairs of elements we select the bigger one, and we also add *B*_{C1} to the set, so in the end the sum of the selected elements will be bigger than the sum of the remaining ones.

It also satisfies the condition for *A*, because *A*_{p1} is equal or greater than the complement element of *p*_{2} (that is — the index which we could've selected instead of *p*_{2} from the above procedure — if we selected *C*_{2k} then it would be *C*_{2k + 1} and vice-versa). Similarly *A*_{p2} is greater than the complement of *p*_{3} and so on. In the end we also add the last element from the last pair and this makes the sum of the chosen subset strictly bigger than the sum of the remaining elements.

The case when *N* is even can be done exactly the same as when *N* is odd, we just pick the last remaining index in the end.

The complexity is .

Solution: Link

# 798E - Mike and code of a permutation

Let's consider *a*_{i} = *n* + 1 instead of *a*_{i} = - 1. Let's also define the sequence *b*, where *b*_{i} = *j* such that *a*_{j} = *i* or *b*_{i} = *n* + 1 if there is no such *j*. Lets make a directed graph with vertices be the indices of the permutation *p* with edges of type (*a*, *b*) representing that *p*_{a} > *p*_{b}. If we topologically sort this graph then we can come up with a possible permutation: if *S* is the topologically sorted graph then we can assign to *p*_{Si} number *i*.

In this problem we will use this implementation of topological sort.

But how we can find the edges? First of all there are edges of the form (*i*, *b*_{i}) if *b*_{i} ≠ *n* + 1 .For a vertex *i* he visited all the unmarked vertices *j* (1 ≤ *j* < *a*_{i}, *j* ≠ *i*) and you know for sure that for all these *j*, *p*_{j} < *p*_{i}. But how we can check if *j* was already marked? The vertex *j* will become marked after turn of vertex *b*_{j} or will never become unmarked if *b*_{j} = *n* + 1. So there is a direct edge from *i* to *j* if *j* = *b*_{i} or 1 ≤ *j* < *a*_{i}, *j* ≠ *i* and *b*_{j} > *i*.

Suppose we already visited a set of vertices and for every visited vertex *node* we assigned to *b*_{node} value 0 (for simplicity just to forget about all visited vertices) and now we want to find quickly for a fixed vertex *i* an unvisited vertex *j* with condition that there is edge (*i*, *j*) or say it there isn't such *j*, if we can do that in subquadratic time then the task is solved. As stated above the first condition is *j* = *b*_{i} if 1 ≤ *b*_{i} ≤ *n*, this condition is easy to check. The second condition is 1 ≤ *j* < *a*_{i} and *b*_{j} > *i*, now consider vertices with indices from interval 1..*a*_{i} - 1 and take *j* with maximal *b*_{j}. If *b*_{j} > *i* we found edge (*i*, *j*) otherwise there are no remaining edges. We can find such vertex *j* using segment tree and updating values while we visit a new vertex. In total we will visit *n* vertices and query the segment tree at most 2 × (*n* - 1) times (*n* - 1 for every new vertex and *n* - 1 for finding that there aren't remaining edges).

Complexity and memory are and *O*(*N*).

Solution: Link