Codeforces Round #410 (Div. 2) Editorial

Правка en4, от I_Love_Tina, 2017-04-21 19:54:10

798A - Mike and palindrome

Let cnt be the number of such that si ≠ sn - 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 dpi, j the smallest number of operations for making the first i strings equal to string si moved j times.

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

The answer is min(dpn, 0, dpn, 1, ..., dpn, |sn| - 1).

The complexity is O(|S|3 × 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 ai and ai + 1, the new gcd d must satisfy d|ai - ai + 1 and d|ai + ai + 1 d|2ai and d|2ai + 1. Similarly, because d is the gcd of the new sequence, it must satisfy d|aj, 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 v1, v2, ... , vn of zero or one,in one move we can change numbers vi, vi + 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 s1, s2, ... , st,the answer is .

Complexity is .

798D - Mike and distribution

In the beginning, it's quite easy to notice that the condition "2·(ap1 + ... + apk) is greater than the sum of all elements in A" is equivalent to ap1 + ... + apk is greater than the sum of the remaining elements in A.

Now, let's store an array of indices C with Ci = i and then sort it in decreasing order according to array A, that is ACi ≥ ACi + 1.

The complexity is .

798E - Mike and code of a permutation

Let's consider ai = n + 1 instead of ai =  - 1. Let's also define the sequence b, bi = j such that aj = i or bi = 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 pa < pb. 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 pSi number i (in other words pSi = i).

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

The main problem is to extract j for a given i in a sub-quadratic time,the solution is segment tree and is based on the fact that each time we want to extract vertex j from all non-visited edges (1 ≤ j < ai,j ≠ i) with maximal bj,if bj < i then there aren't remaining edges.

Complexity and memory are and O(N).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en14 Английский I_Love_Tina 2017-04-24 21:33:41 4 Tiny change: 'he form $(b_i,i)$ if $b_' -> 'he form $(i,b_i)$ if $b_'
en13 Английский I_Love_Tina 2017-04-23 15:17:20 2 Tiny change: 'if $1 \le a_i \le n$,' -> 'if $1 \le b_i \le n$,'
en12 Английский I_Love_Tina 2017-04-23 14:06:34 2 Tiny change: 'that $p_a < p_b$. If ' -> 'that $p_a > p_b$. If '
en11 Английский I_Love_Tina 2017-04-23 14:01:11 4
en10 Английский I_Love_Tina 2017-04-22 22:38:16 3 Tiny change: 'city just for forget ab' -> 'city just to forget ab'
en9 Английский I_Love_Tina 2017-04-22 21:03:25 1201 Tiny change: 'number $i$ (in other words $p_{S_i} = i$). \n\nBut ho' -> 'number $i$.\n\nBut ho'
en8 Английский I_Love_Tina 2017-04-21 20:35:59 11 Tiny change: 'eck the solution.\n\nLet's' -> 'eck the source code.\n\nLet's'
en7 Английский I_Love_Tina 2017-04-21 20:29:31 0 (published)
en6 Английский I_Love_Tina 2017-04-21 20:27:20 1751
en5 Английский I_Love_Tina 2017-04-21 20:09:11 418 Tiny change: '\neq i$ an. \n\nThe ' -> '\neq i$ and $b_j > i$. \n\nThe '
en4 Английский I_Love_Tina 2017-04-21 19:54:10 1853 Tiny change: 'A_{C_{i+1}$.\n\n[pr' -> 'A_{C_{i+1}}$.\n\n[pr'
en3 Английский I_Love_Tina 2017-04-21 19:40:45 1358 Tiny change: 's,a_n) = 2, so the g' -> 's,a_n) = 2$, so the g'
en2 Английский I_Love_Tina 2017-04-21 18:56:53 1094 Tiny change: '[problem:7' -> '#### [problem:7'
en1 Английский I_Love_Tina 2017-04-21 18:46:00 54 Initial revision (saved to drafts)