\begin{tutorial}{Шифровка}

\textbf{ Подгруппа 1 ($n \leq 10$). }

В этой подзадаче можно было перебрать все возможные варианты расшифровки (для каждой позиции выбрать, какую из двух букв мы возьмём), для каждого варианта определить его информативность и выбрать оптимальную расшифровку. Информативность строки можно найти, честно перебрав $d$ и проверив, верно ли, что $s$ представляет собой префикс длины $d$, повторённый $\frac{n}{d}$ раз. Такую проверку можно осуществить за $O(n)$, при этом проверять имеет смысл только те $d$, которые являются делителями $n$. Поскольку делителей $n$ не более чем $2 \sqrt{n}$, то нахождение информативности будет работать за $O(n \sqrt{n})$. Всего существует $2^n$ различных вариантов расшифровок, поэтому общая асимптотика алгоритма --- $O(2^n n \sqrt{n})$.

\textbf{ Подгруппа 2. } 

В этой подзадаче можно было заметить, что оптимальной будет расшифровка, содержащая только буквы \texttt{a} и \texttt{c}. Действительно, ведь при такой расшифровке буквы совпадают на всех парах позиций, на которых они вообще могли бы совпасть, поэтому информативность в таком случае будет минимально возможной. Построить требуемую расшифровку можно за $O(n)$.

\textbf{ Полное решение. }

Давайте, как в первой подзадаче, будем перебирать $d$ (делитель $n$) и проверять, можем ли мы получить строку с информативностью $d$. Для этого для каждого $1 \leq i \leq d$ надо проверить, что у позиций $i, i+d, i+2d, \dots$ существует общая буква. Для этого переберём букву на позиции $i$ и проверим, что на позициях $i+d, i+2d, \dots$ эта буква также присутствует. Для позиции $i$ проверку можно осуществить за $O\left(\frac{n}{d}\right)$, для всех $i$ это будет работать за $O(n)$. Суммарно по всем $d$ алгоритм будет работать за $O(n \sqrt{n})$.

\end{tutorial}
