анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 15 Дополнительные темы В этой последней главе представлена подборка дополнительных алгорит- мов и структур данных. Свободное владение изложенными здесь методами иногда может помочь при решении наиболее трудных олимпиадных задач. В разделе 15.1 обсуждаются приемы создания структур данных и алго- ритмов, в которых встречается квадратный корень. В основе решения за- частую лежит идея о разбиении последовательности n элементов на O(√n) блоков, каждый из которых состоит из O(√n)элементов. В разделе 15.2 рассматриваются дополнительные возможности дерева отрезков. Например, мы увидим, как создать дерево отрезков, которое поддерживает как запросы по диапазону, так и обновление диапазона. В разделе 15.3 представлена структура данных «дуча» (дерево-куча), позволяющая эффективно разбить массив на две части и объединить два массива в один. Раздел 15.4 посвящен оптимизации метода динамического программи- рования. Сначала мы рассмотрим трюк с выпуклой оболочкой, который применяется для линейных функций, а затем обсудим его оптимизацию методом «разделяй и властвуй» и оптимизацию Кнута. В разделе 15.5 рассматриваются различные приемы проектирования алгоритмов, в частности встреча в середине и параллельный двоичный поиск. 15.1. Квадратный корень в алгоритмах Квадратный корень можно рассматривать как «логарифм для бедных»: сложность O(√n)лучше, чем O(n), но хуже, чем O(log n). Так или иначе, многие структуры данных и алгоритмы, в которых участвуют квадратные корни, оказываются быстрыми и практичными. В этом разделе приведено несколько примеров использования квадратного корня в проектировании алгоритмов. 15.1.1. Структуры данных Иногда эффективная структура данных получается, если разбить мас- сив на блоки размера √n и хранить информацию о значениях элементов 280 Глава 15. Дополнительные темы массива внутри каждого блока. Например, предположим, что требуется обрабатывать запросы двух типов: модификация элементов массива и на- хождение минимального значения в диапазоне. Выше мы видели, что де- рево отрезков способно поддержать выполнение обеих операций за время O(log n), а сейчас решим эту задачу проще, согласившись на временную сложность O(√n). Разобьем массив на блоки по √n элементов и для каждого блока будем хранить минимальное значение в нем. На рис. 15.1 показан массив из 16 элементов, разбитый на блоки по 4 элемента. При изменении значения любого элемента необходимо модифицировать соответствующий блок. Это можно сделать за время O(√n), просмотрев все элементы блока, как показано на рис. 15.2. Затем для вычисления минимального значения по диапазону мы разобьем диапазон на три части: одиночные элементы по краям и блоки между ними. На рис. 15.3 показан пример такого разбиения. Ответом на запрос является либо значение какого-то из одиночных эле- ментов, либо минимум в одном из блоков. Поскольку и число одиночных элементов, и число блоков равно O(√n), то запрос выполняется за время O(√n). 5 8 6 3 4 7 2 6 7 1 7 5 6 2 3 2 3 2 1 2 Рис. 15.1. Структура на основе квадратного корня для поиска минимального значения в диапазоне 5 8 6 3 4 7 5 6 7 1 7 5 6 2 3 2 3 4 1 2 Рис. 15.2. При обновлении элемента массива необходимо также обновить минимальное значение в соответствующем блоке 5 8 6 3 4 7 2 6 7 1 7 5 6 2 3 2 3 2 1 2 Рис. 15.3. Для определения минимального значения в диапазоне этот диапазон разбивается на одиночные элементы и блоки Насколько эта структура эффективна на практике? Чтобы выяснить это, мы поставили эксперимент: создали массив, содержащий n случайных чи- сел типа int , и обработали n случайных запросов о минимуме. Мы реали- зовали три структуры данных: дерево отрезков с временной сложностью запроса O(log n), описанную выше структуру на основе квадратного корня с временной сложностью O(√n) и простой массив с временной сложно- 15.1. Квадратный корень в алгоритмах 281 стью O(n). Результаты сведены в табл. 15.1. Оказалось, что для этой задачи структура на основе квадратного корня вполне эффективна для значений n , не превышающих 2 18 , но потом время выполнения заметно уступает де- реву отрезков. Таблица 15.1. Время выполнения запроса о минимуме в диапазоне при использова- нии трех структур данных: дерева отрезков (O(log n)), структуры на основе квадратно- го корня (O(√n )) и простого массива (O(n)) Размер входных данных n Время выполнения O(log n) (с) Время выполнения O(√n ) (с) Время выполнения O(n ) (с) 2 16 0.02 0.05 1.50 2 17 0.03 0.16 6.02 2 18 0.07 0.28 24.82 2 19 0.14 1.14 > 60 2 20 0.31 2.11 > 60 2 21 0.99 9.27 > 60 15.1.2. Подалгоритмы Далее мы обсудим две задачи, которые можно эффективно решить пу- тем создания двух подалгоритмов, специализированных для различных ситуаций, которые могут иметь место в процессе выполнения алгоритма. И хотя каждый подалгоритм может решить задачу без использования дру- гого, их комбинирование повышает общую эффективность. Расстояние между буквами. Первая задача ста- вится следующим образом: дана сетка n×n, в каждой клетке которой находится буква. Каково минимальное манхэттенское расстояние между двумя клетками, со- держащими одну и ту же букву? На рис. 15.4 минималь- ное расстояние между клетками, содержащими букву «D», равно 2. Для решения задачи мы можем перебрать все буквы в сетке и для каждой буквы c определить минимальное расстояние между клетками, содержащими эту букву. Рассмотрим два алгоритма обработки фиксированной буквы c. Алгоритм 1. Перебрать все пары клеток, содержащих букву c, и опре- делить пару, для которой расстояние минимально. Этот алгоритм требует времени O(k 2 ), где k – число клеток, содержащих букву c. Алгоритм 2. Выполнить поиск в ширину, одновременно начинающийся во всех клетках с буквой c. Этот поиск занимает время O(n 2 ). A C E A B D F D E A B C C F E A Рис. 15.4. Пример задачи о рас- стоянии между буквами 282 Глава 15. Дополнительные темы Для обоих алгоритмов имеются худшие случаи. Для алгоритма 1 это слу- чай, когда буквы во всех клетках одинаковы, тогда k = n 2 , и время рабо- ты алгоритма составляет O(n 4 ). Для алгоритма 2 худшим является случай, когда буквы во всех клетках разные. Тогда алгоритм придется выполнить O(n 2 )раз, и общее время работы составит O(n 4 ). Однако мы можем скомбинировать эти алгоритмы, так чтобы они рабо- тали как подалгоритмы одного алгоритма. Идея в том, чтобы для каждой буквы c по отдельности определить, какой алгоритм использовать. Оче- видно, что алгоритм 1 хорошо работает, если k мало, а алгоритм 2 лучше приспособлен для больших k. Следовательно, мы можем зафиксировать константу x и применять алгоритм 1, если k не больше x, и алгоритм 2 в противном случае. В частности, если выбрать x = √n 2 = n, то получится алгоритм с временной сложностью O(n 3 ). Сначала каждая клетка, обрабатываемая алгоритмом 1, сравнивается не более чем с n другими клетками, так что обработка зани- мает время O(n 3 ). Затем, поскольку существует не более n букв, которые могут встречаться более чем в n клетках, алгоритм 2 выполняется самое большее n раз, и общее время работы также равно O(n 3 ). Черные клетки. В качестве еще одного примера рассмотрим следую- щую игру. На доске n×n имеется ровно одна черная клетка, а все осталь- ные белые. На каждом ходе выбирается одна белая клетка, и мы должны вычислить минимальное манхэттенское расстояние между ней и черной клеткой. Затем выбранная белая клетка перекрашивается в черный цвет. Этот процесс повторяется n 2 − 1 раз, после чего все клетки оказываются черными. На рис. 15.5 показан один ход в игре. Минимальное расстояние от вы- бранной клетки X до черной клетки равно 3 (надо сделать два шага вниз и один шаг вправо). После этого клетка перекрашивается в черный цвет. X Рис. 15.5. Ход в игре в черные клетки. Минимальное расстояние от X до черной клетки равно 3 Эту задачу можно решить, обрабатывая ходы порциями по k ходов. В на- чале каждой порции мы для каждой клетки доски вычисляем минималь- ное расстояние до черной клетки. Это можно сделать за время O(n 2 ), при- менив поиск в ширину. Далее в процессе обработки порции мы храним 15.1. Квадратный корень в алгоритмах 283 список всех клеток, которые были перекрашены в черный цвет в текущей порции. Таким образом, минимальное расстояние до черной клетки либо предварительно вычислено, либо является расстоянием до одной из кле- ток в списке. Поскольку список содержит не более k значений, то для его обхода требуется время O(k). Следовательно, взяв k = √n 2 = n, мы получим алгоритм, работающий за время O(n 3 ). Во-первых, существует O(n)порций, поэтому полное время, затраченное на поиски в ширину, равно O(n 3 ). Во-вторых, список клеток в порции содержит O(n)значений, поэтому вычисление минимальных рас- стояний для O(n 2 )клеток также требует времени O(n 3 ). Оптимизация параметров. На практике необязательно использовать в качестве параметра точный квадратный корень, нужно лишь настро- ить производительность алгоритма, поэкспериментировав с различными значениями параметров и выбрав то, которое дает наилучший результат. Разумеется, оптимальное значение зависит от алгоритма и от свойств тес- товых данных. В табл. 15.2 приведены результаты эксперимента, в котором алгоритм игры в черные клетки с временной сложностью O(n 3 )выполнялся для раз- личных значений k при n = 500. Порядок перекрашивания клеток в черный цвет выбирался случайным образом. В данном случае оптимальным, по- хоже, является параметр k в районе2000. Таблица 15.2. Оптимизация значения параметра k в алгоритме игры в черные клетки Параметр k Время работы (с) 200 5.74 500 2.41 1000 1.32 2000 1.02 5000 1.28 10 000 2.13 20 000 3.97 15.1.3. Целые разбиения Пусть имеется палочка длины n, разрезан- ная на несколько частей целочисленной дли- ны. На рис. 15.6 показано несколько таких разбиений для n = 7. Каково максимальное число различных длин в таком разбиении? Оказывается, что различных длин может быть не более O(√n). А оптимальный способ 7 3 4 1 3 1 2 Рис. 15.6. Несколько целых разбиений палочки длины 7 284 Глава 15. Дополнительные темы получить максимально возможное число различных длин – взять длины 1, 2, …, k. Тогда, поскольку 1 + 2 + ··· + k = k (k + 1) , 2 мы можем сделать вывод, что k не может быть больше O(√n). Далее мы увидим, как воспользоваться этим наблюдением при проектировании ал- горитмов. Задача о рюкзаке. Пусть дан список целых весов [w 1 ,w 2 ,…,w k ] – та- ких, что w 1 + w 2 + … + w k = n, а наша задача – найти все возможные сум- мы, составленные из этих весов. На рис. 15.7 показаны возможные суммы, составленные из весов [3, 3, 4]. 0 1 2 3 4 5 6 7 8 9 10 Рис. 15.7. Возможные суммы, составленные из весов [3, 3, 4] Применив стандартный алгоритм рюкзака (раздел 6.2.3), мы можем ре- шить задачу за время O(nk), так что если k = O(n), то временная сложность окажется равной O(n 2 ). Но поскольку различных весов не более O(√n), зада- чу можно решить эффективнее, если одновременно обрабатывать все веса, имеющие определенное значение. Например, если имеются веса [3, 3, 4], то мы сначала обработаем два веса, равных 3, а затем вес 4. Стандартный алгоритм рюкзака нетрудно модифицировать таким образом, что обра- ботка каждой группы одинаковых весов займет всего лишь время O(n), и в результате получается алгоритм с временной сложностью O(n√n). Составление строки. Рассмотрим еще один пример. Пусть даны строка длины n и словарь, состоящий из слов суммарной длины m. Наша задача – посчитать, сколько существует способов составить строку из слов. Напри- мер, имеется четыре способа составить строку ABAB из слов {A , B, AB} : • A + B + A + B ; • AB + A + B ; • A + B + AB ; • AB + AB Применив динамическое программирование, мы для каждого k = 0, 1, ..., n сможем вычислить, сколькими способами можно составить префикс стро- ки длиной k. Одно из возможных решений – воспользоваться префиксным деревом, которое содержит обращения всех словарных слов, что дает алго- ритм с временной сложностью O(n 2 + m). Но есть и другой подход: восполь- зоваться хешированием строк и тем фактом, что существует не более O(√m) различных длин слов. Следовательно, можно ограничиться фактически 15.1. Квадратный корень в алгоритмах 285 существующими длинами слов. Для этого мы можем создать множест во, содержащее все хеш-коды слов, что приводит к алгоритму с временной сложностью O(n√m + m)(если воспользоваться классом unordered_set ). 15.1.4. Алгоритм Мо Алгоритм Мо 1 обрабатывает множество запросов по диапазону стати- ческого массива (т. е. значения элементов массива не изменяются между запросами). Для ответа на каждый запрос требуется вычислить нечто, за- висящее от элементов массива в некотором диапазоне [a, b]. Поскольку массив статический, запросы можно обрабатывать в любом порядке, а изюминка алгоритма Мо состоит в том, чтобы выбрать специальный по- рядок, гарантирующий эффективность алгоритма. В алгоритме поддерживается активный диапазон массива, и в каждый момент ответ на запрос, касающийся активного диапазона, известен. Ал- горитм обрабатывает запросы по одному и каждый раз перемещает кон- цевые точки активного диапазона, вставляя и удаляя элементы. Массив разбивается на блоки по k = O(√n)элементов, и запрос [a 1 , b 1 ] всегда обра- батывается раньше запроса [a 2 , b 2 ], если • ⌊a 1 /k⌋ < ⌊a 2 /k⌋ или • ⌊a 1 /k⌋ = ⌊a 2 /k⌋ и b 1 < b 2 Таким образом, все запросы, для которых левые концевые точки нахо- дятся в некотором блоке, обрабатываются один за другим в порядке воз- растания правых концевых точек. При таком порядке алгоритм выполня- ет только O(n√n)операций, поскольку левая концевая точка сдвигается на O(n)×O(√n )шагов, а правая концевая точка – на O(√n)×O(n)шагов. Следо- вательно, за время работы алгоритма обе концевые точки суммарно сдви- гаются на O(n√n)шагов. Пример. Пусть дано множество диапазонов массива, и требуется вы- числить количество различных значений в каждом диапазоне. В алгоритме Мо запросы всегда сортируются одинаково, но способ хранения ответа на запрос зависит от задачи. Чтобы решить эту задачу, мы заведем массив count , в котором элемент count [x ] показывает, сколько раз элемент x встречается в активном диапа- зоне. При переходе от одного запроса к другому активный диапазон изме- няется. Рассмотрим, к примеру, два диапазона на рис. 15.8. Для перехода от первого диапазона ко второму надо сделать три шага: левая концевая точка сдвигается на один шаг вправо, а правая концевая точка – на два шага вправо. После каждого шага массив count следует обновить. Добавив элемент x, мы увеличиваем значение count [x ] на 1, и если после этого окажется, что 1 Согласно [6], алгоритм Мо назван в честь китайского олимпиадного программиста Мо Тао. 286 Глава 15. Дополнительные темы count [x ] = 1, то также прибавляем 1 к ответу на запрос. Аналогично, удалив элемент x, мы уменьшаем значение count [x ] на 1, и если после этого ока- жется, что count [x ] = 0, то также вычитаем 1 из ответа на запрос. Поскольку каждый шаг выполняется за время O(1), временная сложность алгоритма равна O(n√n). 4 2 5 4 2 4 3 3 4 4 2 5 4 2 4 3 3 4 Рис. 15.8. Переход от одного диапазона к другому в алгоритме Мо 15.2. И снова о деревьях отрезков Дерево отрезков – многоцелевая структура данных, применимая для ре- шения многих разных задач. До сих пор мы видели лишь небольшую часть ее возможностей. Пора обсудить более развитые варианты деревьев от- резков, позволяющие решать задачи посложнее. Выше при реализации операций с деревом отрезков мы поднимались снизу вверх. Так, для вычисления суммы значений в диапазоне [a, b] (раз- дел 9.2.2) использовалась следующая функция: |