Комментарии 11
НЛО прилетело и опубликовало эту надпись здесь
Спортивное программирование учит человека думать по-другому. Ваши заслуги достойны уважения! Достичь отличных результатов можно только приложив массу усилий. Есть чем гордиться, поздравляю!
Чем-то мне это напомнило дебюты в шахматах.
Профессиональные шахматисты знают десятки, а может сотни тысяч, и в нужный момент применяют.
Аналогично и тут. У человека есть база алгоритмов, которые он должен увидеть в задаче и применить.
Профессиональные шахматисты знают десятки, а может сотни тысяч, и в нужный момент применяют.
Аналогично и тут. У человека есть база алгоритмов, которые он должен увидеть в задаче и применить.
Даже не столько алгоритмов, сколько известных конструкций. Взгляд цепляется за знакомые объекты:
— О, турнир. Можно построить к нему дерево турнира и посчитать какую-нибудь информацию на нём.
— О, минимумы на отрезках. Можно применить дерево отрезков.
— О, нужно выделять отрезки из последовательности и заменять. Можно воспользоваться декартовым деревом по неявному ключу.
— О, наиболее удалённый лист в дереве. Можно воспользоваться динамическим программированием…
И тому подобное.
— О, турнир. Можно построить к нему дерево турнира и посчитать какую-нибудь информацию на нём.
— О, минимумы на отрезках. Можно применить дерево отрезков.
— О, нужно выделять отрезки из последовательности и заменять. Можно воспользоваться декартовым деревом по неявному ключу.
— О, наиболее удалённый лист в дереве. Можно воспользоваться динамическим программированием…
И тому подобное.
Напомнило задачу из книги «конкретная математика» кнута. Там где пленные выстраивались в круг и убивали каждого третьего вроде.
Не о задаче ли Иосифа Флавия речь?
Пожалуй, тут можно обойтись без дерева. Будем работать с массивами, в которых хранятся начала и концы отрезков (являющихся проекциями вершины дерева на ряд рыцарей, оставшихся к какому-то моменту), отсортированными по возрастанию (в нашем примере, если проектировать весь турнир на начальную позицию, получится массив [(1,+),(1,+),(2,+),(4,-),(4,-),(5,-)]. Чтобы построить такой массив за N*log(N), можно воспользоваться аналогом MergeSort: разделить турнир на две части, построить проекцию его первой половины на начало турнира, а второй половины — на начало этой второй половины (получится: первый массив [(2,+),(4,-)], а второй — [(1,+),(1,+),(2,-),(3,-)]. Нетрудно понять, как за линейное время составить из этих половинок проекцию всего турнира — первый массив пойдет без преобразования, а точки второго будут попадать только в места, свободные от отрезков первого, причем их положения надо будет модифицировать.
После того, как проекция турнира построена, идем по ней от начала, и для каждого отрезка считаем три характеристики — максимум силы рыцарей на этом отрезке, в предположении, что опоздавший попал в него; максимальную глубину вложенности отрезков, начиная с данного, и какую-нибудь точку на самом глубоком отрезке (чтобы выдать её в качестве ответа). Это делается за линейное время (понадобится стек). В процессе обхода для каждого отрезка, сила рыцарей на котором меньше силы опоздавшего, его максимальная глубина и положение будут кандидатами на ответ — из них нам надо выбрать отрезок максимальной глубины.
И никаких декартовых деревьев, всё детерминировано.
После того, как проекция турнира построена, идем по ней от начала, и для каждого отрезка считаем три характеристики — максимум силы рыцарей на этом отрезке, в предположении, что опоздавший попал в него; максимальную глубину вложенности отрезков, начиная с данного, и какую-нибудь точку на самом глубоком отрезке (чтобы выдать её в качестве ответа). Это делается за линейное время (понадобится стек). В процессе обхода для каждого отрезка, сила рыцарей на котором меньше силы опоздавшего, его максимальная глубина и положение будут кандидатами на ответ — из них нам надо выбрать отрезок максимальной глубины.
И никаких декартовых деревьев, всё детерминировано.
Да, все верно. Похожее решение у нас написал Егор Суворов (yeputons).
Отличный разбор! И, кстати, поздравляю с золотой медалью!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разбор задачи с IOI2012