Блог пользователя sankear

Автор sankear, 11 лет назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

Автор sankear, 13 лет назад, По-русски

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


Вот краткий разбор тех задач, которые я прочитал на контесте:

Задача A
Думаю, что здесь ничего не надо разбирать, а просто аккуратно написать то, что от Вас требуют

Задача В
Разобьем слово из запроса на буквы - это будет первая доля графа, вторая доля - многогранники. Проведем ребро между вершиной первой доли и вершиной второй доли, если на многограннике есть соответствующая буква. Построим паросочетание. Если для каждой буквы нашлась пара, то увеличиваем ответ.

Задача С
Т. к. НОД(A, B, C) = НОД(НОД(A, B), C), то можно каждую строку матрицы разбить на sqrt(N) блоков и в каждом предпосчитать НОД. Теперь будем отвечать на запросы, проходясь по строкам матрицы честно, а столбцы обрабатывать группами.

Задача D
A - массив заданных чисел
Посчитаем две вспомогательные величины.
SUM1i - сумма чисел с A1 по Ai
SUM2i - сумма чисел Ai, Ai+2, Ai+4 и т.д.
Максимум в первой строке всегда будет A1, а максимум второй строки мы переберем. Понятно, что максимум второй строки можно разместить под A1 и ответ от это не ухудшится. Пусть мы сейчас смотрим на число Ai, тогда вверх точно должно пойти числа с A2 по Ai-1, т. к. мы планируем сделать Ai максимумом во второй строке. Значит мы "под" эти числа можем поставить числа с Ai+1 по A2 * (i - 1). Ответ от этого не ухудшится. Теперь надо оставшиеся числа разбить на пары. Максимальное число в паре поставим вверх, а минимальное - "под" максимальное. Тогда ответ для такой конфигурации будет (A1 + Ai) * (SUM1i - 1 - SUM11 + SUM22 * i - 1 + A1). Из всех конфигураций нужно взять минимум.

Задача Е
SUM - массив сумм префиксов.
Будем решать задачу динамикой. Di, j - максимальная сумма, которую мы можем получить, сделав не более i зачеркиваний и используя первые j чисел.
Di, j = max(Di, j - 1, Di - 1, j - k + SUMj - SUMj - k)

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор sankear, 13 лет назад, По-русски

Задача Е.


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


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

Обозначим s1, s2, ..., sn - набор данных строк, Len = |s1|.

Для начала, посчитаем вспомогательную функцию f. f1 = 0, fi = fi-1 + Len - Li-1, i, где Li-1, i - то же самое, что и ранее введенное L, только для строк si-1 и si

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

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

2) di = min(dj + fi - fj+1 + Len - Lj, i+1), где j = 1..(i-1) - это значит что мы строки с (j+1)-й по i-ю относим к одному набору, а строку (i+1) относим к другому набору, содержащему j-ю строку.

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

1) dn = Len + fn.

2) dn = min(di + fn - fi+1) для всех i = 1..(n-1).


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

Теперь будем хранить для каждой строки все ее префиксы и суффиксы. bi, j - суффикс длины i у строки sj. ci, j - префикс длины i строки sj.

Пусть мы сейчас хотим посчитать di. Пусть posj, z - число от 1 до (i-1) такое, что значение dpos[j, z] + fi - fpos[j, z]+1 минимально и строка spos[j, z] имеет суффикс длины j равный z. Переберем L. Тогда префикс (i+1)-й строки длины L равен cL, i+1. Значит, di = min(di, dpos[L, c[L, i+1]] + fi - fpos[L, c[L, i+1]]+1 + Len - L).

Как пересчитывать posj, z тоже понятно. Переберем все суффиксы строки si. posj, b[j, i] изменится только если di < dpos[j, b[j, i]] + fi + 1 - fpos[j, b[j, i]] + 1.

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится