Codeforces Round #316 Editorial

Revision ru1, by josdas, 2015-08-13 22:12:07

570А — Выборы Реализация

Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя. O(n * m)

570B — Простая игра Математика, разбор случаев

Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором |a – m| > 1 так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m. Таким образом, мы рассматриваем два варианта хода a = c – 1 и a = c + 1. Вероятность победы в первом случае (c – 1) / n, во втором (n – c + 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 * (log n + 26) + n) – времени O(n * 26) — памяти, существует офлайн решение за O(m * 26 / 32 + n) и O(n * 26 / 8) памяти

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

Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя. O(n^3) – времени и O(n^2) — памяти

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