Codeforces Round #316 Editorial
Difference between ru2 and ru3, changed 741 character(s)
<a href="http://codeforces.me/contest/570/problem/A" title="Codeforces Round 315 (Div. 2)">570А &mdash; Выборы </a>↵

**Реализация**↵

Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.↵

$
O(n * m)$↵

<a href="http://codeforces.me/contest/570/submission/12523729" title="Codeforces Round 315 (Div. 2)">Решение</a>


<a href="http://codeforces.me/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B &mdash; Простая игра   </a>↵

**Математика, разбор случаев**↵

Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором 
$|a – m| > 1$ так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m$m$. ↵

Таким образом, мы рассматриваем два варианта хода 
$a = c – 1$ и $a = c + 1$. Вероятность победы в первом случае $(c – 1) / n$, во втором $(n – c + 1) / n$. Выбираем наилучший вариант. Нужно помнить про случай $n = 1$.↵

$
O(1)$↵

<a href="http://codeforces.me/contest/570/submission/12523744" title="Codeforces Round 315 (Div. 2)">Решение</a>


<a href="http://codeforces.me/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Замены</a>↵

**Разбор случаев, (возможно) структуры**↵

Рассмотрим, как происходят замены. Если был отрезок из точек длины 
L$l$, то мы потратим L$l – 1$ операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков. ↵

После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков. ↵

Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать. ↵

$
O(n + m)$↵

<a href="http://codeforces.me/contest/570/submission/12523751" title="Codeforces Round 315 (Div. 2)">Решение</a>


<a href="http://codeforces.me/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D &mdash; Деревянные запросы</a>↵

**DFS, бинарный поиск**↵

Запишем вершины в порядке DFS от корня для вершин каждой глубины отдельно, храним время входа/выхода из вершины в DFS. Все вершины находящиеся в поддереве v, в такой  записи представляют отрезок. Теперь мы умеем получать все вершины в v на высоте h, в виде отрезка, делая два бинарных поиска. ↵

Палиндром можно составить, если количество нечетных вхождений каждой буквы меньше 2. Эту функцию можно посчитать для каждого префикса в обходе на каждой глубине отдельно. ↵

Для экономии памяти можно воспользоваться битовым сжатием, поняв, что нас интересует только четность и функция – это xor. ↵

$O(m * (log n + 26) + n)$ – времени $O(n * 26)$ &mdash; памяти, существует оффлайн решение за $O(m * 26 / 32 + n)$ и $O(n * 26 / 8)$ памяти↵

<a href="http://codeforces.me/contest/570/submission/12523757" title="Codeforces Round 315 (Div. 2)">Решение</a>↵

<a href="http://codeforces.me/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E &mdash; Свинка и палиндромы</a>↵

**ДП**↵

Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. ↵

Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. 
Если у первой клетки координаты $(x1; y1)$, у последней $(x2; y2)$, то $x1 + y1 = n + m - x2 - y2$.

Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя.↵
$O(n^3)$ – времени и $O(n^2)$ — памяти

<a href="http://codeforces.me/contest/570/submission/12523769" title="Codeforces Round 315 (Div. 2)">Решение</a>

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English josdas 2015-08-15 08:10:02 4 Tiny change: ' will be $(c-1)/n$ for fi' -> ' will be $c/n$ for fi'
ru4 Russian josdas 2015-08-15 08:08:58 6 Мелкая правка: 'м случае $(c – 1) / n$, во ' -
en3 English josdas 2015-08-14 09:39:01 91
en2 English josdas 2015-08-14 09:35:48 650 Tiny change: '(m * (log n + 26) + n' -
ru3 Russian josdas 2015-08-14 09:17:53 741 Мелкая правка: '(Div. 2)
en1 English josdas 2015-08-13 23:37:55 2851 Initial revision for English translation
ru2 Russian josdas 2015-08-13 22:14:27 14
ru1 Russian josdas 2015-08-13 22:12:07 3252 Первая редакция (опубликовано)