Почему указатели
не пропускают ответ

Категория

Доказательство

Уровень

Средний

Опирается на

Глава 8.4; занятие 7: инвариант прохода

Зачем это знать

Объяснить на интервью, почему решение верное

§1Таблица всех пар

В главе 8.4 правило сдвига проверено на примерах, но один вопрос остался открытым: почему цена, которую исключил ход указателя, не могла входить в ответ. Чтобы ответить на него, запишем все пары каталога в таблицу. Строка — левая цена prices[i], столбец — правая prices[j], в клетке — их сумма. Заполнена только часть над диагональю, где i < j. Пара (2, 3) и пара (3, 2) — одна и та же пара товаров, а на диагонали товар складывается сам с собой.

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

§2Ход указателей по таблице

Указатели i = 0 и j = n − 1 — это правый верхний угол таблицы: самая дешёвая цена с самой дорогой. Клетка с рамкой — текущая пара. Если её сумма меньше цели, то и все клетки левее в этой строке меньше цели. Строку вычёркивают целиком и переходят на строку ниже — это i += 1. Если сумма больше цели, то и все клетки ниже в этом столбце больше: вычёркивается столбец, указатель уходит влево — j -= 1.

Кнопка «ход указателей» делает один ход и объясняет, что вычеркнуто. Кнопка «перебор по порядку» для сравнения обходит клетки так, как это делают вложенные циклы, — строку за строкой.

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

Та же таблица для цели, которой в каталоге нет. Здесь указатели дойдут до диагонали, вычеркнув всю таблицу, и вернут None.

§3Инвариант задачи 1

Таблица показывает доказательство наглядно, а на интервью его произносят словами. Для этого, как в занятии 7, формулируют инвариант — утверждение, которое верно перед каждой проверкой условия цикла.

§4Монотонность указателей

Инвариант объясняет, почему указатели не теряют ответ. Второй вопрос, который задают на review, — почему они делают не больше n шагов. Ответ на него — ещё одно свойство алгоритма.

Указатели монотонны в каждой задаче модуля, и в каждой из этого следует оценка O(n).

У перебора монотонности нет: внутренний указатель j после каждого шага внешнего цикла возвращается к i + 1 и проходит конец списка заново. Поэтому проверок там n·(n − 1) / 2.

§5Неотсортированный вход

Проверим, что без сортировки указатели действительно ошибаются. Возьмём тот же каталог и поменяем местами две цены: 700 и 1200. Пара 700 + 900 = 1600 в списке осталась, на индексах 3 и 4.

>>> print(pair_sum([300, 450, 1200, 700, 900, 1500], 1600))
None
>>> pair_sum_brute([300, 450, 1200, 700, 900, 1500], 1600)
(3, 4)

Перебор пару нашёл, указатели — нет. Прогон показывает, на каком ходе она потерялась: при i = 1, j = 4 сумма 450 + 900 = 1350 меньше цели, и правило исключает цену 450. У 450 пары действительно нет. Но на следующем ходе сумма 1200 + 900 = 2100 больше цели, и правило исключает 900 — а 900 входит в ответ вместе с 700. Ход j -= 1 верен, только если prices[i] = 1200 — самая дешёвая из оставшихся цен, а на участке ещё есть 700.

Поэтому первый вопрос к любой задаче на указатели навстречу — отсортирован ли вход. Если нет и индексы не нужны, его сортируют: sorted(prices) стоит O(n log n). Если индексы нужны, выбирают словарь — глава 8.2, §4.

§6Как объяснить решение на интервью

Кроме кода интервьюер ждёт рассуждение, по которому видно, что решение верное. Всё, что доказано в этой главе, для задачи 1 укладывается в четыре фразы: это инвариант и три проверки, сказанные обычными словами.

§7Проверьте себя