Итак, начнём разбор.

219A - k-String

Давайте для каждой буквы l посчитаем, сколько раз она встретилась в строке --- массив c[l]. Подсчет осуществляется примерно так: c[s[i]]++. Если количество вхождений какой-то буквы не кратно k, то мы уже сразу понимаем, что составить нужную нам строку невозможно. Теперь построим строку p: добавим в неё букв 'a', букв 'b', и так далее. Выведем полученную строку k раз.

219B - Special Offer! Super Price 999 Bourles!

Переберем количество девяток на конце числа от 1 до 18. Пусть эта величина равна k. В таком случае максимальное число не превосходящее заданное p можно получить так:

• сотрем последние k цифр числа x:  = p / 10^k
• добавим справа k девяток y:  = x·10^k + 10^k - 1
• если значение y больше p, то уменьшим число x (то, что идет до k девяток) на 1 и к результату допишем k девяток y:  = (x - 1)·10^k + 10^k - 1

Если получившееся y >  = p - d, то обновим ответ значением k.

219C - Color Stripe

Разберём 2 два случая:

1. k равно 2. Тогда нам подходят только две строки — чередующиеся буквы 'A' и 'B'. Выбираем из них тот, который требует меньшего числа перекрасок.
2. k больше 2. Возьмем самый левый блок из одинаковых букв. Пусть его длина равна k, тогда надо не менее k / 2 перекрашиваний, чтобы избавиться от соседних одинаковых клеток в этом блоке. Если k нечетно, то можно каждую вторую клетку в блоке перекрасить в любой из цветов, отличных от цвета блока. Если k четно, то можно делать тоже самое, но аккуратнее выбрать цвет: он должен отличаться не только от цвета блока, но и от цвета следующей клетки за блоком. Это всегда возможно сделать, так как количество цветов больше 2.

219D - Choosing Capital for Treeland

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

В задаче были достаточно большие ограничения, поэтому нельзя было просто посчитать все эти значения n обходами в глубину. Авторское решение запускает только два обхода в глубину. Первым обходом в глубину посчитаем ответ для города номер 1. Заметим, что если посчитан ответ для вершины x, то ответ для вершины y, которая соединена с x, можно посчитать за O(1). А именно, ans(y) = ans(x) - direction(x, y) + (1 - direction(x, y)), где direction(x, y) — равно 1, если ребро (x, y) ориентировано не так как во входных данных, и равно 0, иначе.

Пользуясь описанным фактом, можно посчитать все значения ans(v) одним обходом, зная ans(1).

Итоговая ассимптотика решения O(n).

219E - Parking Lot

Будем поддерживать две структуры: множество отрезков свободных парковочных мест, в котором отрезки отсортированы по их началу, и множество отрезков свободных парковочных мест отсортированных по размеру. Такие структуры должны поддерживать операцию быстрого поиска первого больше либо равного элемента, удаление элемента и его вставку, нахождениe максимума и следующего по величине элемента.

В языке C++, авторское решение использовало set <pair<int,int>> и map <int, set<int>>. Set отрезков и Map из длины отрезка в набор отрезков с заданной длиной. Операция поиска больше либо равного элемента в этих структурах называется lower_bound.

Научимся поддерживать эти структуры от операции к операции. Для того, чтобы определить автомобилиста на стоянку, нужно взять свободный отрезок с максимальной длиной или с (максимальной длиной минус один), который не упирается в начало или конец стоянки, и попробовать определить автомобилиста на свободное парковочное место в середину этого отрезка (если точной середины нет, то в ближайшую к ней клетеку). Среди всех таких позиций нужно выбрать наилучшую (в смысле условия задачи). После нахождения лучшей позиции надо разрезать соотвествующий отрезок свободных позиций на два и обновить обе структуры (удалить старый отрезок и вставить два новых).

Чтобы удалить автомобилиста со стоянки нужно добавить новый отрезок свободных парковочных мест длины один в структуру. Предварительно нужно удалить смежные с этим отрезком отрезки в структуре. Соединить их с нашим отрезком и добавить один большой отрезок в структуру.

Отдельные случаи возникает при рассмотрении крайних отрезков.

Итоговая сложность решения O(m log n)