Codeforces Round #410 (Div. 2) Editorial

Правка en2, от I_Love_Tina, 2017-04-21 18:56:53

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

История

 
 
 
 
Правки
 
 
  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)