514A - Чубакка и число
Автор: Rebryk
Очевидно, что все цифры, которые больше 4, нужно инвертировать. Кроме цифры 9, если она первая цифра числа.
Асимптотика: 
514B - Хан Соло и лазерная пушка
Автор: Antoniuk
Переберем точки, в которых находятся солдаты. Если в данной точке солдаты еще не убиты, то сделаем выстрел и уничтожим всех солдатов, находящихся на прямой, проходящей через месторасположение пушки и данную точку.
Точки (x1, y1), (x2, y2), (x3, y3) лежат на одной прямой, если (x2 - x1)(y3 - y1) = (x3 - x1)(y2 - y1).
Асимптотика: 
514C - Уотто и механизм
Автор: Rebryk
При добавлении строки в множество, посчитаем от нее полиномиальный хэш и добавим его в массив. Затем этот массив отсортируем. Теперь для ответа на запрос будем пробовать менять каждый символ в строке и с помощью бинарного поиска проверять, встречается ли ее хеш в массиве (пересчитывая хэш за 
). Если хэш встречается, то ответ на запрос "YES", иначе "NO".
Асимптотика: 
, где L — суммарная длина всех строк.
514D - R2-D2 и армия дроидов
Автор: Rebryk
Чтобы уничтожить всех роботов на отрезке с l по r, нужно сделать 
выстрелов, где cnt[i][j] — кол-во деталей j-го типа у i-го дроида.
Будем поддерживать указатели на начало и конец отрезка, на котором хотим уничтожить всех дроидов. Пока мы можем уничтожить дроидов на текущем отрезке, будем увеличивать правую границу отрезка, иначе — левую, каждый раз обновляя ответ.
Чтобы эффективно находить максимум на отрезке, будем использовать очередь.
Асимптотика: 
514E - Дарт Вейдер и дерево
Автор: Antoniuk
Нетрудно понять, что 
, где dp[i] — кол-во вершин, которые находятся на расстоянии i от корня, а cnt[j] — кол-во детей, расстояние до которых j. Ответ 
.
Пусть состояние динамики
Построим матрицу перехода размера 101 × 101
Теперь, чтобы перейти к следующему состоянию, нужно A умножить на B. Следовательно, если мы рассмотрим матрицу C = A·Bx - 100, то ответ на задачу будет находиться в самой правой ячейке этой матрицы. Для x < 100 ответ будем находить динамикой, которая была изложена в начале.
Для нахождения Bk будем пользоваться бинарным возведением в степень.
Асимптотика: 
