Связь с Эйвой

Автор задачи: Даниил Орешников, разработчик: Константин Бац

Для решения первой подзадачи нужно было сделать несколько переборов. Переберем генетические коды первого и второго Аватаров для рекомбинации, сравним полученный код со всеми кодами в первом поколении. Все существует $$$n$$$ кодов, сравнение двух кодов происходит за $$$\mathcal{O}(n)$$$. Таким образом, сложность такого решения — $$$\mathcal{O}(n^4)$$$.

Во второй подзадаче в строке было не больше двух символов 'b', а все остальные символы были равны 'a'. Рассмотрим случаи:

Для решения третьей подзадачи нужно было немного оптимизировать решение первой подзадачи. Давайте предварительно сохраним unordered_set генетические коды в первом поколении, и чтобы проверить, встречался ли полученный код среди кодов в первом поколении, будем использовать не линейный поиск, а запросы к unordered_set. Время работы такого решения будет $$$\mathcal{O}(n^3)$$$.

Для решения предпоследней подзадачи заметим, что чтобы получить какую-то строку $$$q$$$, являющуюся циклическим сдвигом $$$s$$$, в ходе рекомбинации, надо взять два циклических сдвига, у первого из которых символы на нечетных позициях совпадают с символами на нечетных позициях $$$q$$$, а у второго — аналогично с четными позициями.

Посчитаем полиномиальные хеши отдельно на четных позициях строки $$$s$$$, отдельно на нечетных. Соберем хеши всех циклических сдвигов $$$s$$$ и положим их в unordered_set. Теперь, перебирая $$$i$$$ и $$$j$$$ для рекомбинации, будем вычислять соответствующие частичные хеши их четных/нечетных позиций и проверять, лежит ли их сумма в посчитанном множестве. Такое решение работает за $$$\mathcal{O}(n^2)$$$.

Полное решение требует обратного подхода. Заметим, что количество пар особей, дающих новый код, равно $$$n^2 - t$$$, где $$$t$$$ — количество пар особей, дающих код из первого поколения. То есть можно найти количество пар, дающих уже существующий код, а затем вычесть это число из общего количества пар.

Для каждого уникального циклического сдвига строки $$$s$$$ найдем количество способов его получить в ходе рекомбинации. Для этого, обратно предыдущему решению, заведем множество cnt, в котором для каждого хеша циклического сдвига четных/нечетных позиций $$$s$$$ будем хранить количество раз, которое он встречается. Количество способов получить $$$q$$$, некоторый циклический сдвиг $$$s$$$, в таком случае равно $$$\mathtt{cnt.count}(q_{\mathrm{even}}) \cdot \mathtt{cnt.count}(q_{\mathrm{odd}})$$$.

Авторам также известно альтернативное полное решение задачи, использующее префикс-функцию. Для него обратимся к ключевой идее, указанной в решении подзадачи 2.

  1. Количество уникальных циклических сдвигов $$$s$$$ равно ее периоду $$$p$$$.
  2. Количество способов получить строку $$$s$$$ в ходе рекомбинации равно произведению количества способов выбрать циклический сдвиг с теми же четными позициями и количества способов выбрать циклический сдвиг с теми же нечетными позициями:
    • количество способов перевести четные символы $$$s$$$ в четные сдвигом равно $$$m_{00} = \frac{n}{2 p_0}$$$, где $$$p_0$$$ — период строки $$$s_0$$$ из четных символов $$$s$$$;
    • количество способов перевести нечетные символы $$$s$$$ в нечетные, аналогично, равно $$$m_{11} = \frac{n}{2 p_1}$$$, где $$$p_1$$$ — период строки $$$s_1$$$ из нечетных символов $$$s$$$;
    • количество способов перевести четные в нечетные и наоборот, равно $$$0$$$, если $$$s_0$$$ и $$$s_1$$$ не являются циклическими сдвигами друг друга, и $$$m_{01} = m_{00} = m_{11}$$$ иначе.

Найти период строки можно с помощью префикс-функции ($$$p = n - \mathtt{pf}[n]$$$, если он является делителем $$$n$$$, иначе $$$p = n$$$). Аналогично, с помощью алгоритма Кнута-Морриса-Пратта можно проверить, является ли строка $$$s_1$$$ циклическим сдвигом $$$s_0$$$. В конце останется просто посчитать ответ как $$$$$$n^2 - (m_{00} + m_{01}) \cdot (m_{10} + m_{11}) \cdot p\text{.}$$$$$$