Обсуждение @ 2118. Шифровка 4 @ Timus Online Judge

Online Judge	Задачи	Авторы	Соревнования
О системе Часто задаваемые вопросы Новости сайта Форум Ссылки	Архив задач Отправить на проверку Состояние проверки Руководство	Регистрация Исправить данные Рейтинг авторов	Текущее соревнование Расписание Прошедшие соревнования Правила

вернуться в форум

Обсуждение задачи 2118. Шифровка 4

What is difficulty of correct solution?

Послано Zergatul 21 мар 2021 08:15

I have O(len(s) * k^2), and it is definitely too slow (TL#26).

BTW, and here is some tests (don't want to create separate topic):

3
CC
00
1
01
*****
ans=-1

3
BAB
10
111
0
*****
ans=7

3
BA
00
01
1
*****
ans=3

3
CA
001
000
01
*****
ans=5

Re: What is difficulty of correct solution?

Послано bsu.mmf.team 20 июн 2021 23:24

By applying suffix automaton, O(len(s) + k^2) complexity is received.