Привет! Около полугода назад я начал заниматься олимпиадным программированием серьезно, перейдя из математики, в этом сезоне уже начали бороться за победу в ДФО, но суть не об этом. Что на полуфинале, что на отборе Всесиба не смогли решить задачи на строки, которые немалая часть команд решает без проблем (задача H на полуфинале и задача A на отборе Всесиба). Придумать самостоятельно решение задач лучше чем за квадрат я не смог, но из разборов понял что используются для решения мапы или хэшмапы. Хочется попросить немного подробнее объяснить подобные задачи, если можно дать ссылку на теорию или главу книги где бы это обсуждалось, ну и ссылки на задачи кодфорсес на похожие темы. Заранее спасибо
Трудно понять что вы имеете в виду (самая типовая задача очевидно найти дублирующие строки за примерно O(N)). Однако я вижу что на популярном сайте даже целый раздельчик есть:
http://e-maxx.ru/algo/string_hashes
Вообще говоря, эти две задачи разные. Общего в них только наличие самого мэпа как такового, но используется он для принципиально разных хешей.
В А отбора всесиба был такой смысл хешей — проще посчитать хеш от строки и пихнуть его в меп, чтобы потом при сравнении они сравнивались за О(1), а не как строки за О(длина строки), + занимали меньше места. Т.е. смотря на текущую (под)строку посчитаем ее хеш, если нашли его в мепе, значит строка как бы уже встречалась. Но может и не эта строка, а строка с таким же хешем, но другая — этот случай называется коллизией.
В H в мепе хранилась маска четности для букв из префикса (от 0..52), что влезает в
long long
(там 64 бита). К строковым хешам это явление не относится, но хешмеп для более оптимального хранения тут пригодится.Помимо обычного мепа (например
std::map
и прочих основанных на сбалансированных бинарных деревьях) существует хеш-меп (или хеш-таблица). Делается так — берем массивhashtable
какого-то размераP
и считаем хеш сначала как угодно, а потом берем результат по модулюP
и пихаем или сам элемент, или его хеш вhashtable[hash(str) % P]
. Теперь, на запрос "есть ли строка в массиве" мы можем сказать, что ее точно нет, еслиhashtable[hash(str) % P].size() == 0
. Иначе, нам надо проверить, именно наша ли строка там есть — проходом или бинпоиском, если поддерживать его отсортированным. Понятно, что тут возможно куча эвристик и шаманств типа дополнительных хешей и т.д. Например, в отборовсесибской А я пропихнул решение с двумя разными хешами ) один был для хеш-таблицы, поменьше, а другой, большой, для хранения в хештаблице. Хешмап круто использовать, когда у вставляемых в мап элементов коллизии довольно редкие.Надеюсь, понятно объяснил ) + автор комментария выше кинул правильную ссылку на емакс, а его заминусовали О_о
Можешь вот эту задачу пропихнуть хеш-таблицей, точно разберешься)
Кажется, я начинаю кое-что понимать, спасибо большое:) Сегодня сяду разбираться, наверное, что-то да получится, по крайнем мере про задачу со Всесиба кажется уже все понял
Стал перерешивать задачу A с отбора Всесиба, получил TL14 с таким кодом: ~~~~~
~~~~~
http://pastebin.com/nCYDRv60 — код на pastebin Какие тут явные ошибки, какие недочеты можно исправить? Спасибо.
явный квадрат. во втором цикле вообще куб, поделённый на твой простой модуль
а конструктивной критики нет — сам писать пока не пытался
выкинь на pastebin, не понятно ничо в форматировании
вроде понял, что происходит: ты пихаешь сначала все хеши, что есть, а потом пытаешься их разобрать и посчитать ответ, поэтому может действительно выродиться в куб. Надо считать ответ так: берешь текущий хеш и смотришь на ячейку таблицы, если она не пустая, то ищешь в ней такой же элемент, и если находишь, то ничего не делаешь и ответ не меняешь. Если же не находишь, то теперь уже пихаешь в таблицу новый хеш и плюсуешь ответ.
edit: или не понял что ты делаешь...
Да, получается в начале я считаю хэши за квадрат. Потом считаю хэши для обратных строк, если нахожу пару одинаковых хэшей строк с непересекающимися индексами — обновляю ответ. Неужели можно считать хэши все подстрок быстрее чем за квадрат или же можно не считать многие из них?
В этой задаче ограничения на длину строк до 105, пихать квадрат — не лучшая идея.
Действительно, можно не считать многие из хешей. Как описано на емаксе, если посчитать хеши на всех префиксах строки, то после этого можно за O(1) получить хеш любой подстроки. Правда там не совсем очевидно описан один очень полезный трюк — если мы хотим сравнивать на равенство много подстрок фиксированной длины len, то есть смысл домножить хеш каждой подстроки [i..j] на pmaxn - i, чтобы равные подстроки имели равные хеши.
Конкретно в этой задаче помогает наблюдение, что если есть ответ длины len, то будет и ответ длины len - 1, т.е. можно сделать бинпоиск по ответу. Единственное что осталось — научиться проверять, существует ли ответ длины len. Ну а для этого можно просто выписать все подстроки такой длины, отсортировать их хеши и аккуратно проверить, есть ли совпадающие. O(nlog2n) хорошо укладывается в ограничения.
Ух ты, спасибо, от того, что недостаточно опыта не видел бинарный поиск в упор, даже когда мне внизу на него указали, думаю теперь-то я сдам задачу:)
Как уже сказали, тут плохая ассимптотика, уж я то знаю, в дорешке сдал за +75. Ну и на самом контесте пробовал не один раз. Мысль с хеш таблицей абсолютно верная, а вот остальное хромает. Попробуй как-нибудь (спойлер)