1 Отредактировано mansur115 (2011-06-05 13:09:43)

Тема: Keven

http://acm.sgu.ru/problem.php?contest=0&problem=337

2

Re: Keven

Укажите ссылку на задачу из архива, так оно ее не отображает, если виртуальный контест не запущен.

3

Re: Keven

Бин поиском нахожу максимальную допустимую длину подстроки N^2logN после чего нахожу минимальную лексикографическую подстроку N^2 и получаю TL, есть алгоритм оптимальнее или у меня баг в реализации?

4

Re: Keven

Да ее вроде и за O(NlogN) решить можно, хотя тут и квадрата достаточно.

Сделаем бинпоиск по длине ответа. Теперь при фиксированной длине 2Х найдем все позиции начал К-четных строк такой длины. Понятно, что от цикличности можно избавиться просто записав исходную строку S как S+S. Рассмотрим подстроку из первых Х позиций. Найдем кол-во символов из первой половины, которые отличаются от второй половины. Теперь сдвинем эту строку на 1 вправо. Что мы получим?

Пусть были символы: 1234 5678, после сдвига станет 2345 6789. Как видно, символы 234 и 678 соответствуют друг другу как в изначальной строке, так и в сдвиге, значит нам нужно только удалить пару 1-5 и добавить 5-9, что делается за О(1). Таким образом, можно пройти по всей строке и за O(N) найти все позиции начал К-четных строк.

Теперь, когда мы знаем длину ответа, просто пройдем по всем позициям начала и выберем мин. лексикографическую строку за квадрат. Если сильно хочется O(NlogN), можно это суфф. массивом сделать.

5

Re: Keven

бин поиск нельзя использовать тут нету монотонности ответа, например тест
0
abcdabcde
есть ответ длины 8 но нету ответов меньших длин
решил задачу перебором длин

6

Re: Keven

Да, точно, тогда как раз выходит квадрат.