A div2. Искомая строка — та, на которой звездочка встретилась ровно один раз, искомый столбец — тот, где звездочка встретилась только однажды. Перебрав все строки/столбцы и проверив количество звездочек в них, получаем ответ.

Авторы: MikeMirzayanov, Gerald .

B div2. Наивное решение за O(n³) (перебор всех троек с последующей проверкой) не укладывается по времени.

Заметим, что по двум точкам из тройки (скажем, это точки A и C) можно однозначно установить предполагаемое положение точки B. То есть достаточно перебора всех пар точек с последующий проверкой середины отрезка, их соединяющего.

Прибавим ко всем координатам точек 1000 (понятно, что ответ от этого не изменится) и отметим эти точки в двумерном массиве флагов размера 2001х2001. Теперь мы можем проверить есть ли в данной позиции точка или нет за O(1).

Объединим две последние идеи и получим верное решение за O(n²).

Авторы: MikeMirzayanov, Gerald

A div1. C div2. В данной задаче предполагалось жадное решение.

Зафиксируем две планеты: на планете i мы будем покупать товары, на планете j — продавать. Тогда прибыль с товара типа k будет равна b_jk-a_ik. Поскольку каждый товар занимает единицу места, нам выгоднее всего закупать для перепродажи товары в порядке уменьшения прибыли.

Отсюда сразу вытекает решение: перебираем все пары планет, для каждой пары сортируем товары в порядке уменьшения прибыли, после чего жадно закупаем самые прибыльные товары пока хватает места в трюме. Из всех пар планет выбираем ту, где суммарной получилось как можно больше.

Автор: Ripatti

B div1. D div2. Заметим, что операция split — это ничто иное, как циклических сдвигов строки. Мы можем переходить от любого циклического сдвига к любому другому кроме текущего.

Назовем циклический сдвиг хорошим, если он равен конечной строке. Все остальные сдвиги назовем плохими. Пусть у нас A хороших сдвигов и B плохих (проверить все сдвига на "хорошесть" можно в лоб за O(|w|²).

Обозначим за dpA[n] — количество способов получить хороший сдвиг за n split-ов, за dpB[n] — количество способов получить плохих сдвигов за n split-ов.

В начале либо dpA[0]=1, dpB[0]=0, либо dpA[0]=0, dpB[0]=1 в зависимости от того, хороший сдвиг начальной строка (= совпадает ли с конечной) или нет. Далее переходы легко выводятся:

dpA[n] = dpA[n-1] * (A-1) + dpB[n-1] * A

dpB[n] = dpA[n-1] * B + dpB[n-1] * (B-1)

Посчитаем все для n<=k, ответом будет dpA[k]. Итого решение за O(|w|² + k).

Также, в этой задаче есть решение за .

Автор: havaliza

C div1. E div2. У второго игрока есть довольно очевидная стратегия, позволяющая задержать фишку с начальными координатами (X, Y) в одной из 4х полуплоскостей — x ≤ X + 2, x ≥ X - 2, y ≤ Y + 2 и y ≥ Y - 2. Причем какая это будет плоскость — решать второму игроку.

Таким образом, если max(|x1 - x2|, |y1 - y2|) > 4, выигрывает второй игрок — он просто задерживает фишки в двух не пересекающихся полуплоскостях.

Оставшиеся случаи max(|x1 - x2|, |y1 - y2|) ≤ 4 предполагалось добивать перебором (возможно, с отсечениями). Понятно, что первому игроку ходить так, чтобы фишки "расходились" не выгодно, поэтому пространство перебора ограничивается квадратом 5 × 5. Если перебор не укладывается в 2 сек, можно сделать precalculation. Еще можно было написать дп на масках.

Кроме того, здесь можно было вывести формулу вручную. Однако тут много сложных для разбора случаев и легко ошибиться.

Автор: Ripatti

D div1. Заведем динамику dp[pre][len], в которой будем хранить наименьшую длину префикса гиперстроки, которая имеет с префиксом длины pre строки s наибольшую общую подпоследовательность длины len.

Тогда несложно получить формулы перехода:

dp[pre][len] = min(dp[pre - 1][len],  наименьшая позиция буквы s[pre] в t правее dp[pre - 1][len - 1]).

Чтобы получать значения второго значения внутри минимума в вышеупомянутой формуле за O(1), нужно завести еще несколько динамик:

dp1 — для каждой базовой строки, позиции в ней и буквы посчитать самую левую позицию данной буквы правее данной позиции;

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

Итого решение за .

Автор: havaliza.

E div1. Сначала попробуем решить такую задачу: в деревы вебрано k вершин, нужно найти сумму ребер "натянутого" на них поддерева за .

Упорядочим все k вершин в порядке обхода dfs — v₁, v₂, ... , v_k. Рассмотрим пути v1-v2, v2-v3, ... , v(k-1)-vk и vk-v1. Нетрудно заметить, что они покрывают нужное нам поддерево, причем каждое ребро покрыто ровно два раза. Теперь, чтобы найти сумму ребер надо просто посчитать сумму всех путей (при помощи LCA это можно сделать как раз за ), а потом просто поделить на 2.

Чтобы решить первоначальную задачу, нужно поддерживать множество активных вершин в упорядоченном состоянии (например, использую std::set) и сумму всех путей между последовательными вершинами. Теперь запросы на добавление и удаление вершин можно обработать за , после чего обновить текущую сумму пересчитав 3 пути — тоже за .

Итого имеем решение за .

Автор: Ripatti.