150E - Замерзаем красиво

Идея:

1. Сделаем бинарный поиск по ответу. Пусть мы хотим проверить существование пути с медианой Mid.

2. Если ребро  ≥ Mid положим его вес равным  + 1, иначе  - 1. Теперь надо проверить существование пути не отрицательного веса, у которго длина  ≥ l и  ≤ r. Назовем такой путь хорошим.

3. Подвесим дерево за какую-то вершину V.

4. Сначала предположим, что путь проходит через V. Затем удалим эту вершину и сведем задачу к нескольким меньшим.

5. Если в качестве вершины V выбирать центр дерева (такую вершину, что после подвешивания за нее, размер всех поддеревьев не превохсодит половины размера всего дерева), то таких шагов будет не более Log(N).

6. Т.е если мы сейчас научимся за O(F(N)) проверять наличие хорошего пути, то мырешим задачу за сложность O(F(N) * log²(N)).

7. Для начала научимся ее решать за O(NLog(N)). Для каждой вершины посчитаем ее глубину, стоимость пути от нее до корня, и первое ребро на пути от корня до нее. Вершины будем обрабатывать пачками, в одну пачку попадают вершины с одинаковым первым ребром. Это сделано чтобы все учтенные пути были простыми. Сначала для каждой вершины из пачки вычислим максимальную стоимость хорошего пути, начинающегося в ней, проходящего через корень, и заканчивающегося в вершине из уже обработанной пачки. В силу того, что мы обрабатываем вершины пачками, условие прохождения через корень выполнится автоматически. Построим дерево отрезков на массиве q[x] =  максимальная стоимость пути длиной x начинающегося в корне. Тогда для нашей вершины искомая величина это просто максимум на отрезке с L - dep по R - dep. Затем после обработки всей пачки сделаем апдейты в дереве интервалов.

8. Чтобы получить АС нужно было очень аккуратно написать это решение (его сложность O(N * log³(N)) ~ 8 * 10⁸ операций или заметить, что можно заменить дерево отрезков очередью с максимумом.

150D - Миссия непроходима

Правильное решение — динамика. Для удобства будем вычислять три динамики, каждая зависит от обеих других. Обратите внимание, что не смотря на это динамика — ациклическая.

Состояния:

Best[l][r] — лучший результат который можно получить на подстроке с l по r.

Full[l][r] — лучший результат который можно получить на подстроке с l по r, при этом удалив ее полностью.

T[l][r][Len] — лучший результат который можно получить на подстроке с l по r, чтобы в результате получился палиндром длины ровно Len и больше ничего.

Переходы:

1. Full[l][r]. Давайте посмотрим какой ход мы сделаем последним. Это будет удаление палиндрома какой-то длины len, причем c[len] ≥ 0. Какой результат мы в итоге получим? c[len] + T[l][r][len], где T[l][r][len] — это оптимальный способ оставить на отрезке только палиндром длины len.

2. Best[l][r]. Либо мы удалим отрезок целиком, либо существует буква, которую мы не трогали. Но тогда каждый удаляемый палиндром лежит либо строго слева либо строго справа от этой буквы. Другими словами можно решать задачу независимо для левой половины и правой. Получаем что либо Best[l][r] = Full[l][r] либо Best[l][r] = Best[l][m] + Best[m + 1][r] для какого-то m, l ≤ m < r.

3. T[l][r][len]. len = 0, len = 1 — два частных случая, которые надо рассмотреть отдельно. В общем же случае давайте посмотрим на самую левую букву. Она либо войдет в оставшийся в результате палиндром либо нет. Если нет, то переберем позицию m (l < m ≤ r) самой левой буквы которая войдет в ответ. Все что находится слева от нее необходимо полностью удалить, из оставшейся строки все еще нужно оставить палиндром длины len. Получили Full[l][m - 1] + T[m][r][len] (for l < m ≤ r). Аналогично для самой правой буквы. Если она не войдет в ответ, то мы целиком удалим какой-то суффикс нашего отрезка. Получаем T[l][m][len] + Full[m + 1][r] (for l ≤ m < r). Остался последний вариант: и самая левая и самая правая буквы войдут в ответ, но тогда они обязаны совпасть. Значит в случае когда s[l] = s[r] мы можем их обе оставить и набрать оптимально палиндром на 2 символа короче на отрезке с l + 1 по r - 1. Получаем последний переход T[l + 1][r - 1][len - 2] (if s[l] =  = s[r]).

150C - Хитрый жук

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

2. Для каждого маленького отрезка пути (перегон между соседними станциями) посчитаем матожидание заработка если мы не продадим билет на него.

3. Теперь, когда нам нужно решить задачу для пассажира едущего с L до R, на самом деле надо найти под отрезок с максимальной суммой.

4. Это можно сделать например при помощи дерева интервалов. Каждая вершина дерева покрывает какой-то отрезок массива с l по r. Будем в ней хранить следующие величины: префикс с максимальной суммой, суффикс с максимальной суммой, сумму на всем отрезке и просто лучший результат. Для отрезка длины 1 все эти величины вычисляются очевидным образом. И в то же время, зная все эти величины для обоих сыновей вершины, мы с легкостью можем пересчитать значения в нашей.

150B - Количество строк

У задачи есть два принципиально разных решения:

1. Построить граф, где ребра это позиции в строке, а ребро означает равенство символов. Тогда на позициях, оказавшихся в одной компоненте связности, должны стоять одинаковые буквы. Пусть e — количество компонент связности, тогда ответ в точности равен m^e.

2. Разобрать четыре случая:

   • k = 1 или к > n ответ mⁿ.
   • k = n ответ m^{(n + 1) / 2}.
   • k mod 2 = 1 ответ любая строка вида abababab..., т.е. ответ m².
   • k mod 2 = 0 все символы в строке совпадают, т.е. ответ m.

150A - Победи или замерзни

• Если Q — простое или Q = 1 то первый игрок уже выиграл.

• Проигрышные позиции: p * q и p², где p и q — простые.

• Вполне очевидно, что из всех остальных позиций мы можем сделать ход в одну из проигрышных. Значит они выигрышные.

Остается лишь аккуратно проверить, что у нашего числа есть делитель удовлетворяющий условию проигрышности. Это можно сделать за O(sqrt(Q)) факторизовав наше число.

151B - Телефонные номера

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

151A - Газировкопитие

Газировки хватит на gas = (K * L) / (N * l) тостов.

Лаймов хватит на laim = (C * D) / N тостов.

Соли хватит на sol = P / (p * N) тостов.

Итого ответ: res = min(gas, laim, sol).