Codeforces Round #316 Editorial

Revision ru4, by josdas, 2015-08-15 08:08:58

570А — Выборы

Реализация

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

O(n * m)

Решение

570B — Простая игра

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

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

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

O(1)

Решение

570C — Замены

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

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

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

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

O(n + m)

Решение

570D — Деревянные запросы

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

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

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

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

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

Решение

570E — Свинка и палиндромы

ДП

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

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

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

Решение

Tags 316, editorial

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 Первая редакция (опубликовано)