UPD1: Задача <<Строки Фибоначчи>>

Выпишем, рекурентность для ответа.

Здесь ans(k, s_i) — количетство вхождений строки s_i в строку f_k, а cross(k, s_i) --- количество вхождений строки s_i в строку f_k таких, что они пересекают разрез на стыке f_k - 1 и f_k - 2.

Понятно, что значение cross(k, s_i) зависит, только лишь от некоторого суффикса f_k - 1 и некотрого префикса f_k - 2. А именно, длина этих префиксов/суффиксов должна быть не менее длины s_i.

Если посмотреть на префиксы/суффиксы строк f_i фиксированной длины L, то можно заметить, что начиная с некоторого момента префиксы начинают повторяться, а суффиксы чередоваться.

Этих фактов уже достаточно для решения задачи. Сгенерируем строку Фибоначчи f_j, такую, что |f_j| > |s_i|, а также строку f_j + 1. Утверждается, что начиная со стороки f_j + 2 префиксы стабилизируются, а суффиксы чередуются: суффикс f_j, суффикс f_j + 1, суффикс f_j, и так далее. Это означает, что для всех k > j + 1 значения cross(k, s_i) также будет чередоваться.

Посчитаем два значения cross(j + 2, s_i) и cross(j + 3, s_i). Далее нужно вычислить рекурентность.

Чтобы сдать задачу на 30 баллов, было достаточно циклом посчитать рекуррентность.

Чтобы сдать задачу на 100 баллов, нужно быть воспользоваться возведением матрицы в степень, для быстрого подсчета рекуррентности.

Итак, второй дивизион ABBYY Cup 2.0 завершился!

Всем спасибо за участие! Хороших выходных :)

UPD: Друзья, а вот и долгожданный разбор!

Задача <<Хорошие элементы матрицы>>

Это была самая простая из задач, предложенных на ABBYY Cup’е. В ней просто требовалось посчитать сумму некоторых элементов матрицы. Ограничения позволяли использовать для хранения суммы обычные целочисленные типы для хранения суммы. Проверка принадлежности элемента к <<средней>> строке или <<среднему>> столбцу является тривиальнойым. Принадлежность элемента (i, j) матрицы к главной диагонали проверяется как i = j, а к побочной: i = n-j+1. Итоговая сложность решения составляет O(N²).

Задача “Прямоугольная игра”

Немного переформулируем исходную задачу: дано число N, и нужно найти цепочку с максимальной суммой. Цепочкой будем называть такую последовательность чисел, что:

• A₁ = N, A_k = 1
• A_i делится нацело на A_i + 1 для i от 1 до k - 1

Для решения будем использовать жадный алгоритм. Мы знаем, что A₁ = N. После этого выбираем максимально возможное подходящее значение для A₂. Далее аналогично для A₃ и так далее, пока не получим 1. Доказательство корректности данного подхода основано на единственности разложения любого числа на простые множители. Для эффективной реализации можно было факторизовать исходное число N. И потом просто каждый раз делить его на минимально возможный простой множитель. Итоговая сложность решения составляет .

Задача <<Вечеринка>>

Заметим, что если некоторый человек идет на вечеринку, то на нее также идут все люди, которые находятся с ним в одной связной компоненте по ребрам дружбы. Также отметим, что на вечеринке может присутствовать ровно одна такая связная компонента. Если же внутри некоторой связной <<дружной>> компоненты есть ребра антипатии, то такая компонента не может образовывать дружную вечеринку. Итого, решение следующее: выделяем все связные <<дружные>> компоненты. Выбираем из них максимальную и не содержащую ребер антипатии. Для выделения компонент связности можно было пользоваться поиском в ширину или поиском в глубину. Итоговая сложность решения составляет O(n + k + m). Возможен альтернативный вариант за O(n²), если использовать для хранения графа матрицу смежности.

Задача <<Шифрование сообщений>>

Заметим, что каждый элемент A_i модифицируется следующим образом: к нему прибавляются некоторые элементы B_i. Причем прибавляется некоторый интервал, то есть элементы B_i такие, что L(i)≤i≤R(i). Итак, мы свели задачу к двум подзадачам:

1. Определение значений L(i) и R(i) для некоторого индекса i. Приведем вариант формул для определения этих величин: R(i) = min(m, i) L(i) = max(1, i - (n - m)), где n – длина массива A_i, m – длина массива B_i, i от 1 до n.

2. Обоснование правильности этих формул оставляем читателю в качестве упражнения. Быстрый подсчет суммы элементов B_i в интервале от L(i) до R(i). Перед построением ответа вычислим следующую величину: S(i) = сумма элементов Bi от 1 до i. Пусть S(0) = 0. Тогда S(i) = S(i–1) + B_i. А сумма в интервале от L(i) до R(i) будет равна S(R(i)) - S(L(i) - 1). Итоговая сложность решения составляет O(n + m).

Разборы других задач давно готовы, но маркап сегодня не дает нормального превью формул :(

Надеюсь, MikeMirzayanov поможет!