Тренировочная сессия 10: два указателя навстречу по отсортированному массиву СЕССИЯ

Что тренируем сегодня

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

Сегодняшний приём — два указателя навстречу друг другу: один стартует в начале отсортированного массива, другой в конце, и они сходятся, ни разу не возвращаясь назад. Обе задачи на него, но применяют по-разному. В первой указатели считают: вопрос звучит как «сколько пар удовлетворяют неравенству», наивный ответ — двойной цикл на $4 \cdot 10^{10}$ операций, правильный — сортировка и один проход. Во второй указатели идут: левый тратит то, что заработал правый, и вся задача — понять, почему такой встречный обмен оптимален.

Коридор ~CF 1400–1600. Уровень, на котором ошибка стоит уже не «некрасивого кода», а превышения лимита времени.

---

Теория

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

Форма 1 — считать пары с условием на сумму.

Когда применять:

• в условии просят посчитать количество пар $(i, j)$, $i < j$, для которых выполняется неравенство на сумму (или разность) элементов;
• размер массива до $2 \cdot 10^5$ и больше — двойной цикл не проходит по времени;
• порядок элементов в исходном массиве для ответа не важен: пара $(i, j)$ — просто пара значений, а не пара позиций.

Последний пункт — самый важный и самый пропускаемый. Сортировка перемешивает индексы; если условие задачи привязано к порядку («$i$ левее $j$ и при этом $a_i > a_j$»), сортировать нельзя, и приём не работает.

Как решать:

1. Свести условие к виду «сумма двух элементов одного массива» — часто для этого нужно ввести новую величину (разность, отношение, значение функции от элемента).
2. Отсортировать полученный массив по возрастанию.
3. Поставить левый указатель в начало, правый — в конец.
4. Если пара «левый + правый» условию удовлетворяет, то ему удовлетворяет и любая пара «что-то между ними + правый» — все элементы между указателями не меньше левого. Значит можно засчитать сразу все такие пары разом и сдвинуть правый указатель влево.
5. Если не удовлетворяет — правому указателю уже никто не поможет в паре с текущим левым (он и так самый большой), значит левый указатель обязан сдвинуться вправо.

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

Мини-пример — массив $[-2, -1, 0, 3, 5]$, ищем пары с суммой строго больше нуля. Указатели на $-2$ и $5$: сумма 3, подходит — значит подходят все четыре пары с пятёркой (с $-2$, $-1$, $0$, $3$), засчитываем 4 и двигаем правый на $3$. Пара $-2$ и $3$: сумма 1, подходит — засчитываем 3 пары с тройкой, двигаем правый на $0$. Пара $-2$ и $0$: сумма $-2$, не подходит — двигаем левый. Пара $-1$ и $0$: $-1$, снова нет — двигаем левый, указатели встретились. Итого 7 пар.

Каркас приёма — подсчёт пар с суммой строго больше нуля:

Форма 2 — не считать, а идти. Те же два указателя могут не подсчитывать пары, а проходить жадный сценарий. Типичная обстановка: набор объектов отсортирован по некоторому порогу; ход с «дешёвого» конца выгоден, но доступен только при накопленном ресурсе, а ход с «дорогого» конца невыгоден, зато этот ресурс приносит.

Когда узнавать эту форму:

• объекты можно упорядочить по числу-порогу, и выгодность действия зависит только от того, перешагнули мы порог или ещё нет;
• ресурс общий и только растёт — накопленное не тратится и не пропадает;
• жадность просится, но непонятно, с какого конца начинать: оба варианта выглядят разумно.

Схема действий:

1. Отсортировать объекты по порогу.
2. Поставить левый указатель на самый низкий порог, правый — на самый высокий.
3. Если ресурса хватает, чтобы левый стал выгодным, — целиком отработать левый по выгодной цене и сдвинуть левый указатель.
4. Если не хватает — брать невыгодные ходы с правого конца, ровно столько, сколько нужно, чтобы дотянуть ресурс до порога левого.

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

Мини-пример: три вида товара, у каждого «нужно купить» и «порог скидки» — $(1, 3)$, $(3, 4)$, $(1, 5)$, обычная цена 2, со скидкой 1. Скидок пока нет, а левому нужен счётчик 3. Берём один товар справа по 2 (счётчик 1), потом два из середины по 2 (счётчик 3, потрачено 6). Теперь левый выгоден: берём его единицу за 1 (счётчик 4, потрачено 7), а следом становится выгодной и середина — её остаток за 1. Итого 8, и это минимум.

Где приём перестаёт работать. Всё держится на одной монотонности: чем правее элемент в отсортированном массиве, тем «легче» ему выполнить условие (или тем позже он станет выгодным). Для суммы и для порогов это так; для условия вроде «сумма делится на $k$» — нет, там сортировка не даёт никакой монотонности, и приём бесполезен. Второй обязательный признак — что двигаться назад никогда не нужно: если после сдвига указателя может понадобиться вернуться, за один проход не обойтись.

С чем путают. Соседний приём — скользящее окно, где оба указателя идут в одну сторону и поддерживают отрезок. Различать просто по вопросу: «пара элементов / два конца набора» — указатели навстречу; «самый длинный (короткий) непрерывный отрезок с условием» — окно. Формально это разные инварианты: встречные указатели поддерживают пару границ, окно — множество элементов между ними. Скользящее окно возьмём на сессии 12 отдельно.

Сложность приёма: $O(n \log n)$ — сортировка доминирует, сам проход указателей $O(n)$. Взаимозаменяемая альтернатива для формы 1 — для каждого элемента искать границу бинарным поиском; тот же порядок сложности, но два указателя короче и не требуют возиться с границами.

---

Задача 1 — CF ~1400 — «Pair of Topics»

Что дано

Есть n тем. Для каждой темы известны два числа: a[i] — насколько тема интересна первому участнику, и b[i] — насколько она интересна второму. Пара тем (i, j) с i < j считается хорошей, если суммарный интерес первого участника строго больше суммарного интереса второго:

a[i] + a[j] > b[i] + b[j]

Нужно посчитать количество хороших пар.

Формат ввода:

• Строка 1: целое число n ($2 \le n \le 2 \cdot 10^5$).
• Строка 2: n целых чисел a[1] … a[n] ($1 \le a_i \le 10^9$).
• Строка 3: n целых чисел b[1] … b[n] ($1 \le b_i \le 10^9$).

Формат вывода: одно число — количество хороших пар.

Пример 1:

Ввод:
5
4 8 2 6 2
4 5 4 1 3

Вывод:
7

Пример 2:

Ввод:
4
1 3 2 4
1 3 2 4

Вывод:
0

Разберём на примере

Возьмём пример 1. Проверять каждую пару вручную — десять проверок, при n = 2 · 10^5 таких проверок будет двадцать миллиардов. Но прежде чем ускорять, стоит упростить само условие.

В неравенстве a[i] + a[j] > b[i] + b[j] перемешаны обе темы и оба участника. Перенесём всё, что относится к теме i, налево, а всё, что относится к j, направо — вернее, сгруппируем по темам:

(a[i] - b[i]) + (a[j] - b[j]) > 0

Теперь каждая тема характеризуется одним числом c[i] = a[i] - b[i] — насколько она «перевешивает» в сторону первого участника. Условие превратилось в «сумма двух элементов массива c строго положительна». Два массива схлопнулись в один, и это ровно тот вид, с которого начинается приём двух указателей.

Считаем c для примера 1:

Отсортируем: [-2, -1, 0, 3, 5]. Это ровно тот массив, который разбирался в теории, — ответ 7.

Важная деталь: пары считаются по значениям, а не по исходным позициям. Условие i < j здесь означает только «две разные темы, каждая пара учитывается один раз» — сама формула симметрична относительно i и j, поэтому от порядка тем ничего не зависит и сортировать можно смело.

Идея решения

Алгоритм в одну фразу: заменить каждую тему на c[i] = a[i] - b[i], отсортировать массив c и двумя указателями навстречу посчитать пары с положительной суммой.

Почему это работает. После сортировки массив монотонен, и работает главное свойство: если c[l] + c[r] > 0, то и c[k] + c[r] > 0 для любого k между l и r, потому что c[k] ≥ c[l]. Значит, обнаружив подходящую пару из крайних элементов, мы имеем право засчитать сразу r - l пар — все пары текущего правого элемента с элементами от l до r - 1 — и больше к правому элементу не возвращаться: все его хорошие пары уже учтены.

Если же c[l] + c[r] ≤ 0, то для левого элемента l не существует ни одного партнёра среди оставшихся: правый указатель сейчас указывает на самый большой доступный элемент, и даже он не спасает. Значит элемент l можно выбросить из рассмотрения, сдвинув левый указатель.

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

Про строгость неравенства. Условие «строго больше», поэтому пара с суммой ровно ноль не считается — именно поэтому во втором примере ответ нулевой: там все c[i] равны нулю, любая пара даёт сумму ноль, а ноль не больше нуля.

Псевдокод

прочитать n, массивы a и b

для i от 0 до n-1:
    c[i] = a[i] - b[i]

отсортировать c по возрастанию

ответ = 0
l = 0
r = n - 1

пока l < r:
    если c[l] + c[r] > 0:
        ответ = ответ + (r - l)   // все пары от l до r-1 с элементом r подходят
        r = r - 1
    иначе:
        l = l + 1                 // элементу l партнёра не найти

вывести ответ

Код решения

Комментарии по реализации. Ответ обязан храниться в 64-битном типе: пар может быть до $\frac{n(n-1)}{2} \approx 2 \cdot 10^{10}$, а 32-битный тип держит лишь около двух миллиардов. Разности c[i] в 32-битный тип помещаются (значения до $10^9$ по модулю), но их сумма — уже нет, поэтому в C++ проще сразу объявить массив как long long, чем ловить переполнение в одном-единственном сравнении. В Python таких забот нет — целые числа произвольной длины, — но чтение через sys.stdin.buffer.read() обязательно: построчный ввод на $2 \cdot 10^5$ числах в двух строках заметно медленнее.

Проверка на примерах

Пример 1: n = 5, c = [0, 3, -2, 5, -1], после сортировки [-2, -1, 0, 3, 5].

Наш вывод: 7 — совпадает с ожидаемым.

Пример 2: n = 4, a и b совпадают поэлементно, значит c = [0, 0, 0, 0]. Первая же проверка 0 + 0 > 0 ложна, левый указатель едет вправо до встречи с правым, ответ остаётся нулевым.

Наш вывод: 0 — совпадает с ожидаемым.

Крайние случаи

• n = 2. Один-единственный шаг цикла: либо пара подходит и ответ 1, либо нет и ответ 0.
• Все c[i] отрицательны. Левый указатель доезжает до правого без единого засчитанного шага — ответ 0. Проверка на то, что цикл вообще завершается по условию l < r.
• Все c[i] положительны. Подходят все $\frac{n(n-1)}{2}$ пар; на этом тесте ловится переполнение 32-битного типа при $n = 2 \cdot 10^5$.
• Ровно нулевая сумма. Пары вида $(-3, 3)$ не считаются: неравенство строгое. Самая частая содержательная ошибка в этой задаче.
• Максимальные значения. a[i] = 10^9, b[i] = 1 — разности порядка $10^9$, их сумма около $2 \cdot 10^9$ уже выходит за 32-битный знаковый тип.
• Все элементы равны. Указатели идут корректно независимо от того, есть ли в массиве дубликаты: логика опирается только на неубывание.

Типичные ошибки

1. Не свести задачу к одному массиву. Пока в неравенстве живут и a, и b, сортировать нечего: любая сортировка по a перемешает b. Ключевой шаг — именно переход к c = a − b.
2. Считать в 32-битном типе. Ответ до $2 \cdot 10^{10}$, промежуточная сумма до $2 \cdot 10^9$. Переполнение здесь даёт не падение, а тихо неверный ответ.
3. Использовать нестрогое сравнение. >= вместо > добавит в ответ все пары с нулевой суммой — на втором примере это сразу видно.
4. Считать каждую пару дважды. Возникает, когда вместо «два указателя навстречу» пишут «для каждого i посчитать всех подходящих j» и забывают поделить на два или ограничить j > i.
5. Сомневаться, можно ли сортировать. Можно: условие симметрично относительно двух тем, а i < j требует только различности тем, а не их порядка в исходном вводе.
6. Сдвигать оба указателя за один шаг. При выполненном условии сдвигать надо только правый: левый элемент ещё может пригодиться в парах с меньшими правыми.
7. Медленный ввод. $4 \cdot 10^5$ чисел через построчное чтение в Python — заметная часть бюджета времени на ровном месте.

Сложность

Время: $O(n \log n)$ — сортировка; проход двумя указателями $O(n)$. Память: $O(n)$ — один массив разностей.

---

Задача 2 — CF ~1600 — «PriceFixed»

Что дано

В магазине n видов товара, каждая единица стоит 2 рубля. У каждого вида есть порог b[i]: как только суммарно куплено не меньше b[i] единиц товара (любого, не обязательно i-го), все дальнейшие покупки i-го вида идут по 1 рублю. Нужно купить не меньше a[i] единиц каждого вида; покупать сверх нормы разрешено. Найти минимальную сумму денег.

Формат ввода:

• Строка 1: целое n ($1 \le n \le 100\,000$) — количество видов товара.
• Каждая из следующих n строк: два целых числа a[i] и b[i] ($1 \le a_i \le 10^{14}$, $1 \le b_i \le 10^{14}$) — сколько нужно купить и каков порог скидки. Сумма всех a[i] не превосходит $10^{14}$.

Формат вывода: одно число — минимальная сумма.

Пример 1:

Ввод:
3
3 4
1 3
1 5

Вывод:
8

Пример 2:

Ввод:
5
2 7
2 8
1 2
2 4
1 8

Вывод:
12

Разберём на примере

Возьмём пример 1 и отсортируем товары по порогу: $(1, 3)$, $(3, 4)$, $(1, 5)$ — здесь первое число «сколько нужно», второе «порог скидки». Всего надо купить $1 + 3 + 1 = 5$ единиц, и это число зафиксировано условием: сколько ни хитри, ходов будет ровно пять. Значит вопрос не «сколько покупать», а какие из пяти покупок окажутся по 2 рубля, а какие по 1.

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

Ответ: единицы товара с самым высоким порогом. Логика такая. Товар с порогом 5 станет выгодным позже всех — возможно, вообще никогда, если пять покупок закончатся раньше. Его единицы всё равно с большой вероятностью придётся брать по полной цене, так пусть они и работают «топливом» для счётчика. А товар с порогом 3 наоборот — до его скидки ближе всего, поэтому его единицы разумно приберечь до момента, когда они станут стоить 1 рубль.

Проследим: берём единственную единицу товара с порогом 5 за 2 рубля (счётчик 1, потрачено 2). Мало, нужно 3. Берём две единицы товара с порогом 4 — тоже по 2 (счётчик 3, потрачено 6). Теперь порог 3 достигнут: единственная единица первого товара идёт за 1 рубль (счётчик 4, потрачено 7). Счётчик стал 4 — открылась скидка и у товара с порогом 4, а у него как раз остался неоплаченный остаток: берём его за 1 рубль (потрачено 8). Все пять единиц куплены, ответ 8 — ровно как в эталоне.

Обратите внимание на характерное движение: один указатель шёл слева (тот, кого мы обслуживаем со скидкой), другой справа (тот, кого мы приносим в жертву ради счётчика), и они встретились. Отдельно любопытно, что в последнем шаге товар с порогом 4 оказался и «жертвой», и «выгодным» — сначала две его единицы ушли по 2 рубля, а остаток по 1. Это нормально: указатели вполне могут сойтись на одном и том же товаре.

Идея решения

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

Почему жадность корректна. Сначала зафиксируем: общее число покупок равно $\sum a_i$ и от нашего порядка не зависит — покупать сверх нормы никогда не выгодно, ведь лишняя единица стоит минимум 1 рубль, а счётчик и без неё дорастёт до того же значения за счёт нужных покупок. Значит минимизировать надо количество покупок, сделанных до открытия соответствующей скидки.

Теперь обменный аргумент. Пусть в оптимальном плане какая-то единица товара i куплена по полной цене, а какая-то единица товара j — со скидкой, причём порог i ниже порога j. Поменяем эти две покупки местами: пусть по полной цене пойдёт единица j, а со скидкой — единица i. Такой обмен допустим: момент времени тот же, счётчик тот же, а раз в этот момент был достигнут порог j, то тем более достигнут и более низкий порог i. Суммарная цена не изменилась. Повторяя обмены, приводим план к виду «по полной цене покупаются товары с самыми высокими порогами» — то есть ровно к тому, что делает наш алгоритм.

Почему указатели не возвращаются. Счётчик покупок только растёт, поэтому если порог левого товара уже перекрыт, он останется перекрытым до конца — возвращаться к этому товару незачем, его можно забрать целиком за один шаг. А правый товар мы уменьшаем только когда скидок ещё не хватает; как только его остаток обнулён, он больше не нужен. Каждый шаг цикла либо сдвигает левый указатель, либо уменьшает остаток правого до нуля и сдвигает правый, либо доводит счётчик ровно до порога левого — то есть за $O(n)$ шагов всё заканчивается.

Псевдокод

прочитать n и пары (a[i], b[i])
отсортировать товары по b по возрастанию

left = 0, right = n - 1
куплено = 0, стоимость = 0

пока left <= right:
    если куплено >= b[left]:            // скидка на левый уже открыта
        стоимость += a[left]            // забираем его целиком по 1
        куплено   += a[left]
        a[left] = 0
        left += 1
    иначе:                              // не хватает счётчика — берём справа по 2
        взять = min(b[left] - куплено, a[right])
        стоимость += 2 * взять
        куплено   += взять
        a[right]  -= взять
        если a[right] == 0:
            right -= 1

вывести стоимость

Код решения

Комментарии по реализации. Все величины 64-битные: количество единиц доходит до $10^{14}$, а стоимость — до $2 \cdot 10^{14}$, так что int переполнится молча и незаметно. Пара сортируется по первому элементу, поэтому порог кладётся первым — так sort не требует компаратора. Обратите внимание на условие left <= right со знаком «не строго»: когда указатели сходятся на одном товаре, его остаток может частично уйти по 2 рубля (пока порог не достигнут), а частично по 1 — как раз случай из разбора примера, и строгое неравенство его потеряло бы.

Проверка на примерах

Пример 1: товары после сортировки по порогу — $(a=1, b=3)$, $(a=3, b=4)$, $(a=1, b=5)$.

Наш вывод: 8 — совпадает с ожидаемым.

Пример 2: товары после сортировки — $(1, 2)$, $(2, 4)$, $(2, 7)$, $(2, 8)$, $(1, 8)$.

Наш вывод: 12 — совпадает с ожидаемым. Второй пример особенно полезен: на шагах 6–7 левый и правый указатели стоят на одном товаре, и его две единицы уходят по разной цене.

Крайние случаи

• n = 1. Указатели сразу сходятся. Если порог больше нужного количества, весь товар покупается по 2; если меньше — часть по 2, остаток по 1.
• Все пороги равны 1. Первая единица покупается по 2 (счётчик стартует с нуля), все остальные — по 1.
• Все пороги огромны (больше суммы всех a[i]). Скидка не откроется никогда, ответ — ровно $2 \sum a_i$.
• Порог ровно равен сумме, купленной до него. Проверка bought >= threshold со знаком «не строго» — тут легко потерять рубль, написав строгое неравенство.
• $a_i = 10^{14}$ у одного товара. Проверка на переполнение: стоимость доходит до $2 \cdot 10^{14}$, что требует 64-битного типа, но помещается в него с большим запасом.
• Товары с одинаковыми порогами. Порядок между ними не важен — обменный аргумент ничего не различает при равных порогах.

Типичные ошибки

1. Покупать «лишние» единицы, чтобы быстрее открыть скидку. Соблазнительно, но бессмысленно: лишняя единица стоит не меньше рубля, а счётчик дорастёт до нужного значения и на обязательных покупках.
2. Строгое неравенство left < right. Теряется случай, когда указатели сошлись на одном товаре, и часть его единиц должна уйти по полной цене, а часть — со скидкой.
3. Сортировать по a вместо b. Порядок задаёт именно порог скидки; количество нужных единиц на порядок обслуживания не влияет.
4. 32-битные типы. Количества до $10^{14}$ не помещаются в int, и ошибка проявится не сразу, а на больших тестах.
5. Брать с правого конца больше, чем нужно. Если купить у правого товара всё разом, а до порога левого требовалось меньше, лишние единицы уйдут по 2 рубля вместо 1.
6. Считать, что скидка действует только на «свой» товар. Счётчик общий: единицы любого вида приближают скидку на все виды сразу — на этом и построен весь приём.

Сложность

Время: $O(n \log n)$ — сортировка; проход указателей линейный, поскольку каждый шаг сдвигает один из них или обнуляет остаток. Память: $O(n)$ — массив пар.

---

Самостоятельная тренировка

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

• Codeforces 1369C «RationalLee» (~CF 1400) — есть n целых чисел и k получателей; получатель i должен получить ровно w[i] чисел, а его «радость» равна сумме максимального и минимального из полученных им чисел; нужно максимизировать суммарную радость. Отсортированный массив плюс аккуратное решение, кому достаются самые большие числа, а кому — самые маленькие.
• Codeforces 1792C «Min Max Sort» (~CF 1500) — за одну операцию разрешается взять пару элементов перестановки и отправить меньший в начало, а больший в конец; нужно минимальное число операций, чтобы перестановка стала отсортированной. Пары просятся сами: самый маленький с самым большим, второй с предпоследним — и дальше вопрос только в том, где эта цепочка обрывается.
• Codeforces 1891C «Smilo and Monsters» (~CF 1500) — можно либо убивать по одному, накапливая заряд, либо потратить весь накопленный заряд и убить столько же за один ход; нужно минимизировать количество ходов. Заряд копится на маленьких группах, а тратится на больших — снова два конца отсортированного массива.
• Codeforces 372A «Counting Kangaroos is Fun» (~CF 1600) — даны размеры n объектов; один объект можно спрятать внутрь другого, если тот как минимум вдвое больше; внутри каждого может лежать не более одного, и спрятанный сам ничего вместить не может — нужно минимизировать количество видимых снаружи. Отсортируйте и подумайте, какую половину массива с какой имеет смысл сопоставлять.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

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

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