Доброго времени суток! До онсайта осталось всего ничего, а я нигде не нашел расписания =( Хотелось бы уже понимать как будут дни устроены...

Сегодня завершился второй раунд. Предлагаю обсудить здесь задачи.

Задача Е.

Пусть у нас есть набор строк a₁, a₂, ..., a_k и нам известна сжатая строка S. a_k является суффиксом S. Мы хотим добавить строку a_k+1. Длины всех строк одинаковы, значит величина сжатия будет |S| + |a_k+1| - L. L - максимальная длина суффикса a_k, который является префиксом a_k+1.

Очевидно, что вся последовательность данных строк разобъется на блоки подряд идущих. Каждый нечетный блок будет принадлежать первому набору, каждый четный - второму.

Обозначим s₁, s₂, ..., s_n - набор данных строк, Len = |s₁|.

Для начала, посчитаем вспомогательную функцию f. f₁ = 0, f_i = f_i-1 + Len - L_{i-1, i}, где L_{i-1, i} - то же самое, что и ранее введенное L, только для строк s_i-1 и s_i

Теперь пусть d_i - минимальная сумма сжатых строк двух наборов, сделанных из первых (i+1) строк. Тогда:

1) d_i = 2 * Len + f_i - мы все строки относим к одному набору.

2) d_i = min(d_j + f_i - f_j+1 + Len - L_{j, i+1}), где j = 1..(i-1) - это значит что мы строки с (j+1)-й по i-ю относим к одному набору, а строку (i+1) относим к другому набору, содержащему j-ю строку.

Формула для d_n будет несколько иной:

1) d_n = Len + f_n.

2) d_n = min(d_i + f_n - f_i+1) для всех i = 1..(n-1).

Мы получили решение за O(n^2).

Теперь будем хранить для каждой строки все ее префиксы и суффиксы. b_{i, j} - суффикс длины i у строки s_j. c_{i, j} - префикс длины i строки s_j.

Пусть мы сейчас хотим посчитать d_i. Пусть pos_{j, z} - число от 1 до (i-1) такое, что значение d_{pos[j, z]} + f_i - f_{pos[j, z]+1} минимально и строка s_{pos[j, z]} имеет суффикс длины j равный z. Переберем L. Тогда префикс (i+1)-й строки длины L равен c_{L, i+1}. Значит, d_i = min(d_i, d_{pos[L, c[L, i+1]]} + f_i - f_{pos[L, c[L, i+1]]+1} + Len - L).

Как пересчитывать pos_{j, z} тоже понятно. Переберем все суффиксы строки s_i. pos_{j, b[j, i]} изменится только если d_i < d_{pos[j, b[j, i]]} + f_{i + 1} - f_{pos[j, b[j, i]] + 1}.

Получаем решение за O(n * Len) времени и O(Len * 2^Len) памяти. Можно использовать и O(n * Len) памяти, но с решением за O(n * Len * log(n)).

Вот и все. Не судите строго, это первый разбор в моей жизни. Буду рад ответить на Ваши вопросы.