<a href="http://codeforces.net/contest/570/problem/A" title="Codeforces Round 315 (Div. 2)">570А — Выборы </a>↵
**Реализация**↵
↵
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.↵
O(n * m)↵
↵
<a href="http://codeforces.net/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Простая игра </a>↵
**Математика, разбор случаев**↵
↵
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором |a – m| > 1 так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m. ↵
↵
Таким образом, мы рассматриваем два варианта хода a = c – 1 и a = c + 1. Вероятность победы в первом случае (c – 1) / n, во втором (n – c + 1) / n. Выбираем наилучший вариант. Нужно помнить про случай n = 1.↵
O(1)↵
↵
<a href="http://codeforces.net/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Замены</a>↵
**Разбор случаев, (возможно) структуры**↵
↵
Рассмотрим, как происходят замены. Если был отрезок из точек длины L, то мы потратим L – 1 операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков. ↵
↵
После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков. ↵
↵
Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать. ↵
O(n + m)↵
↵
<a href="http://codeforces.net/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D — Деревянные запросы</a>↵
**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) памяти↵
↵
<a href="http://codeforces.net/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E — Свинка и палиндромы</a>↵
**ДП**↵
↵
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. ↵
↵
Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. ↵
↵
Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя.↵
O(n^3) – времени и O(n^2) — памятиElections </a>↵
↵
We need to determine choice for each city. Then sum it for each candidate and determine the winner.↵
↵
O(n * m)↵
↵
<a href="http://codeforces.net/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Simple Game </a>↵
↵
Lets find which variant is interesting. For Andrew is no need a variant wherein |a-m|>1 because we can increase probability of victory if we will be closer to m. Then we consider two variants,a=c-1 and a=c+1. Probability of victory will be (c-1)/n for first variant and (n-c+1)/n for second. ↵
↵
We need to choose better variant, also we must keep in mind case of n=1.↵
↵
O(1)↵
↵
<a href="http://codeforces.net/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Replacement</a>↵
↵
Lets find how replacements occur. If we have segment of points with length l,we need l-1 operations and stop replacements for this segment. If we sum lenghts of all segments and its quantity then answer will be = total length of segments — quantity of segments. After change of one symbol length changes by 1.↵
↵
Quantity of segments can be supported by array. Consider events of merging, dividing,creation and deletion of segments. For merging we need to find if both of neighbors(right and left) are points then merging occured and quantity of segments reduced by 1. Other cases can be cosidered similarly.↵
↵
O(n + m)↵
↵
<a href="http://codeforces.net/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D — Tree Requests</a>↵
↵
We need to write vertices in DFS order and store time of enter/exit of vertices in DFS. All vertices in subtree represent a segment. Now we can get all vertices in subtree v on height h as a segment, making two binary searches.↵
↵
We can make a palindrome if quantity of uneven entries of each letter is less than 2.↵
↵
This function can be counted for each prefix in bypass for each depth.↵
↵
For saving the memory bit compression can be used considering that we need only parity and function is xor.↵
↵
O(m * (log n + 26) + n)↵
↵
<a href="http://codeforces.net/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E — Pig and Palindromes</a>↵
↵
We need palindrome paths. Palindrome is word which reads the same backward or forward. We can use it. Count the dynamic from coordinates of 2 cells, first and latest in palindrome.↵
↵
From each state exists 4 transitions (combinations: first cell down/to the right and second cell up/to the left). We need only transitions on equal symbols for making a palindrome. Note that we need a pairs of cells on equal distance from start and end for each.↵
↵
For saving memory we need to store two latest layers. ↵
↵
O(n^3)-time and O(n^2)-memory
**Реализация**↵
↵
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.↵
O(n * m)↵
↵
<a href="http://codeforces.net/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Простая игра </a>↵
**Математика, разбор случаев**↵
↵
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором |a – m| > 1 так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m. ↵
↵
Таким образом, мы рассматриваем два варианта хода a = c – 1 и a = c + 1. Вероятность победы в первом случае (c – 1) / n, во втором (n – c + 1) / n. Выбираем наилучший вариант. Нужно помнить про случай n = 1.↵
O(1)↵
↵
<a href="http://codeforces.net/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Замены</a>↵
**Разбор случаев, (возможно) структуры**↵
↵
Рассмотрим, как происходят замены. Если был отрезок из точек длины L, то мы потратим L – 1 операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков. ↵
↵
После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков. ↵
↵
Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать. ↵
O(n + m)↵
↵
<a href="http://codeforces.net/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D — Деревянные запросы</a>↵
**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) памяти↵
↵
<a href="http://codeforces.net/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E — Свинка и палиндромы</a>↵
**ДП**↵
↵
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме. ↵
↵
Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. ↵
↵
Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя.↵
O(n^3) – времени и O(n^2) — памяти
↵
We need to determine choice for each city. Then sum it for each candidate and determine the winner.↵
↵
O(n * m)↵
↵
<a href="http://codeforces.net/contest/570/problem/B" title="Codeforces Round 315 (Div. 2)">570B — Simple Game </a>↵
↵
Lets find which variant is interesting. For Andrew is no need a variant wherein |a-m|>1 because we can increase probability of victory if we will be closer to m. Then we consider two variants,a=c-1 and a=c+1. Probability of victory will be (c-1)/n for first variant and (n-c+1)/n for second. ↵
↵
We need to choose better variant, also we must keep in mind case of n=1.↵
↵
O(1)↵
↵
<a href="http://codeforces.net/contest/570/problem/C" title="Codeforces Round 315 (Div. 2)">570C — Replacement</a>↵
↵
Lets find how replacements occur. If we have segment of points with length l,we need l-1 operations and stop replacements for this segment. If we sum lenghts of all segments and its quantity then answer will be = total length of segments — quantity of segments. After change of one symbol length changes by 1.↵
↵
Quantity of segments can be supported by array. Consider events of merging, dividing,creation and deletion of segments. For merging we need to find if both of neighbors(right and left) are points then merging occured and quantity of segments reduced by 1. Other cases can be cosidered similarly.↵
↵
O(n + m)↵
↵
<a href="http://codeforces.net/contest/570/problem/D" title="Codeforces Round 315 (Div. 2)">570D — Tree Requests</a>↵
↵
We need to write vertices in DFS order and store time of enter/exit of vertices in DFS. All vertices in subtree represent a segment. Now we can get all vertices in subtree v on height h as a segment, making two binary searches.↵
↵
We can make a palindrome if quantity of uneven entries of each letter is less than 2.↵
↵
This function can be counted for each prefix in bypass for each depth.↵
↵
For saving the memory bit compression can be used considering that we need only parity and function is xor.↵
↵
O(m * (log n + 26) + n)↵
↵
<a href="http://codeforces.net/contest/570/problem/E" title="Codeforces Round 315 (Div. 2)">570E — Pig and Palindromes</a>↵
↵
We need palindrome paths. Palindrome is word which reads the same backward or forward. We can use it. Count the dynamic from coordinates of 2 cells, first and latest in palindrome.↵
↵
From each state exists 4 transitions (combinations: first cell down/to the right and second cell up/to the left). We need only transitions on equal symbols for making a palindrome. Note that we need a pairs of cells on equal distance from start and end for each.↵
↵
For saving memory we need to store two latest layers. ↵
↵
O(n^3)-time and O(n^2)-memory
