Вчера на сайте e-olimp.com закончилась Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского. Среди задач (преимущественно простых) попадались и сложные.
К примеру, задача, упомянутая мной две недели назад — Задача I. Мне удивительно то, что её решило народу гораздо больше, чем следующую за ней — на мой взгляд, гораздо более простую.
В связи с этим вопрос(ы) сообществу, особенно решившим эту задачу на контесте. Как можно решить эту задачу с более-менее доказанной сложностью, заходящей в таймлимит? Как люди, решившие её, её решали? Изменилось ли что-нибудь в решении бы, если бы строки состояли не полностью из цифр, а из произвольных символов?
Скорее всего не изменилось бы, впрочем, я могу и ошибаться. Авторское решение базируется на LCS и KMP. Планируется написание разборов по этим задачам, но немного попозже, так как через неделю III этап (областной) Всеукраинской олимпиады и первоочередные задачи стоят пока немного другие.
Пусть Si — это строка, полученная вставкой строки B после i-го символа строки A. Она однозначно задается числом i. Отсортируем массив чисел от 0 до
Unable to parse markup [type=CF_TEX]
при помощи специального компаратора, который будет сравнивать строки Si лексикографически, используя полиномиальные хеши. Время O(Nlog2N).Может быть я неудачно сгенирировал тесты, но изначально планировалось, что должны на 100% проходить только решения со сложностью O(N).
Не, я ее не сдавал, может оно и не проходит, если там много длинных тестов. Хотя, описанное мной решение можно достаточно просто ускорить до O(NlogN), если вместо хешей в компараторе использовать Z функцию. Оно, мне кажется, пройдет, поскольку sort в C++ достаточно оптимально написан.
А можно по подробнее, как хешами сравнивать строки лексикографически?
Сравнивать строки можно быстро, при условии что изначально мы для них предпосчитали хеши всех префиксов. Тогда бинарным поиском ищем LCP и результат — это сравнение символов, стоящих сразу после этого префикса.
А... так я тоже умею, я думал за О(1) как-нибудь можно.
Только не обязательно отсортировать, достаточно просто найти минимум за n сравнений. При желании можно даже строки сравнивать за O(1) если построить суфдерево и искать lca за O(1), вообще линейное решение будет :)
Точно, нам же не надо сортировать, надо просто минимум найти. Тогда можно при помощи Z функции за O(1) сравнивать.
Я что-то не очень понимаю, как тут поможет z-функция, можете подробней объяснить?
Видимо, я был не прав. Мне казалось, что если мы хотим сравнить 2 строки
Unable to parse markup [type=CF_TEX]
иUnable to parse markup [type=CF_TEX]
, то можно при помощи z-функции найти отличие в той части до B, потом в B (если раньше не было), а потом в последней части. Но здесь выходит так, что если строкаUnable to parse markup [type=CF_TEX]
и префикс соответствующей длины строки S2 совпадают, то дальше нам z-функция не поможет и нужна какая-то суффиксная структура данных.І у меня работает за O(n*n) в худшем случае. худший тест:
когда делал конкантенацию ТЛ, когла проверял без конкантенации A' + B + A'' — прошло за 1,39с