UPD1: Задача <<Строки Фибоначчи>>
Выпишем, рекурентность для ответа.
Здесь ans(k, si) — количетство вхождений строки si в строку fk, а cross(k, si) --- количество вхождений строки si в строку fk таких, что они пересекают разрез на стыке fk - 1 и fk - 2.
Понятно, что значение cross(k, si) зависит, только лишь от некоторого суффикса fk - 1 и некотрого префикса fk - 2. А именно, длина этих префиксов/суффиксов должна быть не менее длины si.
Если посмотреть на префиксы/суффиксы строк fi фиксированной длины L, то можно заметить, что начиная с некоторого момента префиксы начинают повторяться, а суффиксы чередоваться.
Этих фактов уже достаточно для решения задачи. Сгенерируем строку Фибоначчи fj, такую, что |fj| > |si|, а также строку fj + 1. Утверждается, что начиная со стороки fj + 2 префиксы стабилизируются, а суффиксы чередуются: суффикс fj, суффикс fj + 1, суффикс fj, и так далее. Это означает, что для всех k > j + 1 значения cross(k, si) также будет чередоваться.
Посчитаем два значения cross(j + 2, si) и cross(j + 3, si). Далее нужно вычислить рекурентность.
Чтобы сдать задачу на 30 баллов, было достаточно циклом посчитать рекуррентность.
Чтобы сдать задачу на 100 баллов, нужно быть воспользоваться возведением матрицы в степень, для быстрого подсчета рекуррентности.
Итак, второй дивизион ABBYY Cup 2.0 завершился!
Всем спасибо за участие! Хороших выходных :)
UPD: Друзья, а вот и долгожданный разбор!
Задача <<Хорошие элементы матрицы>>
Это была самая простая из задач, предложенных на ABBYY Cup’е. В ней просто требовалось посчитать сумму некоторых элементов матрицы. Ограничения позволяли использовать для хранения суммы обычные целочисленные типы для хранения суммы. Проверка принадлежности элемента к <<средней>> строке или <<среднему>> столбцу является тривиальнойым. Принадлежность элемента (i, j) матрицы к главной диагонали проверяется как i = j, а к побочной: i = n-j+1. Итоговая сложность решения составляет O(N2).
Задача “Прямоугольная игра”
Немного переформулируем исходную задачу: дано число N, и нужно найти цепочку с максимальной суммой. Цепочкой будем называть такую последовательность чисел, что:
- A1 = N, Ak = 1
- Ai делится нацело на Ai + 1 для i от 1 до k - 1
Для решения будем использовать жадный алгоритм. Мы знаем, что A1 = N. После этого выбираем максимально возможное подходящее значение для A2. Далее аналогично для A3 и так далее, пока не получим 1. Доказательство корректности данного подхода основано на единственности разложения любого числа на простые множители. Для эффективной реализации можно было факторизовать исходное число N. И потом просто каждый раз делить его на минимально возможный простой множитель. Итоговая сложность решения составляет .
Задача <<Вечеринка>>
Заметим, что если некоторый человек идет на вечеринку, то на нее также идут все люди, которые находятся с ним в одной связной компоненте по ребрам дружбы. Также отметим, что на вечеринке может присутствовать ровно одна такая связная компонента. Если же внутри некоторой связной <<дружной>> компоненты есть ребра антипатии, то такая компонента не может образовывать дружную вечеринку. Итого, решение следующее: выделяем все связные <<дружные>> компоненты. Выбираем из них максимальную и не содержащую ребер антипатии. Для выделения компонент связности можно было пользоваться поиском в ширину или поиском в глубину. Итоговая сложность решения составляет O(n + k + m). Возможен альтернативный вариант за O(n2), если использовать для хранения графа матрицу смежности.
Задача <<Шифрование сообщений>>
Заметим, что каждый элемент Ai модифицируется следующим образом: к нему прибавляются некоторые элементы B_i. Причем прибавляется некоторый интервал, то есть элементы Bi такие, что L(i)≤i≤R(i). Итак, мы свели задачу к двум подзадачам:
1. Определение значений L(i) и R(i) для некоторого индекса i. Приведем вариант формул для определения этих величин: R(i) = min(m, i) L(i) = max(1, i - (n - m)), где n – длина массива Ai, m – длина массива Bi, i от 1 до n.
2. Обоснование правильности этих формул оставляем читателю в качестве упражнения. Быстрый подсчет суммы элементов Bi в интервале от L(i) до R(i). Перед построением ответа вычислим следующую величину: S(i) = сумма элементов Bi от 1 до i. Пусть S(0) = 0. Тогда S(i) = S(i–1) + Bi. А сумма в интервале от L(i) до R(i) будет равна S(R(i)) - S(L(i) - 1). Итоговая сложность решения составляет O(n + m).
Разборы других задач давно готовы, но маркап сегодня не дает нормального превью формул :(
Надеюсь, MikeMirzayanov поможет!
А разбор будет?
Конечно, завтра-послезавтра выложим )
Нет! Нет! Нет! Нет! Мы хотим сегодня
Нет! Нет! Нет! Нет! Мы хотим прямо сейчас!
Ждём пользователя под ником PornTubeHeroes...
*RedTubeHeroes.
Понятно чем вы занимаетесь в свободное от информатики время
и чем же он занимается? что тут понятного?
Судя по негативному отношению к моему конкретизирующему посту не я один.