Добрый вечер!
Сегодня с 18:00 до 21:00 по Москве проходил 5-й раунд хорватских интернет-олимпиад сезона 2011/2012. Предлагается обсудить здесь задачи.
И сразу несколько вопросов к тем, кто писал:
1) Как решать 5-ю? Интересуют как идеи частичных решений, так и, разумеется, полного.
2) Как решать 6-ю на полный балл?
3) Как понимать "_warning: the `gets' function is dangerous and should not be used_"? Первый раз сталкиваюсь с подобным. По каким причинам функция gets() объявлена вне закона?
Ну вообще это стандартный warning для линуксового g++. gets небезопасный потому что может выйти за пределы строки и случится runtime error, а так как это C++, то может произойти все что угодно, вплоть до звонка вашей бабушке(с). В олимпиадных задачах сие не актуально, так как тесты обычно корректные. Видимо предлагается пользоваться fgets.
Ещё как актуально.
Можно ошибиться и завести массив char [] меньше, чем нужно.
Можно при тестировании ошибиться и ввести строку больше, чем указано в ограничениях.
В обоих случаях при использовании fgets баг найдётся вероятнее, быстрее и/или удобнее.
Неактуально, разве что если тестировать решения только посылкой в систему.
Ну завести массивы меньше чем надо — тут что так что с fgets начнет твориться какая-то чушь. Хотя помню что выход за границу массива который переписал его размер я когда-то очень долго искал.
Как минимум, когда пишешь fgets (s, ?, stdin), на месте ? ставится какая-то длина.
Либо это длина массива, тогда прочитается не вся строка и это можно будет понять по её длине.
Либо это константа, и тогда при мысли "какова же эта константа" и дальнейшем сравнении её с длиной массива при чтении кода есть дополнительные шансы понять, что размер массива неправильный.
На последнюю НМ хешами на 70 баллов сдал, только 2 теста не проходит. Думаю, можно как-то соптимизировать.
Додумал решение. Оказывается можно за N * logM * logM + M * M * logM с хешами.
Захешируем все префиксы всех строчек. Закинем хеши в мапы по их длине. Для каждого такого хеша в мапе будем хранить какому паттерну он принадлежит. Если он принадлежит нескольким паттернам — ничего страшного, нам нужен лишь один.
Далее для каждого паттерна I найдем какие другие паттерны J (нам нужны не сами индексы паттернов, а только их длины) являются его префиксом (паттерна I). Это можно сделать за M * M, т.к. все хеши мы сохранили.
Теперь будем идти по нашей строчке и поддерживать правый указатель, также как бы мы это делали с решением за N * M. Найдем бинпоиском самую длинную строчку, которую можно получить, стартуя с текущей позиции в строке, используя наши сохраненные хеши. Теперь, посмотрим на получившийся итоговый хеш и посмотрим какому паттерну он принадлежит. Пусть он принадлежит паттерну I, пусть длина найденной бинпоиском строки — L. В паттерне I мы сохранили длины других паттернов, которые являются его префиксом. Найдем бинпоиском наибольшую такую длину <= L. Если она нашлась, именно на это значение можно использовать, чтобы сдвинуть наш правый указатель.
Осталось только все это аккуратно реализовать и в теории это должно войти в TL. Но возможно есть решение проще, с более умными структурами данных.
На контесте я зачем-то хранил хеши от образцов одинаковой длины в векторах и запускал по каждому из этих векторов бинпоиск (соответственно, асимптотика была хуже N*M). В результате получил 0, т.к. в каждой группе было по несколько TL'ей.
Сейчас переписал на чистый N*M — получил полный балл. На одном из тестов, впрочем, моё решение работает 3.78, так что вряд ли рассчитывалось, что оно должно проходить.
6-я задача:
Ну очевидно что мы умеем это решать за O(n * m * log(n)). Для каждой позиции переберем все образцы, за O(1) проверяем что она подходит, за O(log n) красим отрезок. От логарифма можно разумеется избавиться(читаем комент ниже).
Сори, блед написал.
COCI!
6-я(дубль 2):
Построим на исходной строчке суф. дерево(можно суф. автомат, об этом ниже). Расмотрим все образцы, супстимся по суф. дереву. Мы остановились в какой-то вершины(если нет, спустимся по ребру до вершины). В поддереве вершины находятся все суффиксы, начала которых совпадают с нашим образцом. Запишем в эту вершину add = len(образца). Сделаем так для всех строчек. Теперь сделаем push из корня. Значение add в вершине = max(среди add на пути между корнем и этой вершины). Теперь в терминальных вершинах записано максимальная длина образца, который начинается в этом суффиксе. Теперь покрасим деревом отрезков(или немжожко магии, и за O(n)), получим ответ.
Все тоже самое можно делать суф. автоматом. Проблема возникает при push. Решение: запомним все вершины в которых остановились, отсортируем по значению add. Запускаем в невозрастающем порядке, помечаем вершины в которые мы зашли, больше в них не заходим. Нетрудо увидеть, что в терминальных вершинах опять запино максимальный образец.
5-ая задача сломала мне мозг. Но она классная =)
В 6-ой задаче такие большие TL и ML — наверное подразумевалось решение с Ахо-Корасик, то есть в вершине бора храним длину самой большой строчки, заканчивающейся здесь, и попав в вершину помечаем столько символов до текущей позиции как хорошие.
5-ю решал примерно так: понятно, что i-ый сверху прямоугольник сдвигает центр масс не более, чем на m / M, где m — его масса, M — суммарная масса верхних i прямоугольников. Посидев x минут с ручкой и блокнотом, можно доказать, что нам выгодно сдвигать центр масс каждый раз на максимальную величину и при этом до какого-то прямоугольника сдвигаться только вправо, а потом только влево. Ну теперь можно перебрать, после какого прямоугольника мы начинаем сдвигаться влево и выбрать лучший ответ. Если использовать частичные суммы, получится решение за O(n).