Блог пользователя ruzana.miniakhmetova

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

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

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

ans(k, si) = ans(k - 1, si) + ans(k - 2, si) + cross(k, si)

Здесь 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)≤iR(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 поможет!

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

»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

А разбор будет?