Сортировка и динамика

Что это за номер

Это самый необычный номер экзамена и стоит он 2 первичных балла. У остальных номеров есть шаблон. Здесь шаблона нет, но есть общая идея: сначала сортируем, а потом идём по данным по порядку.

Простыми словами

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

Как решать любую задачу номера

1. Нарисуй условие. Отрезки на прямой, окошки, коробки. Сплошной текст не решается.
2. Спроси себя: по чему сортировать? Эта мысль всегда первая.
3. Подумай, что выгоднее брать первым. Потом проверь на маленьком примере.
4. Выбери инструмент: таблица или Python.

Таблица или Python

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

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

Правило на экзамене: сначала прикинь, получится ли в таблице. Если понимаешь, что не получается, переходи на Python.

Жадный выбор в таблице

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

Что выгоднее брать первым

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

Решение в таблице

1. Вставь данные в столбцы A (начало) и B (длина). Строку с количеством заявок удали, она не нужна.
2. В столбце C посчитай конец: =A1+B1.
3. Отсортируй всю таблицу по столбцу C по возрастанию.
4. В столбце D храни конец последнего взятого участка. В D1 запиши =C1, а в D2 такую формулу и протяни вниз:

=ЕСЛИ(A2>=D1; C2; D1)

Читается так: если эта заявка начинается не раньше конца последней взятой, берём её, и конец меняется. Иначе всё остаётся как было.

Вот как это выглядит на примере:

Сколько заявок взяли? Столько, сколько разных значений в столбце D. Здесь их 6: это 17, 39, 48, 58, 75, 92.

Второй вопрос: остаток в конце дороги

Часто просят ещё минимальный неубранный кусок в конце дороги. Здесь легко ошибиться: последний взятый участок кончается на 92, но это не значит, что ответ 8. На последнем шаге можно взять любую заявку, которая начинается не раньше конца предпоследней, то есть не раньше 75. Из них берём ту, что кончается позже всех.

Подходят заявки с концами 92 и 98. Самая дальняя кончается на 98, поэтому ответ 100 − 98 = 2. Количество заявок при этом не меняется.

Сортировка в Python

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

data = [[30, 60], [10, 25], [26, 60]]

data.sort()                           # по первому числу
print(data)

data.sort(key=lambda x: x[1])         # по второму числу
print(data)

data.sort(key=lambda x: -x[1])        # по второму, по убыванию
print(data)

data.sort(key=lambda x: (-x[1], x[0]))  # при равенстве по первому
print(data)

Что такое lambda

Это та же функция, только записанная в одну строку. Две записи ниже делают одно и то же:

def f(x):
    return x[1]

lambda x: x[1]

sort берёт каждый элемент списка, подставляет его вместо x и сортирует по тому, что получилось. Минус переворачивает порядок для этого числа. Он удобнее reverse=True: можно перевернуть только одно из нескольких чисел.

Что значит «при равенстве»

Если два элемента равны по первому признаку, они останутся в том порядке, как были. Часто это неверно. Запись (-x[1], x[0]) значит: сначала по второму числу по убыванию, а при равенстве по первому по возрастанию. Это как сортировка по уровням в таблице.

# пиши решение здесь

Окна: проверяем каждое

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

Почему не таблица? Для каждого человека надо проверить все окна, а их могут быть сотни. Здесь нужен цикл.

Что хранить

Пришёл человек в минуту 30. Чтобы понять, свободно ли окно, достаточно знать, когда оно освобождается. Значит, список w хранит для каждого окна минуту, когда оно освободится. Посадили человека, записали его время конца.

data = [(30, 60), (10, 25), (26, 40), (12, 50), (45, 70), (35, 44), (55, 58), (61, 90), (41, 62), (5, 11), (50, 52)]
k = 2

data.sort()              # по времени прихода
w = [-1] * k             # сначала все окна свободны
count = 0
last = 0

for start, end in data:
    for i in range(k):
        if start > w[i]:     # окно уже свободно
            w[i] = end
            count += 1
            last = i + 1     # номера окон идут с единицы
            break            # человек сел, другие окна не проверяем

print(count, last)

Разберём важное:

• data.sort() обязателен: люди приходят по порядку времени. Без него этот же код даст 5 вместо 7, потому что в файле строки идут вперемешку.
• -1 меньше любой минуты, поэтому в начале любое окно свободно.
• break нужен, иначе один человек займёт все окна сразу.
• > или >=? Смотри условие. Если новый может подойти только со следующей минуты, нужно строгое >. Если сразу, то >=.

Цикл идёт от первого окна к последнему, поэтому человек сам садится в окно с наименьшим номером.

Окна двух видов

Если окна принимают разные виды заявок, например нечётные только один сорт, а чётные только другой, цикл идёт с шагом 2: range(1, k + 1, 2) для нечётных и range(2, k + 1, 2) для чётных. Если следующая заявка возможна только через 5 минут после окончания прошлой, условие такое: start >= w[i] + 5.

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

# пиши решение здесь

Таймлайн: плюс один и минус один

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

Заведём список, где номер элемента это минута. Человек пришёл, в этой минуте +1. Ушёл, в следующей -1. Потом идём по минутам и копим сумму: она и равна числу людей в этот момент.

data = [(1, 10), (3, 5), (4, 8), (6, 12), (9, 15), (11, 13), (14, 20), (2, 7)]

a = [0] * 100
for start, end in data:
    a[start] += 1
    a[end + 1] -= 1      # в минуту end человек ещё здесь

now = 0
best = 0
for x in a:
    now += x
    best = max(best, now)
print(best)

Этот приём похож на список расстояний из №23: номер элемента сам несёт смысл. Размер списка бери с запасом. Если минуты идут в пределах суток, хватит 1442 элементов.

# пиши решение здесь

Динамика: цепочка коробок

Теперь самое сложное и самое красивое. Динамика это когда ответ для каждого элемента считается через уже посчитанные ответы для предыдущих. Лучше всего её видно на коробках.

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

Простыми словами

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

Например, коробку 41 можно вложить и в 60, и в 55. У 60 цепочка длиной 1, у 55 длиной 2. Берём лучшую, поэтому у 41 будет 3. А вот в саму 41 коробку 38 вложить нельзя: разница всего 3, поэтому у 38 тоже будет 3.

Самая длинная цепочка в таблице 4. Заканчиваться она может на коробках 25, 21, и нам нужна наибольшая: 25.

a = [60, 55, 41, 38, 25, 21]
k = 5

a.sort(reverse=True)
n = len(a)
chain = [1] * n                  # каждая коробка сама по себе цепочка из одной

for i in range(n):
    prev = [chain[j] for j in range(i) if a[j] - a[i] >= k]
    if prev:
        chain[i] = max(prev) + 1

mx = max(chain)
print(mx, max(a[i] for i in range(n) if chain[i] == mx))

• range(i) перебирает все коробки до текущей, а они больше неё, потому что список отсортирован.
• prev собирает длины цепочек, куда текущая коробка помещается.
• + 1 это сама текущая коробка.

Такой код делает двойной цикл, но в этом номере данных мало, обычно до нескольких тысяч, и скорость не проблема.

# пиши решение здесь

Когда жадный выбор ломается

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

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

a = [(50, 'R'), (47, 'G'), (44, 'R'), (40, 'B'), (38, 'G'), (30, 'B'), (28, 'R'), (26, 'R'), (18, 'R'), (15, 'G')]
k = 3

a.sort(reverse=True)
n = len(a)
chain = [1] * n

for i in range(n):
    prev = [chain[j] for j in range(i)
            if a[j][0] - a[i][0] >= k and a[j][1] != a[i][1]]
    if prev:
        chain[i] = max(prev) + 1

mx = max(chain)
print(mx, max(a[i][0] for i in range(n) if chain[i] == mx))

Изменилось одно условие. В этом и сила способа: новое правило просто дописывается в if.

# пиши решение здесь

Динамика: занятость зала

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

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

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

data = [(10, 40, 5), (35, 50, 4), (45, 70, 9), (20, 30, 2), (55, 65, 3), (72, 80, 6), (60, 95, 8), (82, 90, 7)]

data.sort(key=lambda x: x[1])         # по времени окончания
n = len(data)
best = [[0, 0]] * n                   # [занятое время, сумма]

for i in range(n):
    s, e, p = data[i]
    prev = [best[j] for j in range(i) if s > data[j][1]]
    if prev:
        t, money = max(prev)
        best[i] = [t + e - s, money + p]
    else:
        best[i] = [e - s, p]

print(max(best))

max у списков сравнивает сначала первое число, поэтому ищется наибольшее время.

Динамика: дешёвый маршрут

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

Это почти задача №23, но здесь хватает одного прохода. Переходы идут только вперёд, поэтому если отсортировать их по номеру зоны отправления, к моменту обработки перехода цена зоны отправления уже окончательная.

data = [(1, 2, 10), (1, 3, 6), (1, 4, 14), (2, 4, 5), (2, 5, 20), (3, 4, 3), (3, 5, 18), (4, 5, 9), (4, 7, 30), (5, 7, 12), (5, 8, 40), (6, 8, 1), (7, 8, 6), (8, 9, 50)]
k = 45

data.sort()
cost = [10 ** 9] * 20      # огромное число значит, что сюда не попасть
cost[1] = 0

for a, b, p in data:
    if cost[a] + p <= k:
        cost[b] = min(cost[b], cost[a] + p)

zone = max(i for i in range(20) if cost[i] < 10 ** 9)
print(zone, k - cost[zone])

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

# пиши решение здесь

Двумерная динамика

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

Коробки теперь имеют цену. Нужна самая дешёвая цепочка из ровно q коробок. Одного числа на коробку уже мало: важно, сколько коробок в цепочке. Поэтому строим таблицу: d[t][i] это наименьшая цена цепочки из t коробок, которая заканчивается коробкой i.

Для одной коробки всё просто: цена цепочки равна цене самой коробки. Для t коробок берём самую дешёвую цепочку из t - 1 коробки, куда текущая помещается, и добавляем её цену. Если такой нет, клетка остаётся с огромным числом. В конце выводим цену и наименьший размер последней коробки среди таких цепочек.

a = [(80, 4), (74, 2), (70, 9), (61, 3), (55, 1), (52, 6), (44, 2), (39, 5), (31, 1), (24, 8), (19, 2)]
k = 6
q = 4

a.sort(reverse=True)
n = len(a)
INF = 10 ** 9
d = [[INF] * n for t in range(q + 1)]

for i in range(n):
    d[1][i] = a[i][1]

for t in range(2, q + 1):
    for i in range(n):
        prev = [d[t - 1][j] for j in range(i) if a[j][0] - a[i][0] >= k]
        if prev and min(prev) < INF:
            d[t][i] = min(prev) + a[i][1]

m = min(d[q])
print(m, min(a[i][0] for i in range(n) if d[q][i] == m))

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

Журнал сервера: копим и сбрасываем

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

Простыми словами

Представь ведро заданного объёма. Запросы по очереди наливают в него воду. Если очередная порция не помещается, сначала выливаем всё накопленное: это и есть резервная копия, её объём равен тому, что было в ведре. Потом наливаем новую порцию. Вылитое считается копией только в момент, когда новая порция не влезла, поэтому остаток в конце дня копией не становится.

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

Часть 1. Объём по каждому клиенту

Удобнее всего словарь: ключ это номер клиента, значение это его сумма. После этого вопрос вроде «у кого больше всех» решается через sorted.

Часть 2. Копии

Держим накопленный объём acc. Если acc + s больше вместимости k, записываем копию и обнуляем acc. Время записывается как текст ЧЧ:ММ:СС. Такие строки можно сравнивать прямо как текст: '09:30:00' <= '11:59:59' работает правильно, потому что у всех одинаковая длина и ведущие нули.

log = [('02:00:00', 7, 95), ('03:10:00', 8, 60), ('04:00:00', 7, 30),
       ('09:00:00', 9, 80), ('11:00:00', 8, 40), ('13:00:00', 7, 90)]
k = 100

log.sort()                       # по времени
total = {}
copies = []
acc = 0

for t, c, s in log:
    total[c] = total.get(c, 0) + s
    if acc + s > k:              # не помещается
        copies.append((t, acc))  # копия: время и объём
        acc = 0
    acc += s

print(total)
print(copies)

good = [v for t, v in copies if t <= '11:59:59']
print(sum(sorted(good)[-2:]))    # две наибольшие копии до полудня
print(sum(good[-2:]))            # две последние по времени

Посмотри на вывод. total.get(c, 0) берёт текущую сумму клиента, а если его ещё нет, то 0. Обрати внимание на разницу: две наибольшие копии находим через sorted, а две последние это просто конец списка, потому что копии шли по времени.

Как получить разные вопросы из словаря:

Длинное условие: рейтинг

Бывает задача, где сортировка почти не нужна, зато условие длинное. Главное здесь внимательно разложить его на отдельные проверки. Разберём приём на своём примере.

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

x = [40, 75, 92, 60, 63, 71, 50, 52, 80]
a, b, k = 50, 80, 3

m = x.index(max(x))              # где стоит наибольший
special = []
for i in range(m + 1, len(x) - 1):
    if a <= x[i] <= b and abs(x[i] - x[i + 1]) <= k:
        special.append(x[i])

print(special)
print(1 + sum(v > max(special) for v in x), len(special))

• range(m + 1, len(x) - 1) начинается сразу после наибольшего и заканчивается раньше последнего элемента, ведь у последнего нет следующего соседа.
• abs убирает знак: разница считается в любую сторону.
• Место в рейтинге это единица плюс количество элементов с большим баллом. Равные баллы занимают одно место, поэтому сортировать не нужно. Чем больше балл, тем выше место, значит, наивысшее место у наибольшего из подходящих.

Ловушки

Практика

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

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

# пиши решение здесь