Реализация
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.
O(n * m)
Математика, разбор случаев
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором |a–m| > 1 так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m.
Таким образом, мы рассматриваем два варианта хода a = c–1 и a = c + 1. Вероятность победы в первом случае c / n, во втором (n–c + 1) / n. Выбираем наилучший вариант. Нужно помнить про случай n = 1.
O(1)
Разбор случаев, (возможно) структуры
Рассмотрим, как происходят замены. Если был отрезок из точек длины l, то мы потратим l–1 операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков.
После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков.
Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать.
O(n + m)
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) памяти
ДП
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме.
Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. Если у первой клетки координаты (x1;y1), у последней (x2;y2), то x1 + y1 = n + m - x2 - y2.
Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя. O(n3) – времени и O(n2) — памяти
