Есть ли более быстрое решение проблемы Google Code Jam Great Wall?

Рассмотрим следующий вопрос Google Code Jam в 1С :

Великая китайская стена начинается бесконечной линией, где высота во всех местах равна .$0$

Некоторое количество племен , , будет атаковать стену в соответствии со следующими параметрами - начальный день, , начальная сила , начальная западная координата и начальная восточная координата , Это первое нападение происходит на день , на интервале , по прочности . Если в пределах есть какая-либо часть Великой стены , высота которой , атака будет успешной, и в конце дня стена будет построена так, что любой ее сегмент в пределах$N$$N \le 1000$$D$$S$$W$$E$$D$$[W,E]$$S$$[W,E]$$< S$$[W,E]$ высоты $< S$тогда будет на высоте (или больше, если какая-то другая атака в тот день поразит тот же сегмент с силой S ′ > S )$S$$S' > S$

Каждое племя выполнит до атак перед отступлением, и каждая атака будет определяться итеративно по сравнению с предыдущей . Каждое племя имеет несколько δ D , δ X и δ S, которые определяют их последовательность атак: они будут ожидать δ D ≥ 1 дня между атаками, они будут перемещать свой диапазон атаки δ X единиц для каждой атаки (отрицательный = запад, положительный = восток), хотя размер диапазона останется прежним, и их сила также будет увеличиваться / уменьшаться на постоянное значение после каждой атаки.$1000$$\delta_D$$\delta_X$$\delta_S$$\delta_D \ge 1$$\delta_X$

Цель этой проблемы, учитывая полное описание атакующих племен, определить, сколько их атак будет успешным.

Мне удалось зашифровать решение, которое работает и работает примерно за 20 секунд: я полагаю, что реализованное мною решение занимает время , где A = общее количество атак в симуляции (макс. 1000000 ), а X = общее количество уникальных краевых точек на диапазонах атаки (макс. 2000000 ).$O(A\log A + (A+X)\log X)$$A =$$1000000$$X =$$2000000$

На высоком уровне мое решение:

• Читает во всей информации племени
• Вычисляет все уникальные координаты для дальности атаки - O ( A $X$$O(A)$
• Представляет стену в виде лениво обновленного двоичного дерева в диапазонах которое отслеживает минимальные значения высоты. Лист - это промежуток двух X- координат, между которыми ничего нет, и все родительские узлы представляют непрерывный интервал, охватываемый их дочерними элементами . - O ( X log X $X$$X$$O(X \log X)$
• Формирует все атаки каждое племя будет выполнять, и сортирует их в день - $O(A \log A)$
• Для каждой атаки посмотрите, будет ли она успешной ( время запроса). Когда день изменится, пройдитесь по всем необработанным успешным атакам и обновите стену соответствующим образом ( log X время обновления для каждой атаки). - O ( A log X $\log X$$\log X$$O(A\log X)$

Мой вопрос заключается в следующем: есть ли способ сделать лучше, чем ? Возможно, есть какой-то стратегический способ воспользоваться линейным характером последовательных атак племен? 20 секунд кажется слишком долгим для предполагаемого решения (хотя в этом может быть виновата Java).$O(A\log A + (A+X)\log X)$

Очевидная возможность для улучшения заключается в следующем:

Формирует все атаки каждое племя будет выполнять, и сортирует их в день - $O(A\log A)$

Мы знаем, что племена будут атаковать с определенного дня, через равные промежутки времени. Это означает, что мы должны объединить множество предварительно отсортированных списков. Также постановка задачи говорит нам, что никогда не будет более 1000 племен (т.е. 1000 списков для объединения); крошечное число по сравнению с 1 000 000 максимальных атак! В зависимости от относительной синхронизации вашей реализации переключение может сократить время обработки вдвое.

Это действительно все, что я могу предложить для оптимизации теоретической сложности, но у меня нет доказательств того, что она будет оптимальной после этого изменения.

Я сам решил загадку, но использовал более тупое представление стены: двоичное дерево поиска ( std::mapточнее, C ++ ), в котором хранятся места, где изменяется высота стены. Благодаря этому я смог добавлять и удалять узлы по мере необходимости (т. Е. Если бы сложная секция подвергалась большой, чрезмерной атаке или касалась нескольких атак одинаковой силы, количество узлов значительно уменьшилось бы). Это решило большой ввод за 3,9 секунды (на моем ноутбуке среднего уровня разработки). Я подозреваю, что есть несколько причин для улучшения:

• Как вы указали, упаковка и распаковка могут быть дорогими, но контейнеры на основе шаблонов C ++ полностью этого избегают.
• В то время как представление стены, которое я использовал, теоретически хуже, в подавляющем большинстве случаев возможность динамического сокращения количества узлов делала его сверхбыстрым (большинство тестовых случаев были максимально использованы на узлах менее 1 тыс., А все, кроме 2, были менее 10 тыс.) , Фактически, единственным случаем, который занимал какое-то значительное время, был № 7, который, по-видимому, проверял множество непересекающихся диапазонов.
• Я не использовал предварительную обработку (этапы определяются путем отслеживания того, когда каждое племя будет атаковать в следующий раз, и поиска соединения-младшего в каждом ходу). Опять же, это теоретически хуже, но в большинстве случаев я подозреваю, что более низкие издержки означают, что это было быстрее (я проверю это и вернусь к вам). Обновление : я добавил приоритетную очередь для атак, аналогично описанному выше методу (хотя вместо создания большого массива я вычислял его на лету) и увидел уменьшение времени до 3,0 секунд для большого ввода.

Короче говоря, хотя я думаю, что ваш алгоритм почти оптимален в общем случае, есть несколько способов ускорить его для типичных входных данных .

Следующее было удалено из вопроса, так как это ответ.

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

Решение можно найти здесь . Это очень похоже на то, что я разместил здесь; поэтому я гораздо больше склонен полагать, что более эффективного решения не существует.