Бинарный поиск – примеры задач

Примеры задач бинарного поиска

РЕКОМЕНДУЮ ИЗУЧАТЬ ПРИМЕРЫ ЗАДАЧ КОГДА ВЫ ЗНАЕТЕ ТАКЖЕ И ДРУГИЕ АЛГОРИТМЫ: СОРТИРОВКИ, РЕКУРСИИ, ЖАДНЫЕ АЛГОРИТМЫ, АЛГОРИТМЫ НА ГРАФАХ, ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ!

Описание алгоритма здесь

Задача 1. Кормление муравьев

Условие

У Боби есть террариум в форме дерева. Каждое ребро этого дерева является трубкой, по которой стекает жидкость. Некоторые ребра образованы супер трубками, по которым может протекать большее количество жидкости. В каждом листе (концевом узле) дерева находится один ручной муравей (согласен, что контекст фантастический, но сама задача очень интересная).

У каждой трубки-ребра есть значение веса, указывающее процент протекающей по ней жидкости. К примеру, из узла n исходят три трубки, по которым стекает 20%, 50% и 30% жидкости от общего объема. Если в узел n поступает 20 литров жидкости, тогда по первой трубке стекает 20 × 0,2 = 4 литра, по второй 20 × 0,5 = 10 литров, по третьей 20 × 0,3 = 6 литров.

Каждая супер трубка может работать в стандартном или супер режиме — в зависимости от выбора Боби. Если включен супер режим, то количество протекающей жидкости возводится в квадрат.

Боби заливает жидкость в корень дерева. Его цель — дать каждому муравью не меньше необходимого количества, минимизируя при этом заливаемый объем. Конкретизируем описание на примере террариума на рисунке.

Узлы пронумерованы от 1 до 6. Концевые узлы (2, 3, 5 и 6) имеют дополнительные значения, указывающие необходимое каждому муравью количество жидкости. Также указаны процентные значения для ребер. Обратите внимание, что сумма этих значений для ребер, исходящих из одного узла, всегда равна 100%. В дереве есть одна супер трубка, ведущая из узла 1 к узлу 4. Она обозначена красной линией.

Предположим, что в корень заливается 20 литров жидкости. Супер трубка получает 30% от 20 литров. Если супер режим этой трубки отключен, то через нее протекает 6 литров. Если же этот режим активен, то через нее пройдет 6 * 6 = 36 литров.

Входные данные

Входные данные содержат один тестовый пример, состоящий из следующих строк:

• целого числа n, задающего количество узлов в дереве. Значение n находится между 1 и 1000. Узлы дерева пронумерованы от 1 до n, а корнем является узел 1;
• (n – 1) строк, используемых для построения дерева. Каждая содержит данные об одной трубке и состоит из четырех целых чисел: номеров двух узлов, соединяемых этой трубкой, ее процентного значения (между 1 и 100) и указания о возможности суперрежима (0 означает отсутствие, 1 — наличие);
• строки, содержащей n целых чисел, по одному для каждого узла, сообщающих количество литров, необходимых муравью в этом узле. Каждому муравью требуется от 1 до 10 литров жидкости. Все не концевые узлы (в которых нет муравья) содержат значение –1.

Вот входные данные, которые сгенерируют образец террариума с рисунка выше:
6
1 2 20 0
1 3 50 0
1 4 30 1
4 5 50 0
4 6 50 0
-1 2 9 -1 7 8

Обратите внимание, что первая строка (число 6) указывает количество узлов дерева, а не количество строк, его выстраивающих. Число строк, создающих дерево(в данном случае пять), всегда будет на единицу меньше числа узлов.

Выходные данные

Требуется вывести минимальное количество литров жидкости, которое Боби должен залить в корневой узел дерева, чтобы напоить всех муравьев. Точность должна быть выше четырех цифр после запятой. Верное значение не будет превышать двух миллиардов. Время на решение тестового примера — 2,5 секунды.

Решение

В данном случае для исследования дерева террариума можно использовать алгоритм бинарного поиска или рекурсию. Поскольку дерево не предоставляет необходимую информацию в готовом виде, возьмем значение объема наугад. Итак, Боби, давай зальем в корень 10 литров. Вероятно, вас сильно удивит, если верным ответом окажется именно 10, ведь это число я выбрал наугад. Вас также может удивить, что, выбрав произвольное число и проанализировав происходящее, мы можем многое узнать. Вернемся к рисунку из условия и предположим, что заливаем в корневой узел 10 литров. Итак, 20% от 10 — это 2, значит, 2 литра жидкости поступят к муравью в узле 2. Идеально: именно 2 литра ему и надо. Продолжим. Поскольку 50% от 10 равно 5, то муравей в узле 3 получает 5 литров жидкости. Вот теперь у нас проблема, потому что ему нужно 9 литров. При этом трубка между узлами 1 и 3 не имеет супер режима, значит, изменить ситуацию нельзя и 10 верным решением не является. Можно продолжить подставлять наугад и другие количества жидкости, аналогичным образом моделируя ее течение по дереву. И все же, если 10 литров оказалось недостаточно, теперь следует ограничить диапазон до значений больше 10. Поскольку 10 литров было мало, любое меньшее значение также окажется недостаточным. Нет смысла пробовать 2, 7, 9, 5 литров или любое другое количество меньше 10.

Теперь давайте возьмем 20 литров. На этот раз муравей в узле 2 получает 4 литра, что вполне нормально, так как ему достаточно двух. Муравей в узле 3 получает 10 литров, что также допустимо, потому что ему нужно 9. Трубка между узлами 1 и 4 проводит 30% жидкости, то есть 6 из 20 литров. Но при этом она еще и является супер трубкой! Если задействовать супер режим, то она прокачает 36 литров. Значит, в узел 4 протекает 36 литров. Теперь муравьи 5 и 6 будут довольны: каждый из них получает по 18 литров при том, что в узел 5 нужно 7, а в узел 6 — 8 литров. В отличие от 10 литров, 20 оказалось допустимым решением, но является ли оно оптимальным (то есть минимальным)? Возможно, но не обязательно. Однозначно нам известно лишь то, что проверять количество более 20 литров смысла нет. 20 уже дает нам допустимое решение, так зачем пробовать 25 или 30, которые точно хуже? Теперь мы сократили область задачи до нахождения оптимального решения между 10 и 20 литрами. Можно продолжать подбирать числа, с каждым шагом сужая диапазон, пока он не станет столь мал, что его конечные точки окажутся точным решением.

Если рассуждать в общем, то какое количество литров следует выбирать изначально? Оптимальный объем может иметь значение вплоть до 2 миллиардов, так что, начиная с 10, можно оказаться очень далеко от истины. Установив начальное значение, что следует делать дальше? Оптимальное решение может быть значительно больше или меньше выбранного значения, значит, прибавление или вычитание 10 на каждом шаге может не слишком помочь в его поиске. Сначала нужно разобраться с тем, как считывать входные данные (чтобы иметь возможность исследовать дерево) и определять, является ли некоторое количество литров допустимым решением. Затем построить супер быстрый алгоритм для поиска в больших диапазонах. Диапазон в два миллиарда? Мы выполним расчет для него, не напрягаясь с помощью бинарного поиска.

СЧИТЫВАНИЕ ВХОДНЫХ ДАННЫХ

nodes = dict()  # Словарь узлов
N = int(input()) # Количество узлов
for i in range(N - 1):
    from_node, to_node, percentage, superpipe = map(int, input().split())
    if from_node not in nodes:  # Если узла ещё нет
        nodes[from_node] = [[], [], []]
    nodes[from_node][0].append(to_node)
    nodes[from_node][1].append(percentage)
    nodes[from_node][2].append(superpipe)
liquid_needed = list(map(int, input().split()))# Список по узлам конечных значений о количестве нужной каждому муравью жидкости
print(nodes) # => {1: [[2, 3, 4], [20, 50, 30], [0, 0, 1]], 4: [[5, 6], [50, 50], [0, 0]]}
print(liquid_needed) # => [-1, 2, 9, -1, 7, 8]

Переменная to_node указывает на дочерний узел, соединенный ребром с родительским. percentage является целым числом между 1 и 100, которое сообщает процентное значение для трубки (ребра). superpipe — флаг, который имеет значение 1, если трубка имеет суперрежим, и 0, если такой режим отсутствует. В частности, каждое ребро считывается из входных данных, затем устанавливаются его члены, после чего оно добавляется в список ребер для from_node. При этом можно было бы предположить существование соответствующего ребра из to_node, потому что граф ненаправленный, но я такую возможность исключил: жидкость стекает вниз по дереву, но не вверх, значит, добавление обратных ребер излишне усложнит код, исследующий дерево. После считывания информации о дереве остается только считать значения количества жидкости, необходимого каждому муравью. Для этого используется список liquid_needed. Комбинация из nodes и liquid_needed обеспечивает всю необходимую нам информацию на тестовом примере.

ПРОВЕРКА ПРИГОДНОСТИ РЕШЕНИЯ

На следующем этапе надо определить, является ли заданное количество жидкости допустимым решением. Это очень важный шаг, потому что, когда у нас появится функция для проверки допустимости значения, мы сможем использовать ее для постепенного сужения пространства поиска до момента обнаружения оптимального решения. Для этой функции мы напишем следующий заголовок: def can_feed(node, liquid, nodes, liquid_needed):. Здесь node является корневым узлом дерева, liquid указывает количество жидкости, заливаемой в корень, nodes представляет словарь для дерева, а liquid_needed отражает объем жидкости, необходимый каждому муравью. Если значения liquid окажется достаточно, будет возвращаться 1, в противном случае 0.

Давайте теперь подумаем, можно ли применить рекурсию в этой задаче. Вспомним, что для использования рекурсии требуется сформулировать базовый случай, который можно решить без рекурсии. К счастью, у нас такой имеется. Если дерево представлено одним концевым узлом, то можно сразу определить, достаточно ли количества liquid. Если liquid больше либо равно необходимому муравью количеству жидкости, то перед нами допустимое решение. В противном случае решение не допустимое. Определить, является ли узел концевым, можно проверкой соответствующего значения в liquid_needed: если это -1, значит, он не концевой (можно также проверить, является ли связный список смежности пустым). Вот что получается: if liquid_needed[node] != -1: return liquid >= liquid_needed[node]

А теперь рассмотрим рекурсивный алгоритм. Представьте, что корневой узел некоторого дерева имеет p нисходящих трубок (а значит, и p детей). Дано количество заливаемой в корень жидкости. Используя процентные значения трубок, можно определить объем жидкости, которая поступает через каждую из них. При этом с помощью статусов супертрубок можно определить количество жидкости на выходе из каждой трубки. Если до низа трубки доходит достаточный объем питья, то заливаемой в корень жидкости хватает и нужно вернуть True. Если до низа хотя бы одной из трубок доходит недостаточный объем жидкости, то возвращается False. Это предполагает, что нужно сделать p рекурсивных вызовов, по одному для каждой нисходящей из корня трубки. Сделаем мы это в цикле, использующем словарь для каждой такой трубки:

def can_feed(node, liquid, nodes, liquid_needed):
    if liquid_needed[node - 1] != -1:
        return liquid >= liquid_needed[node - 1]
    e = nodes.get(node)
    if e:
        for p in range(len(e[0])):
            down_pipe = liquid * e[1][p] / 100  # e[1] это percentage — процентное значение для трубки
            if e[2][p]: # если "супер трубка"
                down_pipe *= down_pipe  # 2
            if not can_feed(e[0][p], down_pipe, nodes, liquid_needed): # 3
                return False
    return True

Функция отслеживает, является ли liquid допустимым решением для дерева. Пока функция возвращает True, решение считается допустимым. По умолчанию функция вернёт True а в процессе работы может вернуть False, если количество жидкости, прошедшей через одну из трубок, окажется недостаточным. Если к концу работы функции по-прежнему будет True, то все трубки провели достаточное количество жидкости и мы заключаем, что решение liquid допустимо. Количество жидкости, поступающее в каждую трубку, определяется с помощью ее процентного значения. Затем, если трубка имеет супер режим, это значение возводится в квадрат... но стоп! В условии задачи сказано, что Боби должен решить, нужно ли использовать супер режим каждой супер трубки. Однако здесь мы без вариантов возводим количество жидкости в квадрат, всегда используя супер режим. Причина в том, что возведение в квадрат увеличивает значения: сравните 2 и 2*2 = 4, 3 и 3*3 = 9, и т. д. Поскольку нам нужно знать, является ли данное количество жидкости допустимым, и штрафа за использование супер трубки нет, можно предполагать максимальный объем жидкости. Возможно, есть вариант обойтись и без использования супер режима какой-то супер трубки, но никто не просит нас экономить. Не беспокойтесь о том, что возведение в квадрат уменьшает положительные числа меньше единицы, например 0,5 (0,5 * 0,5 = 0,25). Действительно, в подобных случаях активировать супер трубку мы бы не стали. Поскольку каждому муравью нужно не менее 1 литра жидкости, значит, если в одном из узлов мы получим 0,5 литра, то независимо от наших действий муравьи в поддереве этого узла останутся голодными и мы вернем False. Теперь посмотрим, насколько полезна функция can_feed, и для этого продолжим работу. Ранее выше мы показали, что 10 литров недостаточно для рассматривавшегося примера. Добавьте вызов can_feed для проверки объема 10 литров(после получения тестовых данных): print(can_feed(1, 10, nodes, liquid_needed). В результате должен вернуться False, означающий, что 10 литров мало. В том же разделе мы продемонстрировали, что 20 литров будет достаточно. Измените вызов can_feed для проверки 20 литров: print(can_feed(1, 20, nodes, liquid_needed). В результате должна вернуться True, означающая, что 20 литров достаточно. Теперь нам известно, что 10 недостаточно, а 20 хватает. Давайте сужать этот диапазон далее. Попробуйте 15, на что должен вернуться False. Значит, 15 маловато. Теперь оптимальный ответ больше 15, но не больше 20. Попробуйте 18 — в этом случае жидкости окажется достаточно. А как насчет 17? Нет, 17 уже мало, как и 17.5 или 17.9, значит, оптимальное решение — 18. Этих результатов узконаправленного поиска достаточно, теперь можно их систематизировать.

ПОИСК РЕШЕНИЯ

Из условия задачи известно, что оптимальное значение не больше 2 миллиардов. Следовательно, решение находится в огромном пространстве поиска. Наша цель сократить это пространство максимально быстро, не тратя времени на пустые догадки. Промахнуться легко. Например, если начать с предположения 10, а оптимальное решение окажется равным двум миллиардам, тогда, по сути, это предположение следует считать промахом, исключающим из области поиска только значения от 0 до 10. Но 10 окажется отличным вариантом, если ответ будет равен, например, 8, потому что тогда первый же шаг сразу сократит диапазон до 0 — 10, и на поиск решения много времени не уйдет. Совершение таких выстрелов в небо себя не оправдывает, поскольку редкое везение не перекроет наиболее вероятный случай, когда такая догадка практически бесполезна. Именно поэтому, когда вас попросят отгадать число между 0 и 1000, вы вряд ли начнете с 10. Конечно же, если на такое предположение вам скажут «меньше», то вы очень обрадуетесь, но если ответом будет «больше», как скорее всего и получится, то можно считать, что первую попытку вы потратили зря. Чтобы гарантировать получение с каждой догадкой максимальной информации, мы всегда будем загадывать середину диапазона. Для этого нужно будет вести две переменные, low и high, которые будут хранить нижнюю и верхнюю границы текущего диапазона соответственно. Затем мы будем вычислять середину этого диапазона, mid, проверять допустимость mid, по результату обновляя low и high. Используем алгоритм двоичного поиска.

def solve(nodes, liquid_needed):
    low = 0
    high = 2000000000
    while high - low > 0.00001: # 1
        mid = (low + high) / 2 # 2
        if can_feed(1, mid, nodes, liquid_needed): # 3
            high = mid
        else:
            low = mid
    print(high) # 4

После определения функций и получения данных запустим решение: solve(nodes, liquid_needed). Важно инициализировать low и high так, чтобы в их диапазоне гарантированно содержалось оптимальное решение. Значение low будет постоянно меньшим или равным оптимальному решению, а high — большим или равным оптимальному решению. Начнем со значения low, равного 0. Поскольку каждому муравью требуется не менее 1 литра, 0 литров будет определенно меньше или равно оптимальному решению. Для high же стартовое значение установим как 2000000000, поскольку условие задачи гарантирует, что значение оптимального решения не может превышать этого числа.

1. Условие цикла while ведет к минимизации диапазона между low и high. Нам нужна точность выше четырех цифр после запятой, отсюда появляются четыре 0 после десятичной точки в 0.00001.
2. Первым делом в цикле вычисляется середина диапазона. Для этого мы берем среднее от low и high, сохраняя результат в mid.
3. Теперь пора проверить mid литров на допустимость с помощью can_feed. Если mid окажется допустимым числом, значит, угадывание значений выше mid бесполезно. Следовательно, мы устанавливаем high = mid, уменьшая максимум диапазона до mid. Если же mid окажется недопустимым вариантом, то бесполезно угадывать меньшие значения. Следовательно, мы устанавливаем low = mid, повышая минимум диапазона до mid.
4. По завершении цикла low и high окажутся очень близки. Я вывожу в конце high, но вывод low также вполне допустим.

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

«Кормление муравьев» относится к типу задач, для решения которых нет метода лучше двоичного поиска. Для них характерны две особенности:

• Особенность 1: сложность выбора метода решения, но простота проверки допустимости ответа. Для некоторых задач сложно определить алгоритм поиска оптимального решения. К счастью, во многих таких случаях значительно проще определять, является ли предлагаемое решение допустимым. Такова и была ситуация в задаче про муравьев: мы не знали, как найти оптимальное решение, но при этом видели, как определять, является ли некоторый объем жидкости допустимым.
• Особенность 2: четкое разделение решений на допустимые и недопустимые. Нам нужно, чтобы задача позволяла провести четкую черту, разделяющую допустимые и недопустимые решения. В задаче про муравьев недостаточные объемы жидкости были недопустимы, а избыточные — допустимы. То есть когда мы рассматривали значения объема, то могли установить для них диапазоны недопустимых и допустимых значений. После нахождения первого допустимого значения мы определяли диапазон, не содержащий недопустимых значений. Предположим, что выполняем проверку для 20 литров и выясняем, что этого мало. Следовательно, мы все еще не достигли допустимой части пространства поиска и нужно пробовать большие значения. Если же 20 литров оказывается достаточным, значит, мы находимся в допустимой части пространства и нужно пробовать меньшие значения.
• Если задача не отвечает второму требованию, то двоичный поиск будет бесполезен. Например, есть задачи, где меньшие значения являются недопустимыми, средние допустимыми, а большие снова недопустимыми. Однако вполне нормально, если область поиска будет переходить от допустимых значений к недопустимым, а не наоборот.

ВРЕМЯ ВЫПОЛНЕНИЯ АЛГОРИТМА

Пора окончательно разобраться, как мы использовали в задаче двоичный поиск: мы выполняли больше чем lb 2 000 000 000 итераций алгоритма, потому что не останавливались, когда ширина диапазона достигала 1. Остановка происходила только при достижении точности выше четырех знаков после запятой. При добавлении пяти нулей количество совершаемых итераций равно lb 200 000 000 000 000, который округляется до 48. Всего 48 итераций необходимо для получения решения с точностью выше четырех цифр после запятой из огромнейшего диапазона в триллионы значений!

В дереве из N узлов функция can_feed в задаче «Кормление муравьев» выполняется в линейном времени, то есть продолжительность ее выполнения пропорциональна n. Мы вызываем эту функцию lb(m × 104) раз, где m — ширина диапазона (два миллиарда в тестовых примерах). Это пропорционально lbm работы. Тогда в общей сложности выполняется n работы lbm раз. То есть время можно записать как O(nlbm). Оно не совсем линейно из-за множителя lbm, но двоичный поиск все равно очень быстр.

ВЫВОД

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

Таким образом, в задачах надо применять материал по другим алгоритмам. Для определения допустимости решений нередко требуется проявить изрядную креативность (к счастью, не столь изрядную, как для нахождения оптимальных решений). Верно, что двоичный поиск можно использовать для нахождения подходящего индекса массива в логарифмическом времени, но задачу про муравьев мы решали также с помощью двоичного поиска, а никакого массива задано не было. Не стоит ограничивать использование двоичного поиска только случаями, когда анализу подлежит массив. Этот алгоритм намного более гибок.

Задача 2. Прыжки вдоль реки

Рассмотрим задачу, в которой для определения допустимости решений потребуется жадный алгоритм.

Условие

Дана река длиной L, вдоль которой лежат камни. Один камень лежит в точке 0 (начало реки), другой в точке L (конец реки), а между ними находится еще n камней. Например, вдоль реки длиной 12 камни могут располагаться в следующих местах: 0, 5, 8 и 12. Корова начинает с первого камня (локация 0), перепрыгивает оттуда на второй камень, потом со второго на третий и так далее, пока не достигает последнего камня в точке L. Минимальная длина прыжка равна минимальному расстоянию между любыми двумя соседними камнями. В примере выше минимальное расстояние будет 3 (между точками 5 и 8). Фермеру Джону наскучили короткие прыжки коровы, и он хочет максимально увеличить их длину. Камни в точках 0 или L он убрать не может, но может удалить m других камней. Предположим, что в приведенном выше примере Джон может убрать один камень. В этом случае перед ним стоит выбор — убрать камень из точки 5 или 6. Если он уберет его из точки 5, то минимальное расстояние прыжка станет 4 (из 8 в 12). Однако если он уберет камень из точки 8, то получит минимальный прыжок большей длины (из 0 в 5). Задача — максимизация минимальной длины прыжка, которой может добиться фермер, убрав m камней.

Входные данные

Входные данные состоят из одного тестового примера, содержащего следующие строки: Три целых числа: L — протяженность реки; n — количество камней, не включая начальный и конечный камни; m — количество камней, которые Джон может убрать. Значение L может находиться в диапазоне от 1 до 1 000 000 000, n — от 0 до 50 000, а m — между 0 и n. n строк, каждая из которых указывает координату камня. При этом два камня в одном месте оказаться не могут.

Выходные данные

Требуется вывести максимально достижимое минимальное расстояние прыжка. Для примера выше выводом будет 5. Время на решение тестового примера — две секунды.

Решение

ЖАДНЫЙ АЛГОРИТМ

Сформулировать жадный алгоритм несложно, но не всегда легко определить правильное условие. Если он и подходят, то обычно по уникальным, характерным для конкретной задачи причинам. Эта задача одна из таких. Очень часто, чтобы отличить реально подходящий жадный алгоритм от кажущегося подходящим, требуется тщательное доказательство корректности. Пример, алгоритм Дейкстры. Как правило, специалисты относят этот алгоритм именно к жадным. Когда он объявляет о нахождении кратчайшего пути к узлу, то уже не возвращается к этому решению. Алгоритм окончательно утверждает найденное значение, и дальнейшее исследование пространства поиска не влияет на этот результат.

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

12 2 1
5
8

Камни расположены в точках 0, 5, 8 и 12. Убрать можно один. Самые близкие друг к другу камни расположены в 5 и 8, значит, жадное правило приведет к удалению одного из них. Камень в точке 8 находится от своего соседа справа на расстоянии 4. Камень в точке 5 находится от своего соседа слева на расстоянии 5. Согласно жадному правилу, удаляется камень из точки 8. В этом примере правило работает корректно.

Но приведём контрпример:

12 4 2
2
4
5
8

Камни располагаются в точках 0, 2, 4, 5, 8 и 12. Допускается убрать два. Жадный алгоритм определяет ближайшими камни в точках 4 и 5. Из них он удаляет камень 4, поскольку расстояние между 4 и 2 меньше, чем между 5 и 8. Остаются 0, 2, 5, 8 и 12. Теперь жадное правило определяет ближайшими камни в точках 0 и 2. Удалять стартовый камень нельзя, значит, удаляется камень из 2. Остаются 0, 5, 8 и 12. Минимальная длина прыжка здесь — 3. Однако в данном случае алгоритм с задачей не справился, потому что можно добиться, чтобы это расстояние равнялось 4. Для получения такого значения нужно удалить камни в точках 2 и 5. Так мы получим 0, 4, 8 и 12.

Что же пошло не так? Удалив камень в локации 4 на первом ходе, жадный алгоритм создал два прыжка с длиной три. На втором ходе он может убрать только один из этих двух, что никак не позволит получить итоговое минимальное расстояние больше трех.

ПРОВЕРКА ДОПУСТИМОСТИ

Всегда есть два ориентира используя двоичный поиск: большая простота проверки допустимости, чем определения оптимального решения; четкий переход в области поиска между допустимыми и недопустимыми решениями. Вместо поиска оптимального решения мы попробуем ответить на вопрос: можно ли добиться длины прыжка не менее d? Если нам удастся получить ответ, то можно будет использовать двоичный поиск для нахождения наибольшего допустимого значения d. Тестовый пример на котором остановились:

12 4 2
2
4
5
8

Камни расположены в точках 0, 2, 4, 5, 8 и 12. Убрать можно два. Вопрос: минимум сколько нужно убрать камней, чтобы длина прыжка получилась не менее 6? Разберем пример слева направо и проверим.

Камень в точке 0 трогать нельзя — так гласит условие задачи. Тогда, очевидно, у нас не остается выбора в отношении камня в точке 2: его необходимо убрать. Если этого не сделать, то минимальное расстояние между двумя камнями будет меньше 6. Итак, после этого остались камни в точках 0, 4, 5, 8 и 12. Теперь рассмотрим камень в точке 4 — нужно ли его оставить или убрать? В нашем случае его необходимо также убрать. Если этого не сделать, то минимальное расстояние между камнями составит 4, что меньше нужных нам 6. После его удаления остаются камни в точках 0, 5, 8 и 12. Камень в точке 5 тоже надо убрать, потому что расстояние от него до 0 равно всего лишь 5. Это третье удаление, после которого остаются камни в точках 0, 8 и 12. Теперь нужно удалить камень из точки 8. Он достаточно удален от 0, но недостаточно от 12. Итого четыре удаления, и в конечном итоге остаются камни в точках 0 и 12.

Итак, чтобы получить минимальное расстояние прыжка не меньше 6, требуется четыре удаления, но разрешено удалить всего два камня. В таком случае 6 не является допустимым решением. Оно слишком велико. Будет ли допустимым решением 3? То есть можно ли добиться минимального расстояния прыжка 3, удалив всего два камня? Камень в точке 0 остается, а камень в точке 2 нужно убрать. Это первое удаление, оставляющее камни в позициях 0, 4, 5, 8 и 12. Камень в точке 4 может остаться: он удален от 0 более чем на 3. А вот камень в точке 5 нужно убрать, потому что он слишком близок к камню в точке 4. Это второе удаление, после которого остаются заняты точки 0, 4, 8 и 12. Камень в точке 8 не мешает: он достаточно удален от камней в 4 и 12. Значит, здесь мы закончили: для получения минимального расстояния прыжка 3 потребовалось два удаления. Таким образом, 3 является допустимым решением.

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

def can_make_min_distance(distance, rocks, num_rocks, num_remove, length):
  removed = prev_rock_location = 0
  if length < distance:
    return False
  for i in range(num_rocks):
    cur_rock_location = rocks[i]
    if cur_rock_location - prev_rock_location < distance:
      removed += 1
    else:
      prev_rock_location = cur_rock_location
  if length - prev_rock_location < distance:
    removed += 1
  return removed <= num_remove

У этой функции пять параметров:

• distance — минимальное расстояние прыжка, которое проверяется;
• rocks — массив, содержащий координату каждого камня, кроме расположенных в начале и конце реки;
• num_rocks — количество камней в массиве rocks;
• num_remove — количество камней, которые можно убрать;
• length — длина реки.

Эта функция возвращает True, если distance оказывается допустимым решением, и False, если нет. Переменная prev_rock_location отслеживает координату последнего нетронутого камня. Внутри цикла for переменная cur_rock_location содержит координату камня, рассматриваемого в данный момент. Далее идет проверка, определяющая, нужно ли оставить или удалить текущий камень. Если он находится слишком близко к предыдущему, то мы его удаляем и увеличиваем количество удалений на один. В противном случае текущий камень остается, и соответствующим образом обновляется prev_rock_location. По завершении цикла мы получаем количество камней, которое нужно удалить. Хотя не совсем. Ещё нужно проверить, не находится ли предпоследний камень слишком близко к концу реки. Если да, то он удаляется (не беспокойтесь о возможном удалении камня в точке 0. Если действительно удалить все камни, то prev_rock_location окажется равным 0. Однако length – 0 < distance не может быть верно. В противном случае сработала бы инструкция if еще в начале функции). Итак, условие расстояния прыжка между камнями соблюдено, причем мы удалили заданное число камней.

Прежде чем продолжать, давайте выполним проверку на допустимость. Ниже представлен тест для примера:

rocks = [2, 4, 5, 8];
print(can_make_min_distance(6, rocks, 4, 2, 12))

Можно ли достичь минимальной длины прыжка в шесть единиц, удалив два камня? Ответ «нет», значит, в выводе должен отобразиться False(ложно). Измените первый параметр с 6 на 3, и теперь вопрос ставится о возможности получения минимальной длины в три единицы. Запустите программу, и на этот раз в выводе отобразится True (верно). Превосходно: теперь у нас есть способ проверки допустимости. Время задействовать двоичный поиск для нахождения оптимального решения.

ПОИСК РЕШЕНИЯ

Для использования двоичного поиска мы адаптируем код из задачи 1 в «Кормлении муравьев» требовалось достичь точности выше четырех знаков после запятой. Здесь же нам нужно оптимизировать количество камней, выражаемое целочисленным значением. Так что вычисления будут останавливаться при целых значениях high и low.

def solve(rocks, num_rocks, num_remove, length):
  low = 0
  high = length + 1
  while high - low > 1:
    mid = (low + high) // 2
    if can_make_min_distance(mid, rocks, num_rocks, num_remove, length):
      low = mid
    else:
      high = mid
  print(low)

Минимальное расстояние прыжка low, равное нулю, всегда достижимо и допустимо и high точно недопустимо: нельзя прыгнуть на длину length + 1. Далее нужно выяснить, что делать с этими двумя возможностями в цикле. В каждой итерации мы вычисляем среднюю точку диапазона mid и используем вспомогательную функцию для проверки ее допустимости. Если mid окажется допустимо, то можно установить low = mid. Потому что low и все, что левее, является допустимым. Если же mid недопустимо, то можно установить high = mid. Потому что high и все правее него значения являются недопустимыми. Таким образом, в обоих случаях истинность инварианта сохраняется. Мы видим, что никакой элемент кода не может повлиять на инвариант, а значит, можно спокойно наконец выводить low по завершении цикла.

СЧИТЫВАНИЕ ВХОДНЫХ ДАННЫХ

Осталось только считать входные данные и вызвать solve:

rocks = []
length, num_rocks, num_remove = map(int, input().split())
for _ in range(num_rocks):
  rocks.append(int(input()))
rocks.sort()
solve(rocks, num_rocks, num_remove, length)

Мы анализировали эту задачу, рассматривая координаты камней слева направо, то есть от наименьшего значения к наибольшему. Однако во входных данных они могут быть представлены в любом порядке, так как в условии задачи последовательность не гарантируется. Про алгоритмы сортировки нужно давать описание отдельно. Здесь же скажем что воспользуемся стандартным методом сортировки списков в Python sort(). Затем вызывается solve со списком упорядоченных камней.

Задача 3. Качество жизни

Рассмотрим задачу, в которой для определения допустимости решений потребуется динамическое программирование. Это задача из чемпионата мира по программированию (IOI 2010).

Условие

Город состоит из прямоугольной сетки кварталов. Каждый квартал обозначается координатами строки и столбца. Всего есть r строк, пронумерованных от 0 до r – 1 сверху вниз, и c столбцов, пронумерованных от 0 до с – 1 слева направо. Каждому квадрату присвоен индивидуальный ранг качества в диапазоне от 1 до rc. К примеру, если дано семь строк и семь столбцов, то рангами кварталов будут числа между 1 и 49. Пример схемы города дан в таблице ниже.

Средний ранг качества прямоугольника — это ранг качества, относительно которого другие ранги делятся на две равные половины — с меньшими и большими значениями. К примеру, рассмотрим прямоугольник размером пять строк на три столбца (5 × 3) в верхнем левом углу таблицы. Он содержит 15 рангов качества: 48, 16, 15, 20, 11, 36, 22, 39, 30, 14, 35, 2, 32, 37 и 21. Средним рангом здесь выступает 22, потому что семь чисел меньше 22, а другие семь — больше.

Нам будут даны целые числа h и w, указывающие высоту (количество строк) и ширину (количество столбцов) прямоугольников. Задача — определить минимальный средний ранг качества любого прямоугольника с h строк и w столбцов. Предположим, что h равна 5, а w равна 3. Тогда для города в таблицы средним рангом качества будет определено значение 13. Прямоугольник со средним рангом качества 13 — этот тот, у которого верхний левый угол образует клетка (1, 3), а правый нижний угол — (5, 5).

Входные данные

Все необходимые данные необходимо подставить в параметры функции. Вот функция:

def rectangle(r, c, h, w, q):

Здесь r и c — количество строк и столбцов в схеме соответственно. Аналогичным образом h и w — количество строк и столбцов в рассматриваемых прямоугольниках соответственно. h будет не больше r, а w не больше c. Также гарантируется, что h и w являются нечетными (произведение двух нечетных чисел — нечетное число, поэтому и hw, количество кварталов в рассматриваемом прямоугольнике, будет нечетным. Средний ранг качества в этом случае можно определить точно. Если же у нас будет четное количество рангов качества, например четыре ранга — 2, 6, 4 и 5, то среднее значение придется выбирать между 4 и 5. Автор задачи избавил нас от этого выбора). Заключительный параметр q указывает ранги качества кварталов. К примеру, q[2][3] определяет значение ранга квартала в строке 2, ряду 3. Обратите внимание, что максимальное количество и строк, и столбцов в городе — 3001.

Выходные данные

Вернуть минимальный средний ранг качества. Время на решение тестового примера — 10 секунд.

Решение

УПОРЯДОЧИВАНИЕ ПРЯМОУГОЛЬНИКОВ

Во многом мы будем использовать двумерный массив q. Предположим, что даны координаты верхнего левого и правого нижнего углов прямоугольника и нужно определить средний ранг качества его кварталов. Как это сделать? Прежде чем ответить на этот вопрос создадим саму таблицу с данными(двумерный список) по нашему примеру и вызов функции rectangle.

q = [[48, 16, 15, 45, 40, 28, 8], 
         [20, 11, 36, 19, 24, 6, 33], 
         [22, 39, 30, 7, 9, 1, 18], 
         [14, 35, 2, 13, 31, 12, 46], 
         [32, 37, 21, 3, 41, 23, 29], 
         [42, 49, 38, 10, 17, 47, 5], 
         [43, 4, 34, 25, 26, 27, 44]]
result = rectangle(7, 7, 5, 3, q)
print(result)

Способ 1

Здесь поможет упорядочивание. Нужно просто отсортировать ранги качества от меньших к большим и затем выбрать элемент со средним индексом. Рассмотрим, к примеру, все те же 15 рангов качества: 48, 16, 15, 20, 11, 36, 22, 39, 30, 14, 35, 2, 32, 37 и 21. Если их упорядочить, то получится: 2, 11, 14, 15, 16, 20, 21, 22, 30, 32, 35, 36, 37, 39 и 48. Всего здесь 15 рангов, значит, нужно взять восьмой (22), который и будет средним. Есть и более быстрые алгоритмы для непосредственного нахождения среднего значения без необходимости упорядочивания. Сортировка — алгоритм, которому для нахождения среднего значения требуется O(n logn) времени. Существует и более сложный алгоритм для нахождения среднего со временем O(n). Но здесь мы не станем его использовать. Реализуемый в этом способе процесс будет настолько медленным, что никакое улучшение алгоритма поиска среднего значения все равно не поможет.

Итак, выше напишем функцию с кодом нахождения среднего в заданном прямоугольнике:

def median(top_row, left_col, bottom_row, right_col, q):
        cur_rectangle = []
        for i in range(top_row, bottom_row + 1):
                for j in range(left_col, right_col + 1):
                        cur_rectangle.append(q[i][j])
        cur_rectangle.sort()
        return cur_rectangle[len(cur_rectangle) // 2]

Первые четыре параметра median очерчивают прямоугольник, указывая координаты его левого верхнего и правого нижнего углов. Заключительный параметр q содержит ранги качества. Для хранения рангов качества прямоугольника используется одномерный массив cur_rectangle. Вложенные циклы for проходят через каждую ячейку (квартал) прямоугольника и добавляют соответствующий ранг качества в cur_rectangle. После сбора всех рангов можно вызвать встроенный метод sort(). Далее нам будет в точности известно, где находится среднее значение — в середине массива, — и мы просто его возвращаем. Вооружившись этой функцией, можно перебирать все варианты прямоугольника, и в конце определить тот, чей средний ранг качества окажется наименьшим. Код поиска наименьшего среднего значения среди возможных прямоугольников:

def rectangle(r, c, h, w, q):
    best = r * c + 1
    for top_row in range(r - h + 1):
        for left_col in range(c - w + 1):
            bottom_row = top_row + h - 1
            right_col = left_col + w - 1
            res = median(top_row, left_col, bottom_row, right_col, q)
            if res < best:
                best = res
    return best

В переменной best сохраняется наилучшее (то есть наименьшее) среднее значение, найденное до сих пор. Эту переменную мы изначально устанавливаем с большим значением, которое превосходит среднее любого возможного прямоугольника. Невозможно, чтобы среднее прямоугольника равнялось r * с + 1, это бы означало, что половина его рангов качества больше r * c. Но, согласно условию задачи, никакие ранги качества не могут быть больше r * c. Вложенные циклы for рассматривают все возможные координаты верхнего левого угла прямоугольника. Так мы получаем верхнюю строку и левый столбец, но для вызова median нам также нужна нижняя строка и правый столбец. Чтобы вычислить координату нижней строки, мы берем номер верхней строки, прибавляем h (количество строк в рассматриваемых прямоугольниках), а затем вычитаем 1. Здесь очень просто допустить промах на единицу, но вычитание единицы необходимо. Если верхняя строка имеет номер 4, а h равна 2, то нам нужно, чтобы номер нижней строки был равен 4 + 2 – 1 = 5. Если же сделать этот номер равным 4 + 2 = 6, то у нас получится прямоугольник с тремя строками вместо требуемых двух. Аналогичным образом вычисляется номер правого столбца. Получив все четыре координаты, мы вызываем median для вычисления среднего значения ранга прямоугольника. Если в итоге обнаруживается лучшее значение, то оставшаяся часть кода обновляет best. На этом текущее решение закончено.

Но чтобы понять, почему наш код столь медленный, рассмотрим пример, в котором r и с представлены числом m. Для демонстрации наихудшего случая мы возьмем h и w, равные m/2 (нам не нужно, чтобы прямоугольники получались излишне большими, иначе их будет немного. Нам также не нужно, чтобы они были слишком маленькими, так как тогда каждый будет легко обработать). Самая медленная часть функции median — вызов sort(). Она получает массив с m/2 × m/2 = m*m/4 значений. Для обработки массива из n значений sort() совершает nlogn шагов. Замена n на m*m/4 дает оценку времени Итак, выполнение происходит уже медленнее, чем в квадратичном случае, — а мы ведь вычислили среднее значение только для одного прямоугольника. Функция rectangle вызывает median всего m*m/4 раз, значит, общее время выполнения составляет При таком числе операций данное решение подходит только для примеров с очень малым количеством данных. В нашем решении присутствуют два узких места. Первое — это упорядочивание каждого прямоугольника. Второе — это создание массива cur_rectangle с нуля для каждого прямоугольника. Использование двоичного поиска решает первую проблему, а динамическое программирование — вторую.

ДВОИЧНЫЙ ПОИСК

Почему нам стоит рассчитывать на то, что двоичный поиск обеспечит в данном случае прирост скорости? Во-первых, выше показано, что прямой поиск очень затратен. Подход, который опирался на сортировку, оказался медленнее m*m*m*m. Во-вторых, это еще один пример задачи, где сначала идут все недопустимые решения, а за ними уже допустимые. Предположим, что нет такого прямоугольника, чей средний ранг качества имеет значение менее 6. Тогда не будет смысла искать прямоугольники со средним качеством 5, 4 или любым меньшим значением. И наоборот, предположим, я скажу, что есть прямоугольник со средним рангом качества 5 или меньше. Теперь не будет смысла искать прямоугольники со средним рангом качества 6, 7 или любым другим, чье значение выше 5. Так задается область двоичного поиска.

В задаче с прыжками вдоль реки небольшие значения были допустимыми, а большие недопустимыми. Здесь же у нас обратный случай: небольшие значения оказываются недопустимыми, а большие допустимыми. Следовательно, нам придется изменить инвариант, сменив расположение допустимых и недопустимых частей пространства решений. И вот какой инвариант мы используем: low и все, что меньше, будет недопустимо; high и все, что больше, — допустимо. Таким образом, по завершении нужно возвращать high, поскольку таково будет наименьшее допустимое значение.

def rectangle(r, c, h, w, q):
    low = 0
    high = r * c + 1
    while high - low > 1:
        mid = (low + high) // 2
        if can_make_quality(mid, r, c, h, w, q):
            high = mid
        else:
            low = mid
    return high

Для завершения нужно проверить допустимость с помощью can_make_quality.

ПРОВЕРКА ДОПУСТИМОСТИ

Вот функция проверки допустимости: def can_make_quality(quality, r, c, h, w, q):. Нам достаточно будет определять, не превосходит ли среднее значение некоторого прямоугольника пороговое значение ранга quality. Это более простая задача, для которой этап сортировки необязателен. Конкретные значения нам больше не важны, принципиально только соотношение между каждым значением и quality. Поэтому мы заменим все меньшие или равные quality значения на –1, а все большие — на 1. Затем мы сложим эти –1 и 1 для заданного прямоугольника. Если в итоге значений –1 получится столько же или больше, чем значений 1 (т.е. относительно quality число меньших значений будет превосходить количество больших), то их сумма будет нулевой или отрицательной и мы сделаем вывод, что средний ранг качества данного прямоугольника равен quality или меньше него.

Рассмотрим пример, в котором снова возьмем 15 рангов для прямоугольника 5 × 3 из верхнего левого угла таблицы условия: 48, 16, 15, 20, 11, 36, 22, 39, 30, 14, 35, 2, 32, 37 и 21. Сравним средний ранг качества этого прямоугольника с 16. Для этого возьмем каждое значение и, если оно меньше или равно 16, заменим его на –1, а если больше 16, то на 1. Получатся следующие значения: 1, –1, –1, 1, –1, 1, 1, 1, 1, –1, 1, –1, 1, 1 и 1. Их сложение даст 5. Это означает, что значений, превосходящих 16, на пять больше, чем меньших или равных этому числу. Это, в свою очередь, говорит о том, что среднее значение 16 или меньше для данного прямоугольника невозможно. Если бы мы хотели узнать, является ли допустимым среднее значение 30, то также узнали бы об этом, заменив числа на –1 и 1: 1, –1, –1, –1, –1, 1, –1, 1, –1, –1, 1, –1, 1, 1 и –1. Сложение этих значений даст –3. Значит, 30 является допустимым средним. Важно отметить, что решение о допустимости/недопустимости принимается без предварительного упорядочивания. Нам нужно перебрать каждый прямоугольник, проверяя, содержит ли он средний ранг качества, равный quality или меньше него. Этот процесс реализуется в коде ниже:

def can_make_quality(quality, r, c, h, w, q):
    zero_one = [row[:] for row in q]
    for i in range(r):
        for j in range(c):
            if q[i][j] <= quality:
                zero_one[i][j] = -1
            else:
                zero_one[i][j] = 1
    for top_row in range(r - h + 1):
        for left_col in range(c - w + 1):
            bottom_row = top_row + h - 1
            right_col = left_col + w - 1
            total = 0
            for i in range(top_row, bottom_row + 1):
                for j in range(left_col, right_col + 1):
                    total = total + zero_one[i][j]
            if total <= 0:
                return True
    return False

Нельзя просто заместить массив q значениями –1 и 1, потому что тогда мы не сможем использовать исходные ранги качества для последующей проверки других значений quality. Следовательно, здесь для хранения –1 и 1 создается новый массив zero_one. Обратите внимание, что он заполняется на основании того, является ли каждое значение меньшим или равным (–1) либо большим (1), чем пороговый параметр quality. Далее мы проходим по каждому прямоугольнику так же. При этом суммируются все его –1 и 1, и возвращается True (верно), если средний ранг качества оказывается достаточно мал.

Вот мы и избавились от сортировки — искусно, не так ли? Этот прием очень важен для решения нашей задачи, но недостаточен. Если посчитать вложенные циклы, то окажется, что у нас их целых четыре. Мы обнаружили, что решение без двоичного поиска оказалось очень медленным. Здесь же оценка скорости проверки допустимости все еще равна mmm*m. Умножьте ее на логарифмический множитель, характеризующий двоичный поиск, и возникнет вопрос: а добились ли мы хоть какого-нибудь прогресса? Но мы добились! Просто он скрыт за слишком большим числом вложенных циклов, производящих чересчур много вычислений. Оставшуюся часть пути нам поможет пройти динамическое программирование.

УСКОРЕННАЯ ПРОВЕРКА ДОПУСТИМОСТИ

Предположим, что дана таблица(как в условии задачи выше) и требуется выяснить, содержит ли какой-либо из прямоугольников 5 × 3 средний ранг качества 16 или менее. Изменив все значения, которые меньше или равны 16, на –1, а все значения больше 16 — на 1, получим следующую таблицу:

Можно начать с суммирования элементов прямоугольника 5 × 3 с координатами верхнего левого угла (0, 0). Сумма значений этого прямоугольника равна 5. Далее вычислим сумму элементов прямоугольника 5 × 3 с координатами верхнего левого угла (0, 1). Ранее мы бы в данном случае сложили все 15 чисел. Однако тогда мы не сможем воспользоваться результатами вычислений суммы первого прямоугольника. Действительно, во втором прямоугольнике есть 10 общих значений с первым. Нам нужно избежать подобного дублирования работы как для этого, так и для всех остальных прямоугольников. Исключение повторения работы здесь подразумевает эффективное выполнение так называемого запроса суммы двумерного диапазона. Одномерный случай реализуется по тем же принципам, но проще, поэтому сперва мы вкратце изучим его, а потом уже вернемся к завершению задачи.

Запрос суммы одномерного диапазона

Рассмотрим одномерный массив:

Если требуется найти сумму элементов массива от индекса 2 до индекса 5, то можно напрямую суммировать значения в этом диапазоне: 15 + 9 + 12 + 4 = 40. Это не очень быстро, и будет совсем печально, если потребуется найти сумму всего массива. Однако если требуется ответить всего на несколько таких запросов, то этот вариант приемлем, и можно каждый раз суммировать соответствующие значения. Теперь представим, что мы получаем сотни или даже тысячи подобных запросов. Тогда есть смысл единожды проделать предварительную работу, которая позволит отвечать на них быстрее. Рассмотрим запрос от индекса 2 до 5. Что, если предварительно найти сумму значений от индекса 0 до 5? Она равна 48. Это не нужный нам ответ, которым является 40, однако здесь удобен тот факт, что 48 находится от него недалеко. Ошибочно это значение лишь потому, что включает индексы 0 и 1, которые теперь нужно исключить. Это можно быстро сделать при условии нахождения их суммы, которая равна 8. Если вычесть 8 из 48, то получится нужная сумма 40. В таком случае нам нужен новый массив, тот, где индекс i содержит сумму всех значений от индекса 0 до i. Этот новый массив добавляется в строку частичной суммы в следующей таблице:

Теперь можно быстро отвечать на любой запрос, используя массив частичных сумм: для вычисления суммы диапазона от индекса a до b нужно взять значение в индексе b и вычесть из него значение в индексе a – 1. Для диапазона от 2 до 5 получится 48 – 8 = 40, а от 1 до 6 получится 59 – 6 = 53. Теперь на получение ответов независимо от величины диапазона требуется одинаковое количество времени, причем для этого достаточно было сделать всего один предварительный проход по массиву.

Запрос суммы двумерного массива

Вернемся в двумерный мир наших рангов качества. Суммирование элементов каждого прямоугольника — слишком медленный процесс, поэтому мы расширим освоенный на одномерном примере прием до двух измерений. В частности, потребуется создать новый массив, в котором индекс (i, j) является суммой элементов прямоугольника, координаты верхнего левого угла которого — (0, 0), а нижнего правого — (i, j). Еще раз взглянем на таблицу:

Соответствующий ей массив "частичных сумм" представлен в таблице ниже:

Для начала убедимся, что правильно понимаем предоставляемые этим массивом данные, а потом уже перейдем к рассмотрению его построения. Значение в строке 4 и столбце 2 указывает сумму чисел в прямоугольнике, координаты верхнего левого угла которого — (0, 0), а правого нижнего — (4, 2). Как вычислить значение для ячейки (4, 2) на основе других ранее вычисленных значений? Нужно начать со значения из ячейки таблицы -1 и 1 и прибавить все числа выше, а также левее нее. Это можно сделать, грамотно используя массив из таблицы "частичных сумм", как будет показано в таблице ниже.

Необходимо начать с 1, затем охватить ячейки, включающие x (выше), а также ячейки, включающие y (слева), после чего вычислить сумму. Сумма ячеек, включающих x, представлена элементом (3, 2). Сумма ячеек, включающих y, аналогичным образом представлена элементом (4, 1). Однако их сложение приводит к двойному подсчету ячеек xy (расположенных выше и левее). Но это не проблема, потому что элемент (3, 1) содержит сумму именно этих ячеек и компенсировать двойной подсчет можно его вычитанием. Таким образом, получается 1 + 2 + 4 – 2 = 5, что нам и требовалось. При условии продвижения сверху вниз и слева направо можно строить этот массив с помощью всего двух операций сложения и одной операции вычитания для каждой ячейки.

Теперь мы знаем, как создавать массив "частичных сумм", но что это дает? Это позволяет быстро вычислять сумму элементов любого прямоугольника. Предположим, что нам нужна сумма для прямоугольника, координаты левого верхнего угла которого — (1, 3), а правого нижнего — (5, 5). Нельзя просто использовать значение 10 в ячейке (5, 5). Помимо суммы ячеек нужного прямоугольника оно включает также элементы, находящиеся выше и слева. Однако, как и в одномерном случае, можно вычислить необходимое значение, чтобы оно включало элементы только интересующего нас прямоугольника. Данная операция отражена в таблице ниже, где ячейки нужного прямоугольника отмечены звездочками. На этот раз нужно вычесть ячейки, включающие x, и ячейки, включающие y. Сумму ячеек x содержит ячейка (0, 5), а ячеек y — (5, 2). Но вычитанием обеих этих сумм мы дважды вычтем ячейки xy, поэтому нужно прибавить значение ячейки (0, 2). Таким образом, получается 10 – 2 – 8 + (–1) = –1, что и является суммой ячеек нужного прямоугольника.

Теперь можно объединить все воедино: идею с –1 и 1, построение массива частичных сумм и его использование для быстрого получения сумм прямоугольников. Соответствующий код дан ниже:

def can_make_quality(quality, r, c, h, w, q):
    zero_one = [row[:] for row in q]
    sum_q = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
    for i in range(r):
        for j in range(c):
            if q[i][j] <= quality:
                zero_one[i][j] = -1
            else:
                zero_one[i][j] = 1
    for i in range(1, r + 1):
        for j in range(1, c + 1):
            sum_q[i][j] = zero_one[i - 1][j - 1] + sum_q[i - 1][j] + sum_q[i][j - 1] - sum_q[i - 1][j - 1]
    for top_row in range(1, r - h + 2):
        for left_col in range(1, c - w + 2):
            bottom_row = top_row + h - 1
            right_col = left_col + w - 1
            total = sum_q[bottom_row][right_col] - sum_q[top_row-1][right_col] - sum_q[bottom_row][left_col-1] + sum_q[top_row-1][left_col-1]
            if total <= 0:
                return True
    return False

Вначале создается массив zero_one, в точности как это делалось ранее в коде выше. Вторым шагом идет создание массива частичных сумм sum_q. Мы будем использовать индексы, начинающиеся с 1, а не с 0, чтобы не пришлось беспокоиться о возможном выходе за границы массива при обработке ячеек в строке 0 или столбце 0. На третьем шаге массив частичных сумм используется для быстрого вычисления суммы каждого прямоугольника. Обратите внимание, что любой прямоугольник здесь суммируется за одинаковое время. На втором шаге мы выполнили предварительную обработку, которая в дальнейшем позволит узнать сумму для любого прямоугольника, не тратя времени на сложение всех его элементов. По сравнению с кодом ранее мы удалили из циклов for два уровня вложения. Следовательно, у нас получился алгоритм который достаточно быстр. Попробуйте! А потом советую немного передохнуть, так как нас ждет еще одна серьезная задача.

Задача 4. Двери пещеры

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

Условие

Вы стоите перед входом в длинную узкую пещеру, через которую необходимо пробраться и достичь выхода. На пути нужно пройти через n дверей: первая — это дверь 0, вторая — дверь 1 и т. д. Каждая дверь может быть открыта либо закрыта. Через открытые двери можно пройти, через закрытые — нельзя. Таким образом, если двери 0 и 1 открыты, а дверь 2 закрыта, то можно пройти только до двери 2, причем вы не видите состояния следующих за ней дверей. У входа в пещеру установлена панель с n рычагов. Как и двери, рычаги пронумерованы, начиная с 0. Каждый из них может быть в верхнем (0) или нижнем (1) положении. При этом каждый рычаг связан с одной дверью, определяя, закрыта она или открыта. Если рычаг установлен в правильное положение, то соответствующая дверь открыта. В противном случае эта дверь закрыта. Вам не известны ни связь рычагов с дверьми, ни правильные положения рычагов. К примеру, возможно, что рычаг 0 связан с дверью 5 и для ее открывания должен находиться в нижнем положении, а рычаг 1 связан с дверью 0 и для ее открывания должен находиться в верхнем положении. Можно устанавливать рычаги в желаемое положение, а затем проходить в пещеру для определения первой закрытой двери и возвращаться. При этом запаса сил вам хватит максимум на 70 000 таких циклов. Цель — определить верное положение(0 или 1) каждого рычага и связанную с ним дверь. Нужно написать следующую функцию: exploreCave(n). Здесь n является количеством дверей и рычагов (от 1 до 5000). Для реализации этой функции нужно будет вызвать две функции, предоставленные судьей. Они будут описаны далее.

Входные данные

Из стандартного ввода мы ничего не считываем. Единственный способ узнать исходные данные — это вызвать предоставленную судьей функцию tryCombination. Вот ее сигнатура: tryCombination(switch_positions). Параметр switch_positions является массивом с длиной n целых чисел, указывающим положение (0 или 1) каждого рычага. То есть switch_positions[0] определяет положение рычага 0, switch_positions[1] — положение рычага 1 и т. д. Функция tryCombination симулирует ситуацию, в которой мы устанавливаем рычаги в switch_positions и проходим по пещере до первой закрытой двери. Она возвращает номер первой закрытой двери либо -1, если все двери открыты.

Выходные данные

В стандартный вывод запись не производится. Вместо этого мы отправляем ответ через вызов функции answer, также предоставленной судейским ресурсом. Вот ее сигнатура: answer(switch_positions, door_for_switch). У нас есть только одна попытка: при вызове answer наша программа уничтожается, так что правильный ответ следует отправлять с первого раза. Параметр switch_positions — массив, содержащий предлагаемые нами положения рычагов в том же формате, что и tryCombination. Параметр door_for_switch содержит предлагаемые нами связи между рычагами и дверьми: door_for_switch[0] указывает дверь, связанную с рычагом 0, door_for_switch[1] указывает дверь, связанную с рычагом 1, и т. д. В данном случае ограничено не время, а количество вызовов tryCombination, которых допускается сделать на более 70 000. В случае превышения этого значения программа завершается.

Решение

Автор задачи разделил ее на пять подзадач. Пятая подзадача — это задача в общем виде. Другие подзадачи имеют дополнительные ограничения, упрощая решение. Мне нравится, когда авторы задач используют подзадачи, особенно если у меня возникают сложности с поиском решения. В таких случаях можно поочередно разделываться с каждой подзадачей, постепенно дорабатывая решение, пока не будет решена вся задача. Первая подзадача состоит в решении варианта, где каждый рычаг i связан с дверью под номером i. Это значит, что рычаг 0 связан с дверью 0, рычаг 1 с дверью 1 и т. д. Нам же нужно определить верное положение (0 или 1) для каждого рычага.

Начнем с подзадачи 1, чтобы иметь возможность вызывать судейские функции tryCombination и answer, а уже потом приступим к другим частям основной задачи. У нас нет доступа к судейским функциям, но мы хотим протестировать свою работу локально. Можно запросить в Google «IOI 2013 tasks» и найти тестовые данные с шаблонами для задачи Cave. Вот пример:

Данные оценщика для тестового примера:

4
1110
3102

• 1 строка: N – количество дверей и переключателей;
• 2 строка: S[0]...S[3] – правильное положение переключателей с индексами 0-3;
• 3 строка: D[0]...D[3] – дверь, к которой подключен переключатель с индексами 0-3;

ПРИМЕР СЕАНСА

Эта задача стандартно решается на C/C++ мы попробуем её также решить, но на Python.

Напишем код для подзадачи 1:

def exploreCave(n):
  switch_positions = [0 for _ in range(n)]
  door_for_switch = [i for i in range(n)]
  for i in range(n):
    result = tryCombination(switch_positions)
    if result == i: # дверь i закрыта
      switch_positions[i] = 1
  answer(switch_positions, door_for_switch)

Вначале положение каждого рычага устанавливается на 0, и дверь i связывается с рычагом i. Положения рычагов мы будем обновлять при необходимости, а вот связь рычаг–дверь в данном случае (согласно ограничениям подзадачи) трогать не потребуется. Цикл for перебирает каждый рычаг. Его задача — определить, должен ли текущий рычаг остаться в положении 0 или переключиться в положение 1. Рассмотрим первую итерацию, когда i равно 0. Вначале происходит вызов tryCombination, которая возвращает номер первой закрытой двери. Если возвращается 0, то рычаг 0 установлен неправильно. Если этот рычаг будет установлен верно, то дверь 0 окажется открыта и tryCombination вернет ненулевой номер двери. Если дверь 0 оказывается закрыта, мы изменяем положение рычага 0 с 0 на 1. В результате дверь 0 открывается, и можно продвигаться к двери 1. На следующем шаге i становится равной 1 и снова вызывается tryCombination. Результат 0 в данном случае точно не вернется, потому что код уже проделал работу, гарантирующую открывание двери 0. Если возвращается 1, это означает, что дверь 1 закрыта и нужно изменить положение рычага 1 с 0 на 1. Обобщая, можно сказать, что в начале новой итерации цикла все двери до i (включая i – 1) открыты. Если дверь i закрыта, то мы изменяем положение рычага i с 0 на 1. Если дверь i уже открыта, значит, рычаг i установлен верно. Закончив второй цикл for, мы выяснили верное положение каждого рычага. Этот ответ мы передаем судейскому ресурсу через вызов функции answer.

Итак, в подзадаче 1 мы точно узнаём, какая дверь с каким рычагом связана. Для определения данного соответствия не требовалось выполнять поиск, но для решения всей задачи поиск нам понадобится, так как неизвестно, какой рычаг за какую дверь отвечает. Мы начнем с закрывания двери 0, после чего займемся перебором рычагов, чтобы открыть ее. Для этого будем последовательно изменять положение рычагов, проверяя, открылась или нет дверь 0. Если нет, то рычаг выбран ошибочно. Если же дверь 0 открылась, значит, связанный с ней рычаг найден. С этого момента дверь 0 остается открытой, и тот же процесс повторяется для двери 1: вначале она закрывается, а затем перебираются оставшиеся рычаги в поиске того, который ее откроет.

Начнем с нового кода exploreCave, приведенного ниже. Он краток, потому что перекладывает поиск на вспомогательную функцию.

def exploreCave(n):
  switch_positions = [0 for _ in range(n)]
  door_for_switch = [-1 for i in range(n)]
  for i in range(n):
    set_a_switch(i, switch_positions, door_for_switch, n)
  answer(switch_positions, door_for_switch)

Как и при решении подзадачи 1, каждый элемент switch_positions будет хранить значения указывающие положение каждого рычага. Положение всех рычагов устанавливается как 0(если рычаг уже связан с дверью, его положение больше никогда не должно меняться). Массив door_for_switch указывает, какая дверь с каким рычагом соединена. Изначально каждый элемент door_for_switch инициализируется как -1, поскольку все связи дверей с рычагами неизвестны. Когда становится известна связанная с рычагом i дверь, door_for_switch[i] должен будет обновляться.

А вот контрольный вопрос: если door_for_switch[5] равна 6, то что это значит? Значит ли это, что рычаг 5 связан с дверью 6 или что дверь 5 связана с рычагом 6? Первый вариант! Запомните это, прежде чем продолжать.

Для каждой двери i мы вызываем вспомогательную функцию set_a_switch. Ее задача — выполнить поиск по рычагам и найти связанный с дверью i. Она также определяет, должен рычаг находиться в положении 0 или 1.

ДВОИЧНЫЙ ПОИСК

Числа 5000 (максимальное количество дверей) и 70 000 (максимум попыток подбора) тонко намекают на необходимость применения для решения стратегии двоичного поиска. Обратите внимание, что lb5000 округляется до 13. Если мы найдем способ использовать двоичный поиск, то он сможет подбирать верный рычаг для текущей двери всего за 13 шагов, но никак не за 5000(линейный поиск). Если на каждую дверь нам потребуется по 13 шагов, то при 5000 дверей получится 13 × 5000 = 65 000 шагов в общем. Таким образом, мы впишемся в лимит 70 000.

Как же здесь использовать двоичный поиск? Процесс должен позволить отбрасывать на каждом шаге половину диапазона рычагов. Поясню идею на примере. Предположим, что у нас восемь дверей и восемь рычагов, а также что дверь 0 в текущий момент закрыта. Если мы переключим рычаг 0 и дверь 0 не откроется, то из этого мы поймем немногое: только то, что рычаг 0 не связан с дверью 0 (все равно что сказать «1» при угадывании загаданного кем-то числа между 1 и 1000). Более удачной идеей будет переключить половину рычагов, так что давайте переключим рычаги 0, 1, 2 и 3. Независимо от того, как это повлияет на дверь 0, мы узнаем уже очень многое. Если дверь по-прежнему останется закрыта, то рычаги с 0 по 3 к ней отношения не имеют и можно сосредоточиться на оставшейся половине рычагов с 4 по 7. Если же дверь 0 откроется, то станет ясно, что с ней связан один из рычагов с 0 по 3 и нужно более плотно сосредоточиться именно на них. За один шаг мы сразу отсекаем половину диапазона. Продолжая таким же путем дальнейший поиск, мы в конечном итоге определим рычаг, связанный с дверью 0 (и его положение). Предположим, что проделываем весь этот путь, снова и снова уменьшая диапазон рычагов в два раза, пока не останется всего один рычаг. Допустим, что связанным с дверью 0 оказался рычаг 6. Тогда мы установим его в положение, при котором дверь 0 будет открыта. В этом положении он и останется. Когда далее мы перейдем к обработке двери 1 или любой другой двери впоследствии, то предусмотрительно не станем менять положение рычага 6.

Теперь я могу представить решение для этой задачи, основанное на двоичном поиске. Код set_a_switch приведен ниже:

def set_a_switch(door, switch_positions, door_for_switch, n):
  low, high = 0, n - 1

  result = tryCombination(switch_positions)
  if result != door:
    for i in range(n):
      if door_for_switch[i] == -1:
        switch_positions[i] = 1

  while low != high:
    mid = (low + high) // 2
    for i in range(low, mid + 1):
      if door_for_switch[i] == -1:
        switch_positions[i] = 1 - switch_positions[i]
    result = tryCombination(switch_positions)
    if result != door:
      high = mid
      for i in range(low, mid + 1):
        if door_for_switch[i] == -1:
          switch_positions[i] = 1 - switch_positions[i]
    else:
      low = mid + 1
  door_for_switch[low] = door
  switch_positions[low] = 1 - switch_positions[low]

Вначале заводим переменные low и high необходимые для двоичного поиска и первый раз запустим функцию result = tryCombination(switch_positions). Установив все еще не связанные рычаги в положение 0, мы определяем, открыта или нет текущая дверь. Если открыта, то нужно ее закрыть, чтобы потом путем поочередного изменения положения рычагов определить, какой из них ее откроет. Для закрывания двери мы устанавливаем все несвязанные рычаги в положение 1. Такой прием срабатывает, потому что, когда все рычаги находились в положении 0, дверь была открыта. Один из этих рычагов связан с этой дверью, значит, при изменении их положения она точно закроется.

При каждой проверке условия двоичного поиска в цикле while мы делаем так, чтобы текущая дверь была закрыта. В частности, когда low и high равны и цикл завершается, дверь остается закрытой. Тогда останется лишь изменить положение рычага low, чтобы ее открыть.

Теперь рассмотрим сам двоичный поиск. В каждой итерации мы вычисляем среднюю точку mid, затем изменяем положение первой половины рычагов(но только тех, которые еще не связаны с дверью). Какой эффект это оказало на текущую дверь? Здесь есть две возможности:

• Дверь открылась. Теперь нам известно, что искомый рычаг находится между low и mid, значит, все рычаги больше mid отбрасываются. Мы также возвращаем каждый рычаг между low и mid обратно в положение, предшествовавшее текущей итерации. В итоге дверь снова закрывается, и можно переходить к очередной итерации.
• Дверь осталась закрыта. Значит, искомый рычаг находится между mid + 1 и high, поэтому мы отбрасываем все рычаги, начиная с mid и менее. В данном случае никакие рычаги не переключаются, потому что дверь по-прежнему закрыта, что нам и нужно.

По завершении двоичного поиска low и high будут равны, указывая на рычаг, связанный с текущей дверью. Текущая дверь в этот момент будет все еще закрыта, и мы переключим найденный рычаг для ее открытия. Мы получили чистое, быстрое решение, основанное на двоичном поиске.

Выводы

Иногда найти оптимальное решение намного сложнее, чем проверить допустимость одного из его вариантов. Сколько жидкости нужно залить в дерево? Неизвестно. Будет ли достаточно 10 литров? А вот это уже можно проверить. При правильных условиях двоичный поиск способен преобразовать сложную задачу оптимизации в намного более простую задачу проверки допустимости. Иногда это похоже на жульничество. Добавление двоичного поиска означает всего лишь необходимость учитывать дополнительный логарифмический фактор. Но этот фактор практически не требует ресурсов, зато взамен мы получаем более простую задачу. Я не утверждаю, что двоичный поиск является единственным способом решения задач из примеров выше. Некоторые задачи, которые можно решить с помощью двоичного поиска, также можно решить и через динамическое программирование. Но двоичный поиск часто может предложить решения, которые окажутся конкурентноспособными и более простыми, чем их альтернативы. Если вам интересно, вернитесь к каждой задаче еще раз, но теперь подумайте, как можно их решить без двоичного поиска. И если вы видите задачу, в которой можно использовать двоичный поиск, то не стоит сомневаться.