1 2011-06-04 23:13:21 Отредактировано mansur115 (2011-06-05 13:09:43)
Re: Keven
Укажите ссылку на задачу из архива, так оно ее не отображает, если виртуальный контест не запущен.
Re: Keven
Бин поиском нахожу максимальную допустимую длину подстроки N^2logN после чего нахожу минимальную лексикографическую подстроку N^2 и получаю TL, есть алгоритм оптимальнее или у меня баг в реализации?
Re: Keven
Да ее вроде и за O(NlogN) решить можно, хотя тут и квадрата достаточно.
Сделаем бинпоиск по длине ответа. Теперь при фиксированной длине 2Х найдем все позиции начал К-четных строк такой длины. Понятно, что от цикличности можно избавиться просто записав исходную строку S как S+S. Рассмотрим подстроку из первых Х позиций. Найдем кол-во символов из первой половины, которые отличаются от второй половины. Теперь сдвинем эту строку на 1 вправо. Что мы получим?
Пусть были символы: 1234 5678, после сдвига станет 2345 6789. Как видно, символы 234 и 678 соответствуют друг другу как в изначальной строке, так и в сдвиге, значит нам нужно только удалить пару 1-5 и добавить 5-9, что делается за О(1). Таким образом, можно пройти по всей строке и за O(N) найти все позиции начал К-четных строк.
Теперь, когда мы знаем длину ответа, просто пройдем по всем позициям начала и выберем мин. лексикографическую строку за квадрат. Если сильно хочется O(NlogN), можно это суфф. массивом сделать.
Re: Keven
бин поиск нельзя использовать тут нету монотонности ответа, например тест
0
abcdabcde
есть ответ длины 8 но нету ответов меньших длин
решил задачу перебором длин
Re: Keven
Да, точно, тогда как раз выходит квадрат.