Для каждого момента i времени запомним количество сообщений z[i], которое нужно отправить в момент времени i. Теперь пройдем по каждому моменту времени от 1 до 106, поддерживая текущий размер очереди sz. На каждой итерации попробуем уменьшить размер очереди на 1, то есть выполним sz = max(sz - 1, 0), затем прибавим сообщения, которые нужно отправить в эту секунду, то есть выполним sz = sz + z[i]. На каждом шаге будем обновлять максимальное значение очереди и текущее время, если sz > 0. После выполнения цикла, если в очереди остались неотправленные сообщения, то нужно еще раз обновить ответ.
В этой задаче нужно было посчитать степени каждой вершины и найти ответ. Замечу, поскольку n > = 4, m > = 3 и граф связный, то ответ однозначный.
1) все степени 2 и у двух вершин степень 1 — шина.
2) все степени 2 — кольцо
3) все степени 1 и у одной степень > 2 — звезда
4) иначе неизвестно
Задача решается перебором. Для начала переберем сколько цифр в каждом четверти мы возьмем, например AAA.B.CC.DDD. Теперь посчитаем количество символов в этой строке (AAABCCDDD) и переберем цифры на первой половине этой строки (поскольку строка должна быть палиндромом, то вторая половина однозначно восстанавливается). После этого проверим, что такой ip-адрес является корректным и содержит правильный набор цифр. Если ip-адрес удовлетворяет всем условиям задачи, то добавим его к ответу.
Ограничения в задаче были не слишком удачными и провоцировали писать решение за квадрат, мы постарались максимально не позволить таким решениям пройти.
У этой задачи много правильных решений. Изначально планировалось решение, которое предподсчитывает частичные dsu (структура данных disjoint set union) на префиксах и на суффиксах, то есть массивы ldsu[M][N] и rdsu[M][N]. После этого на запрос [lf ; rg] легко ответить за время O(N·A - 1), если объединить множества ldsu[lf - 1] и rdsu[rg + 1], где A - 1 -- обратная функция Аккермана (константа от dsu).
У этой задачи много правильных решений. Изначально предполагалось решение, использующие корневую эвристику. Разобьем все запросы на sqrt(m) блоков. Будем поддерживать текущий массив b в виде отрезков в массиве z, который хранит четверки (lf, rg, type, start), где lf, rg — отрезок индексов массива b, type — 0 или 1, означающее из какого массива взяты числа для этого отрезка, start — позиция начала этого отрезка в массиве типа type.
На запросы будем отвечать в тупую, то есть честно пересчитывать как изменится массив z от запроса копирования и отвечать на запросы значения в позициях. Однако, каждые sqrt(m) запросов будем сливать данные из массива z в массив b, для того чтобы сам массив z сильно не разрастался.
Есть простое решение с деревом отрезков, которое умеет делать покраску на отрезке. Пусть пришел запрос копирования [lf ; rg], , тогда покрасим отрезок запроса [lf ; rg] в цвет, равный номеру запросу. Все запросы будем сохранять. Пусть пришел запрос значения в позиции x, тогда найдем цвет в дереве в этой позиции. Если такого цвета нет, значит мы находимся в исходном массиве b (выведем b[x]), иначе посчитаем смещение dx от начала этого запроса до нашей позиции x и выведем a[x + dx].
В D можно поделить рёбра на P ~ 20 блоков, и для каждой пары (префикс, суффикс), состоящей из целого числа блоков, посчитать DSU. После этого получается что-то типа O(K * M * C) где C мелкая константа копирования массива.
Можно сделать сразу за N^2 если просто выбросить все ребра, которые не входят в остов в порядке инпута и в обратном инпуту порядке. Интереснее, есть ли решения быстрее.
Сорри, я имел ввиду O(K * M). У тебя выходит O(N * M) , вообще супер!
У меня выходит O(N^2*A^-1 + K). После того, как осталось 2N ребер, различных запросов не более, чем N^2.
Так запросов всего 2 * 104 что на порядок меньше N2. Можно каждый запрос втупую.
А можно ли Е решить декартовым деревом? Склеить 2 массива, а потом вырезать по 2 куска и 1 вставлять на место другого.
Да только нужно еще дерево сделать персистентным)))
И получить ТЛ 30 :)
Неужели там такая большая константа выходит? Я честно говоря был уверен что такое пройдёт, но подумал что это слишком на фоне остальных задач.
P.S. Почитал код, думаю на плюсах бы прошло.
На яве нужно довольно аккуратно написать, чтобы влезть в 2 секунды. У меня зашло только после того, как я убрал одну из оптимизаций.
Интересно, а что за "оптимизация"?
При копировании вершины не совсем понятно, что выставлять у неё в качестве приоритета: его нельзя просто копировать, и обычно помогает добавление небольшого случайного шума.
Вообще говоря, это должно получать TL. Персистентное декартово дерево нужно писать не с приоритетами, а со случайным выбором вершины в merge (в зависимости от размеров поддеревьев). Тогда приоритеты не нужны вообще, но приходится хранить и поддерживать размеры поддеревьев.
не мог бы ты объяснить почему будет ТЛ?
Если выставлять приоритет рандомом, то скоро начнёт нарушаться свойство декартового дерева. При merge это выльется в то, что корень будет выбираться равновероятно из двух вершин. И если сделать много merge подряд вида "большое дерево + вершина", то получится бамбук.
А если выставлять его рандомом от приоритета родителя до приоритетов детей, то через какое-то время все приоритеты станут одинаковыми и, опять же, получится декартовый бамбук.
Впрочем, возможность построить тест зависит от конкретной задачи. Например, в задаче memory (операции с массивом "сумма на отрезке" и "скопировать отрезок в другой, как memcpy") тест строился вообще на халяву — куча средних по размеру копирований.
На сколько я знаю хорошей практикой является вообще не хранить приоритет, т.к. он используется только в мердже, а выбирать какой узел будет новым корнем с вероятностью зависящей от размера поддеревьев.
Кстати меня это очень забавляет, особенно персистентное декартово дерево по неявному ключу, ведь в нём не хранится ни X ни У))
А можно ли избавиться от приоритетов в неперсистентном дереве таким же трюком или это будет плохо работать?
Можно. Неперсистентное дерево — частный случай персистентного, когда мы обращаемся только к последней версии.
Ага, выходит что персистентное декартово дерево не только не декартово (ни X, ни Y не хранятся), но и не дерево (ссылки на сыновей образуют ациклический ориентированный граф, а не дерево).
Персистентное недекартово недерево.
Я сдал персистентное дерево. Только в дорешку, потому что у меня тупая бага: при переполнении массива в середине сплита вызывался пересчет свободных клеток, но дерево было еще криво построено и по-этому дфс зацикливался...
Мне кажется не получится, так как такое решение использует квадрат памяти.
Памяти-то O(NlogN), но константа большая.
caustique ничего не говорил про персистентность)
Ну а если не делать персистентным, то решение вообще работать не будет. Разве что, если каждый раз создавать копию дерева, но тогда это будет работать еще хуже, чем тупой квадрат.
Предлагается не вырезать из массива А кусок, а делать его копию за log(n) с использованием трюков подобно тому как это делается в персистентном декартовом дереве. затем вырезать кусок из B и на его место поставить откопированый массив. при таком подходе можно даже достичь O(n) памяти. ну а время понятно N log N
Тогда чем это отличается от персистентного декартова дерева?
Памяти O(n). Не знаю в точности что ты подразумеваешь под своим "персистентным декартовым деревом" но показалось что у тебя время не N log N "но тогда это будет работать еще хуже, чем тупой квадрат." Полагаю ты и сам знаешь как сделать N log N, закончим дискуссию.
Господа, будьте добры объяснить почему так яростно заминусовали?
Задачу Е надо просто решать мапой.
Можете на словах объяснить свое решение, пожалуйста? Из кода ничего не понял:(
У меня кода было больше, но идея примерна такая же. В сете хранятся отрезки (L, R, startPosA) отрезки сортируются по R, L равно R — 1 предыдущего отрезка, так что её можно и не хранить в принципе. b[L] = a[startPosA], b[L + 1] = a[startPosA + 1], ... .При обработке запроса на интервале (L, R) нужно поудалять из сета все отрезки из этого интервала, крайние пересекающиеся с ним нужно уменьшить, чтобы пересечения небыло. Потом добавляем наш отрезок (L, R). Каждый раз мы увеличиваем число отрезков максимум на 2, поэтому несмотря на то что в какой-то момент мы сможем удалить из сета O(n) отрезков за одну операцию, всего будет O(n) обращений к сету.
Спасибо, понял, интересное решение — буду как-нибудь такую идею следующий раз использовать.
Только не понял маленькую деталь — почему количество отрезков увеличивается максимум на 2, а не на 1? Казалось бы, добавляем только отрезок [L, R] — остальные либо укорачиваем, либо удаляем.
Либо удаляем середину, и оставляем два края.
-1+2=1, то есть увеличение произошло всего на 1 отрезок
Был один отрезок [0..10]. Добавляем отрезок [4..6]. Получилось три отрезка: [0..4], [4..6], [6..10].
Спасибо за подробное объяснение, теперь понял:)
Хреново вы отловили решения за O(nm) в D. Вот зачем такие подгоны делать?
Проведи свой чемпионат и сделай лучше ;)
надеюсь неудачные ограничения в D не испортили идеи придуманных задач, спасибо Сергей)
Дэшка прикольная, хоть и не удалось мне ее сдать на контексте, отослав решение, как в разборе) А Е позволила познать новую идею) Спасибо
Мне уже интересно увидеть то решение в D, над которым авторы долго потели, но так и не заставили его залезть в ТЛ.
Ведь, на самом деле, там еще и с неплохим запасом проходит.
Ставь фильтр ТЛ по задаче Д и выбирай любое)
Вопрос в другом. В том, насколько сильно авторы пытались упихнуть тупизну в этой задаче. У меня возникло ощущение, что вообще не пытались.
Кстати было бы прикольно если бы можно было хакать чужие решения после раунда, конечно никуда это не учитывая. Потому что мне реально интересно пару тестов попробовать на чужих решениях. А на своем компе это уже будет не совсем адекватное сравнение с учетом таких зазоров.
можно еще в запуске. Правда там вроде ольшие тесты нельзя, но можно лечить генерацией внутри
А оказывается, что можно, сам недавно узнал — можно прикрепить код генератора теста.
Кто-то может мне обьяснить, почему у меня по Е SQRT-декомпозиция работает чуть ли не быстрее, чем у других RMQ?
У меня 0.218с; нормальные решения с RMQ укладываются в 0.2, но даже на С++ большая часть решений с какими-то более сложными, чем декомпозиция, структурами работает медленней.
У меня на запрос второго типа ответ за О(1), обработка запроса первого типа — 3*SQRT(N). Т.е. что-то около 1000 операций.
Более того, сабмит с размером блока 50 (что дает нам около 2000 операций на запрос) проходит за 0.265с.
Тесты весьма удачные, или декомпозиция действительно настолько быстро летает за счет простоты операций?
SQRT декомпозиция в кэш хорошо укладывается, от этого и все плюшки, насколько я знаю.
Может посоревнуемся, у кого получится более быстрое решение D, из тех что за квадрат и вообще не должны укладываться в 2 секунды?
Я пока что нашел решение NVAL — 3549348 за 1.437 с.
При этом передо мной система codeforces немного в долгу за не полученный из-за моего собственного фэйла красный, и поэтому на моих посылках идентичное решение (3549806, 3549809) отработало сначала за 1.281, а потом за 1.265.
Если отбросить немного бредовую идею с кармой из-за про**аного 31 места, то получаем другой вопрос — почему система codeforces один и тот же код тестирует с погрешностью в 0.17 секунд?
На фоне решений, которые прошли сегодня за 1.984 (или даже за 2.000 у кого-то? или нету таких?), это вызывает улыбку) А с учетом того, что некоторые просто переслали в архив свое решение с контеста, и оно получило АС за 1.984 или 2.000, при TL на контесте — широкую улыбку))))
По-моему в этом конкурсе у меня есть шансы. Мое решение уложилось в пол секунды. Я сам в шоке, я молился, чтобы оно влезло в две.
DSU это уже не то. Кошерный вариант — пускать DFS каждый раз.
Ну по этому поводу Михаил как-то рассказывал, что во время соревнований тестирование сразу двух решений может производиться на одном ядре. Из-за этого время оценивается немного неправильно, но если решение на каком-то тесте получает TL, то оно перетестируется на отдельном ядре.
Что, имхо, не идеально. Теоретически, если у меня в переборе стоит отсечение по времени, то я вместо TL и OK (на последующем перетестировании) могу получить WA, хотя "на самом деле" решение заходит.
BFS получается быстрее вроде — 3553590 за 1031 мс.
Правда почти идентичное решение 3553789 работает за 1609 мс — погрешность больше полсекунды, что многовато.
can someone translate 292-D in english
can someone translate tutorial of 292-D in english
English Translation-
The restrictions in the problem were not very successful and provoked a solution to be written in a square; we tried not to let such solutions pass as much as possible.
This task has many correct solutions. Initially, a solution was planned that calculates partial dsu (data structure disjoint set union) on prefixes and suffixes, that is, arrays ldsu [ M ] [ N ] and rdsu [ M ] [ N ] . After that, the request [ lf ; rg ] it is easy to answer in time O ( N · A - 1 ) if we combine the sets ldsu [ lf - 1] and rdsu [ rg + 1] , where A - 1 is the inverse Ackerman function (constant from dsu).
Thanks, it helped a lot
I didn't understand the 292E (copy data) solution. Can someone help me out.
u r gray why do you try to understand complex problems