Признаки в формулировке: какие слова на какой метод указывают

Если ты по формулировке сразу называешь кандидата в методы и проверяешь его условие, листай до «Теперь сам».

Как думаешь, какой это метод

Конвейер из 12 заданий нужно разрезать на 4 смены подряд, не переставляя задания. Длительность смены - сумма её заданий. Нужно, чтобы самая длинная смена была как можно короче.

Какой метод напрашивается? Ответь себе до чтения.

Ключевые слова - «самая длинная… как можно короче», то есть минимизировать максимум. Это почти всегда двоичный поиск по ответу из раздела 6: вместо «найди лучший разрез» спрашивают «можно ли уложиться в смены длиной не больше L», и на этот вопрос жадный проход отвечает за один просмотр. Жадность здесь верна: она закрывает смену как можно позже, поэтому её i-я смена кончается не раньше i-й смены любого другого допустимого разреза - и если какой-то разрез укладывается в k смен, жадный тоже уложится.

На что это похоже

Врач на приёме. Жалоба «болит справа внизу живота» - сразу гипотеза: аппендицит. Но врач не режет по одной жалобе - он проверяет признаки, которые гипотезу подтверждают или опровергают. Признак в формулировке задачи работает так же: он называет первого кандидата, а условие метода - анализ, который кандидата подтверждает.

Механизм: признак → кандидат → условие

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

Правило

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

Разбор: «минимизировать наибольшее» и поиск по ответу

Конвейер из начала урока. Перебор пробует все способы разрезать список на k кусков подряд; поиск по ответу двоично ищет наименьшее L, при котором жадная нарезка укладывается в k смен. Условие метода - монотонность: если смены длиной L хватает, хватит и L + 1. Оно выполняется: более длинная смена вмещает всё, что вмещала короткая. Второе условие молчаливое: проверка «хватает ли L» должна быть дешёвой, ведь её зовут на каждом шаге поиска. Здесь она - один жадный проход по списку.

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

schet = [0, 0]     # [вариантов у перебора, проверок у поиска по ответу]

def hvataet(a, k, limit):
    # жадно: набиваем часть, пока сумма не превысит limit;
    # хватит ли k частей
    schet[1] = schet[1] + 1
    chastej = 1
    tekushchaya = 0
    for x in a:
        if x > limit:
            return False
        if tekushchaya + x > limit:
            chastej = chastej + 1
            tekushchaya = x
        else:
            tekushchaya = tekushchaya + x
    return chastej <= k

def po_otvetu(a, k):
    # ответ монотонен: если хватает limit, хватает и limit + 1.
    # Смена короче самого длинного задания невозможна, а смена
    # длиной во всю сумму хватает всегда - это границы поиска
    lo = max(a)
    hi = sum(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if hvataet(a, k, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def perebor(a, k, nachalo):
    # все способы разрезать a[nachalo:] на k кусков; лучший максимум
    if k == 1:
        schet[0] = schet[0] + 1
        s = 0
        for i in range(nachalo, len(a)):
            s = s + a[i]
        return s
    luchshij = sum(a)
    s = 0
    for konec in range(nachalo, len(a) - k + 1):
        s = s + a[konec]
        ostatok = perebor(a, k - 1, konec + 1)
        luchshij = min(luchshij, max(s, ostatok))
    return luchshij

a = [7, 2, 5, 10, 8, 3, 9, 4, 6, 1, 8, 5]
for k in [2, 3, 4, 6]:
    schet[0] = 0
    schet[1] = 0
    p = perebor(a, k, 0)
    b = po_otvetu(a, k)
    print("k =", k, "| перебор:", p, "вариантов", schet[0],
          "| по ответу:", b, "проверок", schet[1])

k = 2 | перебор: 35 вариантов 11 | по ответу: 35 проверок 6
k = 3 | перебор: 24 вариантов 55 | по ответу: 24 проверок 5
k = 4 | перебор: 20 вариантов 165 | по ответу: 20 проверок 6
k = 6 | перебор: 14 вариантов 462 | по ответу: 14 проверок 6

Ответы совпадают, а работа расходится. Перебор считает все способы поставить k − 1 разрез в 11 щелей между заданиями - C(11, k − 1): 11, 55, 165, 462, и при сотне заданий это астрономия. Поиск по ответу делает около log₂(сумма) проверок - здесь сумма 68, проверок 5-6 - и каждая стоит один проход по списку, при любом k. Признак «минимизировать максимум» привёл к методу, а проверенная монотонность сделала его правильным. Программа находит только длину самой длинной смены; сами разрезы даёт тот же жадный проход с найденным L: где начиналась новая часть, там и разрез. Если частей вышло меньше k, недостающие разрезы ставят внутри частей из двух заданий и больше - максимум от этого не вырастет.

Разбор: «кратчайший», но не поиск в ширину

Доставка со склада 0 в точки 1-4. Задача звучит как «найди кратчайший маршрут» - признак поиска в ширину. Но у дорог разное время: прямая дорога в точку 4 стоит 50 минут, а обход через 1, 2 и 3 - по 10.

def bfs(n, rebra, s):
    # число рёбер до каждой вершины и цена этого пути
    sosedi = []
    for i in range(n):
        sosedi.append([])
    for r in rebra:
        sosedi[r[0]].append([r[1], r[2]])
    rebr = [-1] * n
    cena = [0] * n
    rebr[s] = 0
    ochered = [s]
    golova = 0
    while golova < len(ochered):
        v = ochered[golova]
        golova = golova + 1
        for p in sosedi[v]:
            if rebr[p[0]] == -1:
                rebr[p[0]] = rebr[v] + 1
                cena[p[0]] = cena[v] + p[1]
                ochered.append(p[0])
    return cena

def dijkstra(n, rebra, s):
    # простая версия за V²: каждый раз ищем ближайшую необработанную.
    # beskonechnost больше любого пути: здесь пути - минуты доставки
    beskonechnost = 10 ** 9
    dist = [beskonechnost] * n
    gotova = [False] * n
    dist[s] = 0
    for shag in range(n):
        v = -1
        for u in range(n):
            if not gotova[u] and (v == -1 or dist[u] < dist[v]):
                v = u
        gotova[v] = True
        for r in rebra:
            if r[0] == v and dist[v] + r[2] < dist[r[1]]:
                dist[r[1]] = dist[v] + r[2]
    return dist

# склад 0, точки 1-4; [откуда, куда, минуты]
rebra = [[0, 4, 50], [0, 1, 10], [1, 2, 10], [2, 3, 10], [3, 4, 10],
         [0, 2, 35]]
print("поиск в ширину, цена пути с наименьшим числом рёбер:",
      bfs(5, rebra, 0))
print("Дейкстра, наименьшая цена:                          ",
      dijkstra(5, rebra, 0))

поиск в ширину, цена пути с наименьшим числом рёбер: [0, 10, 35, 45, 50]
Дейкстра, наименьшая цена:                           [0, 10, 20, 30, 40]

Поиск в ширину честно нашёл путь с наименьшим числом рёбер: до точки 4 - одно ребро за 50 минут, до точки 2 - одно ребро за 35. Но вопрос был про минуты, а не про рёбра: через 1-2-3 выходит 40 минут, а путь поиска в ширину на четверть длиннее. Слово «кратчайший» совпало, а условие поиска в ширину - все рёбра одной цены - нет. Это граница правила в действии: признак без проверки условия даёт ответ, который выглядит правильным и не является им.

Что ломается без этого

Метод по слову без условия. Поиск в ширину на взвешенном графе, Дейкстра с отрицательными весами, двоичный поиск по немонотонному признаку - каждый может дать правдоподобный неверный ответ, и даст его без ошибок и предупреждений. Случайно верный ответ на одних данных ничего не доказывает о других.

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

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

Зачем это в работе

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

Теперь сам

1. «Расставь k вышек связи в любых точках дороги так, чтобы самое большое расстояние от дома до ближайшей вышки было наименьшим». Кандидат и его условие?
2. «Сколько существует способов подняться на лестницу из n ступенек шагами по 1 и 2?» Кандидат?
3. Лабиринт, каждый шаг стоит 1, но в некоторых клетках можно телепортироваться в другую клетку за 0. Подходит ли обычный поиск в ширину?