Пары, окно и сложные цепочки

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

Сколько пар чисел из списка дают сумму не больше S, если одно число может входить во многие пары?

Отсортировать список и двигать два указателя: если a[left] + a[right] ≤ S, то с a[left] подходят все числа до right — их right − left.

В подтеме «Цепочки коробок и пары» каждый объект использовался один раз. Здесь одно число может входить во многие пары.

Почему пар ровно right − left? Это элементы с индексами left + 1, …, right: каждый не больше a[right], значит, и с a[left] даёт сумму не больше S.

a = [1, 3, 4, 10, 11, 13]limit = 14a.sort()left = 0right = len(a) - 1count = 0while left < right:    if a[left] + a[right] <= limit:        count += right - left        left += 1    else:        right -= 1print(count)

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

«Среднее арифметическое пары встречается среди чисел файла» — здесь два указателя не помогут. Что делать?

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

Для проверки наличия значения удобно использовать множество values = set(a): операция x in values проверяет наличие значения и в обычных условиях работает существенно быстрее последовательного просмотра списка.

a = [2, 5, 8, 11, 14, 20]values = set(a)count = 0best = Nonefor i in range(len(a)):    for j in range(i + 1, len(a)):        total = a[i] + a[j]        if total % 2 == 0:            average = total // 2            if average in values:                count += 1                if best is None or average > best:                    best = averageprint(count, best)

total % 2 == 0 проверяет чётность суммы — это нужно, чтобы среднее было целым. Почему j начинается с i + 1? Чтобы не образовывать пару элемента с самим собой и не считать (a, b) и (b, a) дважды.

Здесь остаётся O(N²) пар: при N = 5000 это 12,5 миллиона проверок — несколько секунд, а при 100 000 уже почти пять миллиардов. Множество ускоряет проверку наличия, но не отменяет сам перебор. Допустимость такого решения зависит от размера входных данных; в задачах подборки чисел несколько тысяч.

Выбрать как можно больше чисел так, чтобы наибольшее и наименьшее отличались не больше чем на D. Как?

После сортировки подходящие числа идут подряд: двигать правую границу окна, а левую подтягивать, пока разность больше D.

Почему подряд? Если минимальное и максимальное допустимы, любое число между ними тоже можно добавить: границы диапазона не изменятся. Для чисел 1, 3, 4, 10, 11, 13 и D = 4 подходят, например, 1, 3, 4 и 10, 11, 13.

Участок между границами left и right называют окном. Посмотри, как оно движется:

a = [1, 3, 4, 10, 11, 13]distance = 4a.sort()left = 0best = 0for right in range(len(a)):    while a[right] - a[left] > distance:        left += 1    length = right - left + 1    if length > best:        best = lengthprint(best)

Длина — right − left + 1, потому что обе границы входят в участок: индексы от 2 до 4 включительно — это три элемента. Почему вложенный while не делает алгоритм квадратичным? left за всю работу только увеличивается и проходит не более N позиций; он не возвращается в начало для каждого right.

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

Альпинист спускается по лагерям; перепад больше D разрешён только со страховкой, и таких переходов не больше K. Как найти самый длинный маршрут?

Это окно по отсортированным различным высотам, в котором особых переходов не больше K, — но только при условии 2(D + 1) > E.

Предположим: альпинист идёт по лагерям только на строго меньшую высоту; обычный переход имеет перепад не более D, специальный (со страховкой) — не более E, специальных переходов не больше K. Нужен самый длинный маршрут, а при равной длине — с наибольшей высотой последнего лагеря. Возникает вопрос: можно ли считать, что оптимальный маршрут проходит по всем высотам подряд в отсортированном списке?

Не всегда. Но это можно доказать, например, при целых высотах и условии E < 2(D + 1). Минимальный целый перепад, уже требующий специального перехода, равен D + 1; два таких перепада вместе дают хотя бы 2(D + 1).

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

Значит, оптимальный маршрут можно искать среди непрерывных участков отсортированных различных высот. Перепад больше E разрывает участок; перепад от D + 1 до E расходует один специальный переход; при превышении K сдвигаем левую границу.

heights = [30, 28, 23, 21, 17, 15, 9, 8]normal_limit, special_limit, allowed_special = 3, 6, 1heights = sorted(set(heights), reverse=True)left = special_count = 0best_length = best_finish = 0for right in range(len(heights)):    if right > 0:        gap = heights[right - 1] - heights[right]        if gap > special_limit:            left = right            special_count = 0        elif gap > normal_limit:            special_count += 1    while special_count > allowed_special:        if heights[left] - heights[left + 1] > normal_limit:            special_count -= 1        left += 1    length = right - left + 1    if (length, heights[right]) > (best_length, best_finish):        best_length, best_finish = length, heights[right]print(best_length, best_finish)

Один из лучших маршрутов — 30 → 28 → 23 → 21: переход 28 → 23 специальный. Удаление повторных высот set допустимо именно потому, что маршрут строго убывает и у лагерей нет других различающих условий: на одной высоте можно посетить не более одного лагеря.

Условие на D и E нельзя отбросить. При D = 3, E = 12, K = 1 и высотах 53, 52, 51, 50, 44, 38, 37, 36, 35 можно пропустить 44 и пройти 53, 52, 51, 50, 38, 37, 36, 35 — восемь лагерей, один специальный переход 50 → 38. А прохождение через 44 потребовало бы двух специальных переходов, и окно найдёт только пять лагерей. Здесь 12 ≥ 2 · 4 — условие нарушено. Это пример того, почему для усложнённой задачи нужно заново обосновывать возможность свести выбор к соседним элементам.

В камере хранения десятки тысяч ячеек и заявок. Как быстро находить свободную ячейку с наименьшим номером?

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

Алгоритм камеры хранения из подтемы о моделировании в худшем случае проверяет k ячеек для каждой из n заявок — порядка O(N · K) действий. Если оба числа большие, это становится дорого. Нужны две операции: быстро узнать, какая занятая ячейка освободится раньше, и быстро выбрать минимальный номер среди уже свободных.

Для этого используют очередь приоритетов — структуру, из которой удобно извлекать элемент с наименьшим ключом. В Python её реализует модуль heapq (подключается так же, как другие модули: from heapq import heapify, heappush, heappop). Основные операции:

• heapify(a) — организовать существующий список как такую структуру;
• heappush(a, value) — добавить элемент;
• heappop(a) — удалить и вернуть минимальный элемент;
• a[0] — посмотреть минимальный элемент без удаления.

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

Храним free_cells — номера свободных ячеек и busy — пары «время освобождения, номер ячейки». На примере двух ячеек и пяти заявок:

from heapq import heapify, heappush, heappop k = 2requests = [(1, 5), (2, 4), (3, 7), (4, 8), (5, 6)]requests.sort(key=lambda x: x[0])free_cells = list(range(k))heapify(free_cells)busy = []accepted = 0last_cell = Nonefor start, finish in requests:    while busy and busy[0][0] <= start:        _, cell = heappop(busy)        heappush(free_cells, cell)    if free_cells:        cell = heappop(free_cells)        heappush(busy, (finish, cell))        accepted += 1        last_cell = cell + 1print(accepted, last_cell)

list(range(k)) создаёт список индексов 0, 1, …, k − 1. Почему нужны две структуры? В занятой ячейке нас интересует время освобождения, в свободной — номер ячейки; один и тот же порядок не решает обе задачи. Обработка после сортировки занимает порядка O(N log K). Если выбирается самая дешёвая свободная ячейка, а при равенстве — минимальный номер, в свободной очереди приоритетов можно хранить пары (price, cell_number).

Коробки двух цветов, и в цепочке цвета соседних коробок должны различаться. Как найти самую длинную цепочку?

Сделать два жадных прохода — с внешней коробкой каждого цвета — и взять лучший: на каждой глубине нужный цвет известен.

Пусть коробки двух цветов, 0 и 1, вкладываются друг в друга с разницей сторон хотя бы 5, а цвета соседних коробок обязаны различаться. Если известно, какого цвета внешняя коробка, цвета всех следующих определены: 0, 1, 0, 1, … или 1, 0, 1, 0, … На каждой глубине нужна коробка известного цвета, и снова выгодно брать самую большую из подходящих: она оставляет больше места внутри.

Программа делает оба прохода и берёт лучший:

boxes = [(40, 0), (37, 1), (33, 1), (31, 0), (26, 0),         (24, 1), (20, 0), (18, 1), (12, 1)]gap = 5best = (0, 0)for first in (0, 1):    need, count, last = first, 0, None    for size, color in sorted(boxes, reverse=True):        if color != need:            continue        if last is None or last - size >= gap:            count += 1            last = size            need = 1 - need    best = max(best, (count, last))print(*best)

Снаружи коробка цвета 0 даёт цепочку 40, 33, 26, 18; снаружи коробка цвета 1 — только три коробки. Кортеж (count, last) сравнивает сначала длину, затем самую маленькую коробку — оба критерия задачи.

А если зазор растёт с номером коробки и материалы чередуются?

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

Пусть правило имеет вид:

Между k-й и (k + 1)-й коробкой нужен зазор хотя бы C + k, материалы должны различаться.

Нумерация идёт изнутри наружу, а второй критерий — наименьшая внешняя коробка. Если известно, из какого материала сделана первая коробка, материалы всех следующих определены. Программа делает оба прохода:

boxes = [(10, 0), (11, 1), (13, 1), (14, 0), (17, 0),         (18, 1), (22, 1), (23, 0), (27, 0), (28, 1),         (33, 1)]base_gap = 2boxes.sort()best_count = 0best_outer = Nonefor first_type in (0, 1):    expected_type = first_type    count = 0    last_size = None    for size, material in boxes:        if material != expected_type:            continue        gap = base_gap + count        if last_size is None or size - last_size >= gap:            count += 1            last_size = size            expected_type = 1 - expected_type    if count > best_count or (        count == best_count and last_size is not None        and (best_outer is None or last_size < best_outer)    ):        best_count = count        best_outer = last_sizeprint(best_count, best_outer)

Здесь base_gap соответствует C. Почему перед добавлением новой коробки используется count? Потому что уже выбрано count коробок: последняя из них имеет номер count, значит, следующий зазор должен быть не меньше C + count. Цепочка из материала 1 — 11, 14, 18, 23, 33: зазоры 3, 4, 5 и 10, а коробка 28 не подошла, потому что 28 − 23 = 5 < 6.

Почему жадность работает при фиксированном первом материале? На одной и той же позиции цепочки нужный материал одинаков, требуемая прибавка к следующей коробке одинакова, а меньшая текущая коробка оставляет не меньше возможностей продолжения.

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

Все коробки убирают на склад блоками вложенных друг в друга коробок. Сколько нужно блоков как минимум?

Столько, сколько коробок умещается в промежуток короче зазора: их никак нельзя вложить друг в друга. Это число находит окно.

Блок занимает одну ячейку склада, одиночная коробка — тоже. Возьмём коробки 12, 14, 18, 21, 22, 27, 34, 40, 45 и зазор 6.

Коробки 18, 21 и 22 попарно отличаются меньше чем на 6 — ни одну из них нельзя вложить в другую. Значит, они лежат в трёх разных блоках, и меньше трёх блоков не бывает. Это оценка снизу, и её дают любые коробки, размеры которых умещаются в промежуток короче зазора. Наибольшее число таких коробок находит окно из этого урока: участок отсортированного списка, где a[right] - a[left] < gap.

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

sizes = [12, 14, 18, 21, 22, 27, 34, 40, 45]gap = 6sizes.sort()blocks = []for size in sizes:    placed = False    for block in blocks:        if size - block[-1] >= gap:            block.append(size)            placed = True            break    if not placed:        blocks.append([size])left = widest = 0for right in range(len(sizes)):    while sizes[right] - sizes[left] >= gap:        left += 1    widest = max(widest, right - left + 1)print(len(blocks), widest)

Флаг placed отмечает, нашёлся ли подходящий блок. Для ответа достаточно окна: раскладка нужна, только чтобы увидеть сами блоки. Наибольшее число коробок в одном блоке — это длина самой длинной цепочки из подтемы 3.

При наибольшем количестве файлов нужен набор, где самый большой файл наибольший, при равенстве — второй и так далее. Как его построить?

Начать с самых маленьких и улучшать места сверху вниз: на каждое место ставить наибольший файл, который ещё помещается.

Это повторение приёма из подтемы 2 «Жадный выбор» для каждого места набора.

Возьмём вместимость 62 и файлы 8, 12, 15, 19, 22, 34. Четыре самых маленьких занимают 54 — свободно 8, пятый не помещается. Сначала улучшаем самый большой элемент набора: вместо 19 можно взять любой файл не больше 19 + 8 = 27 — берём 22, свободно 5. Затем второй: вместо 15 — любой файл не больше 20 среди файлов между 15 и 22 — это 19, свободно 1. Третий, 12, заменить нечем.

sizes = sorted([8, 12, 15, 19, 22, 34])capacity = 62used = k = 0for x in sizes:    if used + x > capacity:        break    used += x    k += 1chosen = list(range(k))free = capacity - usedupper = len(sizes)for j in range(k - 1, -1, -1):    best = chosen[j]    for i in range(chosen[j] + 1, upper):        if sizes[i] - sizes[chosen[j]] <= free:            best = i    free -= sizes[best] - sizes[chosen[j]]    chosen[j] = best    upper = bestprint(*[sizes[i] for i in chosen])

chosen хранит индексы выбранных файлов, upper не даёт взять файл, уже занятый местом выше. Почему замены идут сверху вниз и каждый раз берут наибольший возможный файл? Самый большой элемент важнее всех остальных, а остальные пока самые маленькие — они оставляют ему наибольшее место; затем то же рассуждение повторяется для второго места при закреплённом первом.

• Подсчёт пардва указателя, + (right − left)
• Все парыперебор и проверка по множеству
• Окноправая граница идёт, левая догоняет
• Кучабыстрый наименьший элемент
• Чередованиедва прохода — по цвету начала
• Блокистолько, сколько коробок в промежутке короче зазора