- PVSM.RU - https://www.pvsm.ru -
Всем привет! В сентябре прошла международная олимпиада по программированию, IOI 2012. И мы, сборная России, на неё весьма успешно съездили [1], как вы могли видеть.
Я — Макс Ахмедов. Мне предложили поделиться с общественностью, что из себя представляют подобные соревнования и какие задачи нам приходится решать. Я расскажу о последней задаче второго тура «Jousting Tournament». Английский вариант условия можно найти здесь [2]. К слову, это наиболее простая из трёх задач в тот день :-)
В задаче идёт речь о церемонии обручения герцога Лодовико Сфорца, наместника Милана, и герцогини Беатриче д’Эсте, произошедшей в 1491. Организовывать празднества и управлять культурной программой герцог пригласил своего хорошего друга Леонардо да Винчи, который ему предложил, в частности, устроить шикарный рыцарский турнир.
И вот, к началу празднеств оказалось, что вовремя прибыли все рыцари, кроме одного, который опаздывает, но не настолько сильно, чтобы помешать проведению турнира. По случайному совпадению, этот рыцарь был фаворитом толпы, и все сражения с его участием пользовались большой популярностью. Леонардо знает расписание боёв турнира и то, как будут выбираться рыцари для участия в них, и он хочет слегка повлиять на ход турнира таким образом, чтобы рыцарь-фаворит поучаствовал в как можно большем количестве сражений. Так хитрый пиарщик Леонардо собирается увеличить значимость события.
Такая вот захватывающая история.
Рыцарский турнир происходит следующим образом. В ряд стоит некоторое количество рыцарей. Перед каждым очередным сражением выходит судья и вызывает рыцарей, стоящих на позициях, образующих непрерывной отрезок, на поединок, в результате которого определяется победитель. Победитель возвращается на своё место, а проигравшие рыцари выбывают. После этого ряд рыцарей сдвигается, занимая пустые места. Более формально: в ряд стоят N рыцарей, судья называет два числа l и r, после этого рыцари, занимающие в порядке нумерации слева направо места с l-ого по r-ое, сражаются и из них в ряду остаётся только победитель. После этого происходят последующие сражения по такому же принципу до тех пор, пока не останется один рыцарь, который объявляется победителем турнира.
На данный момент все N — 1 рыцарей, кроме опаздывающего, уже заняли свои места в ряду. Леонардо имеет возможность поставить прибывшего фаворита на любое место в ряду, в том числе в начало или в конец. Порядок сражений и позиции рыцарей, в них участвующих, уже определены. Леонардо знает для каждого рыцаря значение его абстрактной “силы”, выражаемое целым числом от 0 до N — 1. В рамках этой задачи считается, что в сражении, в котором участвует определённые рыцари, в любом случае побеждает тот из них, который имеет наибольшее значение силы. Так сложилось, что на турнире все рыцари различны по силе, то есть в любом сражении победитель определяется однозначно исходя их знания их значений. Леонардо хочет добиться того, чтобы по итогам турнира количество сражений, в которых победил любимец толпы, было как можно большим, а из всех позиций, приводящих к такому исходу, он хочет выбрать самую левую. Обратите внимание: необязательно, чтобы наш рыцарь становился победителем всего турнира! Достаточно максимизировать количество сражений, из которых он вышел победителем.
Разберёмся на примере. Пусть в турнире участвуют 5 рыцарей. Пунктуальные рыцари, стоящие в ряд, имеют значения силы [1, 0, 2, 4], если смотреть слева направо. Как можно понять, опаздывающий рыцарь имеет значение силы 3. Пусть, например, турнир состоит из трёх раундов, которые характеризуются позициями (2, 4), (1, 2) и (1, 2). Поясним, что это значит.
Такой турнир можно более наглядно отобразить в виде дерева:
Далее, к слову, мы ещё вернёмся к подобным деревьям.
Поймём, как будет выглядеть картина турнира, если, например, Леонардо поставит фаворита слева от всех остальных рыцарей. Изначально значения силы рыцарей выглядят слева направо как [3, 1, 0, 2, 4].
Таким образом, наш рыцарь выиграет всего лишь один поединок, до того как выбыть. Лучшим решением было бы поставить его на позицию между рыцарями рангами 1 и 0, образовав ряд [1, 3, 0, 2, 4].
В итоге фаворит выигрывает два поединка.
Большее количество сражений он выиграть не может, так как он уже выиграл все раунды, кроме одного, а победить во всех он не может, потому что есть рыцарь (имеющий ранг 4) сильнее его, который гарантированно станет победителем турнира. Значит, позиция между первыми двумя рыцарями – это та самая, требуемая Леонардо, которая является ответом к задаче.
Количество баллов, которое получит программа, зависит от эффективности решения. Если оно работает достаточно быстро, чтобы получать за одну секунду правильный ответ в ситуациях, где количество рыцарей не превышает 500, то решение получит 17 баллов из 100. Если оно успевает посчитать правильный ответ при количестве рыцарей, достигающем 5000, то оно будет оценено в 49 баллов. Для получения полного балла решение должно успевать обрабатывать турниры, включающие до ста тысяч рыцарей. В нашей сборной все четыре человека написали решения, получающие 100 баллов — задача оказалась самой простой на туре.
Простейшим решением к задаче будет явно проверить каждую из N возможных позиций для опаздывающего рыцаря и найти из них наиболее выгодную. Единственным техническим моментом в решении будет симулирование турнира при данном изначальном расположении рыцарей. Можно делать это совершенно наивно: например, поддерживать ряд рыцарей в списке слева направо и в каждом очередном раунде выделять сражающихся рыцарей, находить из них самого сильного, ставить его обратно, и сдвигать рыцарей, заполняя пустые места.
Такое решение должно проходить первую группу тестов, в которых количество рыцарей не превосходит пятисот. Давайте оценим, сколько оно будет работать, посчитав порядок количества операций, выполняемых программой. В каждом раунде нам необходимо в худшем случае сдвигать почти всех рыцарей левее, заполняя пустые места, то есть один раунд программа в худшем случае обрабатывает за количество операций, пропорциональное длине ряда, который в среднем состоит из, грубо говоря, N / 2 рыцарей. Раундов в турнире в худшем же случае может быть аж N — 1, а нам еще нужно просимулировать целых N возможных турниров – для всех возможных позиций опоздавшего рыцаря. Получается зависимость N^3 / 2 для количества простых операций, выполняемых программой от количества рыцарей N.
К слову, современные компьютеры успевают выполнить порядка 400-500 миллионов простых операций за секунду. Мы оценили сложность нашего решения для N = 500 как около 62 миллионов простых операций, поэтому можно рассчитывать на то, что оно с запасом уложится в ограничение по времени. И действительно, написав это решение, можно получить заслуженные семнадцать баллов – это полезно хотя бы потому, что такое решение может стать хорошим подспорьем при дальнейших отладке и тестировании задачи, благо реализуется совсем просто.
Для того чтобы решение работало не более секунды на тестах с 5000 рыцарей, кубическая сложность алгоритма уже никак не подходит – нужно снижать оценку сложности хотя бы до пропорциональной квадрату N. В таких случаях часто употребляют O-большое терминологию [3]: речь идет об алгоритме сложностью O(N^2).
Нам нужно убрать один их трех множителей N в оценке сложности выше. Как избавляться от внешнего – перебора позиции для опоздавшего рыцаря – пока не очень понятно. Значит, давайте увеличивать эффективность симуляции турнира. От количества раундов нам, казалось бы, никуда не уйти – стало быть, надо сделать более эффективным выполнение одного сражения. У нас есть очень неэффективный кусок в сдвигании всех рыцарей для заполнения пустых мест: так как массив лежит в памяти неделимым фрагментом и мы хотим быстро переходить к рыцарю по его позиции, от этого никуда не уйти. Нам нужно как-то изменить структуру их хранения.
Одним из решений было бы использование вместо массива рыцарей какой-либо структуры, позволяющей вырезать отрезки за более короткое время. Но этот путь очень сомнительный, потому что большинство таких структур работает не быстрее, чем за время O(log N), а сложность работы O(N^2 log N) – очень опасна: 300 миллионов операций совершенно не гарантируют, что решение войдет во временные ограничения.
Налицо факт, что мы делаем слишком много лишних операций – зачем-то поддерживаем положения рыцарей в явном виде. Если вспомнить о такой штуке, как дерево турнира, то становится ясно, как ее использовать для быстрого проведения всех сражений. Если мы должны провести раунд, соответствующий какой-то вершине, то нам достаточно провести раунды, соответствующие дочерним вершинам, а потом выбрать из победителей этих раундов самого сильного. Это делается, например, во время обхода дерева турнира в глубину. Таким образом, при наличии дерева турнира мы можем провести все сражения за линейное время O(N). Снаружи у нас по-прежнему стоит перебор позиции, куда мы ставим нашего фаворита, тоже имеющий сложность O(N). Значит, собственно нахождение ответа при данном дереве мы умеем выполнять за O(N^2).
Осталось только научиться это дерево строить. Нам достаточно его построить один раз хоть за квадратичное время, чтобы потом использовать. Это можно делать по аналогии с тем, как мы в наивном решении проводили раунды: будем вместо значений силы рыцарей хранить в ряду вершины в дереве турнира, соответствующие рыцарям-победителям на этих местах. С каждым раундом будем выделять подотрезок, на котором стоят рыцари-вершины, участвующие в этом раунде, и ставить вместо этого подотрезка новую, родительскую для всех, вершину.
Таким образом, у нас вышло решение, требующее O(N^2) памяти на построение дерева турнира и O(N^2) на нахождение по нему ответа. Такое решение при N <= 5000 должно с запасом заходить по времени и получать 49 баллов.
Давайте дальше улучшать решение. Построение дерева можно оптимизировать по времени, если вместо массива хранить вершины дерева турнира в какой-нибудь структуре данных, умеющей быстро вырезать подотрезок (быстрее, чем за O(N), как это можно сделать в массиве). Примером такой удобной структуры данных является декартово дерево по неявному ключу, о котором когда-то речь шла на хабре [4] в том числе, и о котором можно почитать, например, здесь [5]. В итоге, реализация построения дерева турнира останется почти прежней, за тем исключением, что поменяется представление рыцарей-вершин в ряду и способ работы с ними. Тем самым, первая часть решения оптимизирована до O(N log N).
Чтобы оптимизировать вторую часть, нужно понять, чтоперемещение нашего одного-единственного фаворита на результаты турнира влияет, в принципе, совсем не сильно. Например, то, где изначально стоит опоздавший, никоим образом не изменит победителя всего турнира – это в любом случае будет рыцарь с самой большой силой.
Давайте дальше рассуждать – вот кто вообще оказывается в определённой вершине дерева турнира как победитель? Достаточно очевидно, что это рыцарь, являющийся самым сильным в поддереве, соответствующем этой вершине. Это – очень полезное соображение, оно нам позволяет понять, например, когда наш фаворит может теоретически оказаться как победитель в какой-нибудь вершине: для этого необходимо и достаточно, чтобы в этом поддереве не было рыцаря сильнее его. А что такое поддерево какой-то вершины? Это отрезок ряда, в котором уже стоят пунктуальные рыцари – самого сильного рыцаря на нём мы можем найти, например, с помощью такой структуры данных, как дерево отрезков [6].
Значит, для каждой вершины дерева турнира мы можем определить, может ли наш фаворит в ней оказаться. А если он может в ней оказаться, то нам выгоднее всего поставить его на такую позицию, чтобы путь до неё в этом дереве был как можно длиннее: каждая вершина на пути – это какое-то сражение, в котором фаворит побывал, а нам ровно это количество сражений и надо максимизировать по условию задачи. Значит, осталось только из всех доступных нашему фавориту вершин выбрать ту из них, которая содержит максимально глубокий лист (то есть вершину дерева, не имеющую «детей» – эта вершина соответствует какой-то позиции для рыцаря), и выбрать этот лист в качестве ответа.
Тем самым вторая часть решения тоже оптимизировалась до O(N log N). Для N <= 100000 решение с такой сложностью, как правило, заходит в ограничение по времени – эта задача не является исключением. И действительно, реализовав такое (за незначительными отклонениями) решение, мы вчетвером получили полный балл.
Чем-то из такой оперы на наших олимпиадах мы и занимаемся — это типичный пример многоходовой, серьёзной задачи с международной олимпиады с различными путями решения и множеством логических кирпичиков. Надеюсь, стало чуть-чуть более ясно, чего мы такое программируем, и за что потом получаем медальки :-) До встречи!
Автор: Zlobober
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/17781
Ссылки в тексте:
[1] съездили: http://habrahabr.ru/company/abbyy/blog/153071/
[2] здесь: http://www.ioi2012.org/wp-content/uploads/2011/12/tournament.pdf
[3] O-большое терминологию: http://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5
[4] на хабре: http://habrahabr.ru/post/101818/
[5] здесь: http://e-maxx.ru/algo/treap
[6] дерево отрезков: http://habrahabr.ru/post/128787/
Нажмите здесь для печати.