Предлагаю обсуждать здесь задачи. Кто что делал в C? Кто-нибудь решал D? Мы нашли статью, там даже код есть, но скопипастить его к сожалению никакими способами не получилось, только кучу компо-времени убили :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Предлагаю обсуждать здесь задачи. Кто что делал в C? Кто-нибудь решал D? Мы нашли статью, там даже код есть, но скопипастить его к сожалению никакими способами не получилось, только кучу компо-времени убили :)
Название |
---|
Скопипастить? оО Честно говоря, я ожидал это от кого угодно, но не от Вас. Не могу сейчас найти ссылку, но раньше обсуждалось, что пользовать Интернетом и тем более копипастить код даже в Интернет-соревнованиях нельзя. Что с тех пор поменялось?
Правила opencup'а с тех пор поменялись, теперь prewritten code разрешён =)
(ну а про фразу в посте — это разумеется полу-шутка: просто C у нас писать никому не хотелось, и поэтому от нечего делать страдали фигнёй с извлечением текста из pdf)
Глупый вопрос, а нельзя было перепечатать? :)
1) Так не интересно, 2) А ты посмотри на объём кода там ;)
prewritten code разрешен, а пользование Интернетом-нет. И с вашей команды спрос гораздо больше должен быть за нарушение правил, вы ведь пишете не из сектора.
Я бы даже сказал,
Замечание про prewritten code относилось к вопросу про "копипастить". Пользование интернетом (по модулю коннекта к opencup.ru) конечно запрещено, мы кроме этого ещё используем skype/hangout/(изредка)rdesktop, когда пишем из >1 локации. Если используем что-то кроме этого, на ход контеста это не влияет (в обсуждаемом контексте — мы отлично понимали, что D сдавать не будем, спасибо "обнадёживающим" финальным стендингам первые 5 минут контеста; за неимением других дел в определённый моментэтим было просто интересно заняться). Можно конечно относиться ко всем правилам формально и старательно вырубать все источники инета включая мобильники, но зачем? Я не вижу катастрофы, если используется что угодно, включая интернет, при условии что это на контест не влияет.
Не, если вы уже точно решили, что больше не будете посылать на контесте ни одного сабмита, то нормально, конечно. Извини за наезд :)
Да не, мы ещё надеялись, что чего-нибудь сделаем. И пока Яша думал, как написать C пооптимальнее, я страдал фигнёй с распознаванием pdf'ки. Впрочем, я на тот момент уже точно понимал, что больше ничего на этом контесте не сделаю.
Ну интересен вот какой момент — а если бы в пдф-ке на первой странице было написано "задача тривиально сводится к макс потоку" (не применительно к этой конкретной задаче, конечно) — тогда получается тебе нужно не обсуждать эту задачу больше с сокомандниками :) Опасное дело.
Да, опасное. Но учитывая, что в финальных стендингах, которые зачем-то показывались на старте, по D было 0 сабмитов, вероятность такого к счастью исчезающе мала :)
Как решать F?
Это стандартный алгоритм на пересечение двух ДКА.
А где про него можно почитать не подскажете?
а как нибудь ещё можно? а то нам стыдно, что таких стандартных вещей не знаем
Да, конечно.
Построим новый граф, где вершина в нём будет парой вершин из старых двух -- первая из первого графа, вторая из второго, если буквы совпадают. Итого N^2 вершин и M^2 рёбер. Поймем, что если в таком графе есть цикл, то ответ -1. А в графе без циклов самый длинный путь мы можем найти топ. сортом + простой динамикой. Итого O(N2 + M2)
http://pastie.org/private/c8oy4xfclad8pd9cwhb7a
Все-таки НКА...
Да, согласен, конечно недетерминированных.
А кто нибудь сумел сдать K за N*log^2?
Да. Для каждой вершины будем хранить её двоичный подъем. Операции с деревом устроены так, что все двоичные подъемы всех вершин без проблем быстро пересчитываются. Чтобы узнать ответ на запрос, делаем бинпоиск (по ответу). Нас интересует, верно ли, что при подъеме на высоту K всех вершин каждая вершина-результат получилась из некоторых вершин вдоль одного пути. Как это проверять? Отсортируем все вершины по такому параметру: (вершина, где оказались в результате подъема; исходная глубина). Условие, что все вершины-результаты имеют нужный вид — при фиксированном первом параметре, когда глубина увеличивается, очередная вершина — потомок предыдущей. Все это легко делается при помощи двоичного подъема, в итоге N*log^2, проблем с TL-ем не было.
Мы всё это сдали на дорешивании в ptz... В С проходят set если писать на своих аллокаторах и подвешивать меньшее к большим.. я писал на сжатых кординатах map масок из-за которого получается nlog^2n/32 и делал все операции за размер меньшего. А в D сначала находим целочисленный поток минимальной стоимости в таком графе, а потом делаем разворот циклов где стоимость ребра наша извратская... я искал циклы минимального среднего веса и разворачивал их.
А можно подробнее про D? Вот нашёлся цикл. Насколько сильно его вычитать надо? Какой-то eps был? Или градиентный спуск?
пускай p_i это стоимотсти а f_i это поток который течёт. Тогда если добавить по этому цикл поток велечины c прирости получится таким Sum[p_i{f_i + c}^2] — Sum[p_i{f_i}^2] = 2сSum[p_if_i] + c^2Sum[p_i] ну это квадратичная функция минимум у неё в точке -Sum[p_if_i]/Sum[p_i], но надо ещё взять минимум по пропускным способностям ребёр. Можно ставить eps что если ответ мало меняется (1e-4), то можно успокоиться. Больше eps не нужны если искать цикл минимальноного среднего веса за O(VE), но я искал бинпоиском и поэтому ещё был eps в бинпоиске 1e-2.
Понятно... Там в output'е числа были с 10 знаками, что наводило на мысли о требуемой точности 10 - 10, так что надо было ещё догадаться, что на самом деле это не так :)
Да, но ответ надо было выводить только с 3 знаками)
Суммарный поток; а потоки по рёбрам — с 9 знаками. Ну да ладно, хорошая задача, в результате чтение статей и написание pipeline для OCR на bash — довольно неплохое времяпрепровождение.
Можно было все домножить на 1010 и решать в лонг лонгах.
А расскажите поподробнее про свой аллокатор. Что конкретно делаете и как это помогает?
В дорешивание сдали по C Nlog^2N/32 c нерекурсивным разбором. Реурсивный на контесте падал по стеку
Делаем так. Каждое множество — или множество или дополнение.
Тогда все операции выражаются либо как пересечение, либо как объединение, либо как разность множеств.
Все кроме объединения можно делать в тупую. Объединение надо делать объединяя меньший в больший. Это получился Nlog^2N.
Теперь надо поделить на 32. Для этого сжимаем координаты, и храним ненулевые маски в map
В дорешивание Петрозаводска сдал решение за n*log(n) — то, что, видимо, и рассказывалось на разборе. Построим дерево разбора, в вершине хранится бинарная операция (/значение, если лист) + есть ли отрицание. У нас все бинарные операции коммутативны, поэтому детей можно переставлять. Размер поддерева = сумма размеров множеств (по числу элементов) по листьям в этом поддереве. Сразу договоримся, что размер правого поддерева меньше размера левого, а исходные числа сжаты (различных чисел всяко меньше 5*10^6, хотя, конечно, гораздо меньше). Теперь самое интересное. Для каждой вершины результат вычислений честно будем хранить в некотором массиве, своем для каждой вершины. Причем мы будем заботиться только о том, чтобы ответ располагался компактно — все числа шли бы подряд в любом порядке. Вычисления в дереве производим в таком порядке: сначала вычисляем для правого поддерева, потом для левого. Есть три вида операций — (l/!l)&r, l|r, l&!r. В первом случае в качестве ответа будет массив для правого поддерева, только из него кое-что нужно выкинуть (при выкидывании образуется дырка, её нужно заполнить последним элементом). Честно пройдем по нему и выкинем (как проверять, есть ли элемент в l? об этом позже). Во втором случае ответом будет ответ для l, к которому что-то из r приписали — честно проходимся по r, если в l нет, дописываем в конец. В третьем случае проходимся по r и честно из l удаляем. Как же проверять, есть ли элемент в l и если есть, то на какой позиции? Очень просто, заведем глобальный массив, в котором для каждого числа будем хранить, есть ли оно в последнем ответе, и если есть, то на какой позиции (легко понять, как это дело пересчитывается — используйте счетчики). Почему же это работает: да просто когда мы хотим воспользоваться этими глобальными массивами, то последняя операция была с левым ребенком, и они там насчитался правильно. Почему nlog(n)? Потому что всегда меньшее к большему. Код: http://pastebin.com/TDyCrf2E
Рекурсивный разбор можно сдать, если при рекурсивном спуске внутрь скобок за один раз обработать все "лишние" скобки типа таких: ((( ... ))).
А как это делать? Мы на контесте за две минуты не придумали.
Для каждого символа сохраним rg[i]. Если i-й символ — это открывающаяся скобка, то rg[i] равен индексу соответствующей скобки, иначе -1.
Пусть мы пишем рекурсивный разбор с глобальным указателем. Глобальный указатель называется idx. Пусть символ s[idx] — открывающаяся скобка. Сохраним текущее значение idx в переменной old_idx. Заведем два указателя clf = idx, crg = rg[idx] и будем делать clf++, crg--, пока оба указывают на скобки.
Тогда сначала надо idx = clf, сделать рекурсивный вызов, а потом idx = rg[old_idx] + 1.
Ясно. Я бы еще добавил, что надо еще проверять, что скобки друг другу соответствуют, иначе на тесте вида ((((())(()))) случится ужас.
как решать В? Весь контест пытался придумать и так и не смог ничего путного сделать...
Понятно, что по всем стоящим рядом одинаковым буквам всё разбивается на независимые куски. Для каждого куска надо посчитать все возможные расстояния между парами разных букв. В голову сразу приходит 26 FFT, но к счастью всё гораздо проще :) Если немного подумать, то для куска длины l расстояния 1 ≤ i ≤ l не бывает только если i — какой-то из периодов куска. Считаем все периоды при помощи префикс-функции и решаем задачу.
А расскажите как решать А? (надеюсь там что-нибудь красивое)
Нужно разбить все состояния на пары соседних и каждым ходом переходить в другое состояние в той же паре. Если общее количество состояний чётное, то играть за Алису, иначе за Боба (тогда нужно разбить на пары все состояния, кроме начального). n = 1 — особый случай.
Не совсем так, в случае нечетного числа состояний все зависит от цвета старта в шахматной раскраске
Есть ли хороший конструктивный алгоритм построения паросочетания для случая, когда мы выбираем играть за Боба?
Я на контесте писал Куна с эвристиками, но интуиция подсказывает, что там вообще всё должно аналитически строиться.
Мы делали так. Построим в этом графе гамильтонов путь. Это легко делается рукурсивно, спускаясь по размерности. После этого бьем на пары вдоль этого пути. Пропустить на нем клетку — не проблема.
Мы делал так: давайте коробки, где изначально нечетное число шаров назовем плохими (у нас их четное число). Разобьем их на пары. Теперь будем искать пару данной коробке по следующему алгоритму:
Если есть хорошая коробка, в которой лежит не столько шариков, сколько изначально, то сходим в первую такую коробку. Если там меньше, чем изначально, то из нечетного сходим в -, из четного — в +. Если больше — наоборот.
Если есть плохая коробка, в которой количество шариков от изначального отличается хотя бы на 2, то возьмем самую первую такую и сходим так же, как в пункте 1.
Возьмем самую первую пару плохих коробок, в которой хотя бы одно количество отличается от изначального. Если нарисовать это дело на плоскости, у нас получится квадрат 3*3 без центра. Будем ходить по нему по часовой стрелке
Не, я тебе потом уже не рассказал, но 1 — не особый случай в итоге
Кстати да, разбиение на пары в случае n=1 тоже должно работать