Здравствуйте, столкнулся с такой задачей:

Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 1 запрос на 10 символов): найти max длину подстроки между (pointer, cur_pos) которая повторяет строку начинающуюся с (pointer).

Например, для строки (abcab[запрос префикса с 0, ответ длина 2, pos 3]cab[запрос префикса с 2, ответ длина 3, pos 5]). Т.е. для первого запроса ищем префикс abcab на участке bcab, находим ab; Для второго запроса ищем префикс cabcab на участке abcab, находим cab.

Сейчас решаю ее с помощью хешей, но не устраивает производительность, на больших данных слишком много cache misses.

Знает ли кто-то возможно ли решение быстрее? В теории суффиксное дерево позволяет искать max подстроку, но оно тоже кажется медленным, т.е. слишком большая константа в операциях поиска и построения + не совсем ясно как избавиться от вхождений до начала интервала поиска.

Хочется алгоритм с маленьким средним временем работы и маленьким расходом памяти, в целом, устроят примерные решения, когда находится не самый длинный префикс но близкий к нему.

Если кто-то может дать направление куда копать с такой задачей то буду очень признателен,

Update: о текущем решение, я поддерживаю hash_map[M=20] где ключ это подстрока а значение это позиция где мы последний раз видели подстроку такой длины. В итоге на каждый запрос я проверяю есть ли такая подстрока длины 1, если есть то проверяю 2 и т.д. до 20, после чего возвращаю ответ из самой длинной совпадающей. Сложность M*M в худшем. Когда приходит новый char я обновляю hash_map[1][new_char]=cur_pos, если в hash_map уже была позиция для [new_char] то я пропагандирую ее на длину 2 и так пока не получу уникальное место, тут тоже примерно M операция, в худшем случае M*M. В итоге имею не оптимальный ответ но как минимум длины 20 если такой существует.

Случайно наткнулся что одна моя посылка проходит по TL на одном компиляторе, но падает на другом. Т.к. в основном пользуюсь тут GCC (т.к. более версия со всякими auto и {} ), то интересна причина. На первый взгляд не увидел какую-то известную проблему. Посылки 1 2

Задача B Копия на pastebin

Кто-то знает, что студия оптимизирует лучше и как можно обойти проблему в gcc? Спасибо.

Вижу такую надпись, у всех подобная проблема? Можно ли с ней справиться самостоятельно?

Доброго времени суток, не нашел похожих тем, поэтому пишу сам,

суть в том, что при введении новой системы оценок задач, когда граница для задачи, которые решили многие опустилась с 500 до 250, ценность решения задачи по сравнению со взломом сильно пострадала.

Успешный взлом на любой стадии дает 100 баллов, а цена сданной задачи постоянно падает, в итоге чаще выгодней заняться взломами, чем дорешать еще одну после штрафных попыток за 75 баллов.

Я не знаю как разные люди относятся ко взломам, но при подготовке к АСМ ценность взлома больше решения, не кажется верной. Правила TopCoder в этом плане лучше.

Возможно, для взломов тоже нужна динамическая разбаловка?

Доброго времени суток, возникло желание иметь возможность скрывать решенные задачи из архива, возможно кто-то сталкивался с подобным желанием и сделал какой-нибудь плагин для этого или существует стандартные методы как это сделать? Спасибо.

Обычно узнавал об этом здесь, в этот раз вроде никто не отписался о начале квалификации, или мб я просмотрел.

Осталось 11 часов link

Do you know causes of such strange dreamoon_love_AA and how to get place without any submissions http://codeforces.net/contest/494/standings/participant/3602199#p3602199 ?

Update: Thank you very match, answer was gotten.

Здравствуйте, пусть дана задача нахождения наименьшего общега предка в дереве, допустим в оффлайне, тогда логично писать классический алгоритм Тарьяна. Вопрос как его можно модифицировать для работы на лесе, когда у некоторых вершин может не быть LCA.

Я вижу 2 варианта:

1) завести дополнительные непересекащиеся множества component[N], положить туда леса, перед выводом LCA проверять что они лежат в одном множестве find(component[a]) == find(component[b]), при этом трачу дополнительно N памяти, N времени и строчек 15 кода.

2) Сделать фиктивную вершину, провести из нее ребра во все корни деревьев в лесу. Тогда нужно найти корни, чаще всего опять для этого нужно N памяти, при этом легче ошибиться при построении и т.д. В итоге та же память, может быть только строчек будет 10, а не 15.

Есть ли более красивые варианты как модифицировать LCA, для работы на лесе?

Здравствуйте, 2 вопроса по архиву задач на этом портале (вкладка после тренировок),

во-первых, если я раньше сдавал эту задачу, в рамках какого-либо контеста, то можно ли как-то по-простому найти эти посылки, смотря задачу в архиве?

во-вторых, не могу найти многие задачи которые есть в других разделах, но в архиве их нет, по какому принципу они туда добавляются? Например задач с различных ACM-овских олимпиад там нет.