Задание 27: эффективный алгоритм анализа последовательности

Главное и самое «дорогое» задание: учимся превращать наивный перебор пар за O(n²) в эффективный проход за O(n) с помощью остатков и префиксных сумм.

Идея эффективного решения: вместо перебора всех пар храните «лучшее, что уже встречалось» для каждого остатка от деления — и комбинируйте на лету за один проход.

Что проверяет задание 27

Задание 27 — высокий уровень, 2 балла (единственное двухбалльное), самое сложное в КИМ. Дана числовая последовательность (часто в двух файлах: A — небольшой, B — очень большой). Нужно найти величину с условием «кратно M», «делится на M», «сумма пары/подотрезка делится на …». Полный балл дают только за эффективное решение — такое, которое успевает обработать большой файл за один-два прохода. Наивное (двойной цикл) на большом файле «не успевает», поэтому за него ставят 1 балл из 2.

Классическая задача: максимальная сумма пары, кратная M

Дана последовательность. Найти максимальную сумму двух элементов, которая делится на M (элементы на разных позициях). Разберём оба решения.

Наивное решение — O(n²)

Перебираем все пары (i, j), проверяем делимость суммы, обновляем максимум. Просто, но для n = 1000000 это триллион операций — слишком долго.

data = [23, 17, 8, 14, 5, 31, 12]
M = 5

# Наивно: все пары
naive = -1
for i in range(len(data)):
    for j in range(i + 1, len(data)):
        if (data[i] + data[j]) % M == 0:
            naive = max(naive, data[i] + data[j])
print("Наивный ответ:", naive)

Вывод:

Наивный ответ: 45

Эффективное решение — O(n) через остатки

Ключевая идея: сумма двух чисел делится на M, если их остатки от деления на M в сумме дают M (или оба нулевые). Значит для каждого числа с остатком r нам нужен партнёр с остатком (M − r) % M. Чтобы сумма была максимальной, для каждого остатка достаточно помнить два наибольших уже встреченных числа (два — потому что партнёр может иметь тот же остаток, и нельзя брать один элемент дважды).

data = [23, 17, 8, 14, 5, 31, 12]
M = 5

# best[r] — два наибольших уже встреченных числа с остатком r
best = [[-1, -1] for _ in range(M)]

def push(r, v):
    if v > best[r][0]:
        best[r][1] = best[r][0]
        best[r][0] = v
    elif v > best[r][1]:
        best[r][1] = v

ans = -1
for x in data:
    r = x % M
    need = (M - r) % M           # нужный остаток партнёра
    if best[need][0] != -1:
        if r == need:            # партнёр с тем же остатком — берём ВТОРОЙ максимум
            if best[need][1] != -1:
                ans = max(ans, x + best[need][1])
        else:                    # партнёр с другим остатком — берём его максимум
            ans = max(ans, x + best[need][0])
    push(r, x)                   # добавляем текущее число в копилку

print("Эффективный ответ:", ans)

Вывод:

Эффективный ответ: 45

Оба решения дали 45 (это 14 + 31 = 45, делится на 5). Но эффективное делает один проход и работает даже на миллионе чисел, а наивное — нет. Совпадение ответов на маленьком примере — лучшая проверка корректности эффективного алгоритма.

Почему два максимума на остаток

Если остаток партнёра совпадает с остатком текущего числа (например, M = 4, оба остатка по 2: 2+2 = 4 делится на 4), то нам нужны ДВА разных числа с этим остатком. Поэтому храним два наибольших: текущее число складываем со вторым максимумом той же группы, иначе можно было бы случайно сложить число само с собой.

Другой частый сюжет: подотрезки с суммой, кратной M (префиксные суммы)

«Сколько непрерывных подотрезков имеют сумму, кратную M?» Наивно — перебор всех пар границ (O(n²)). Эффективно — префиксные суммы по модулю M: сумма подотрезка (i, j] делится на M тогда и только тогда, когда префиксные суммы в точках i и j дают одинаковый остаток. Считаем, сколько раз каждый остаток встречался.

from collections import defaultdict

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
M = 5

cnt = defaultdict(int)
cnt[0] = 1                 # пустой префикс с остатком 0
pref = 0
ans = 0
for x in data:
    pref = (pref + x) % M
    ans += cnt[pref]       # столько прежних префиксов с тем же остатком
    cnt[pref] += 1

print("Подотрезков с суммой, кратной", M, ":", ans)

Вывод:

Подотрезков с суммой, кратной 5 : 11

Каждая пара префиксов с одинаковым остатком задаёт подотрезок с суммой, кратной M. Один проход вместо двойного цикла — это и есть эффективность задания 27.

Стратегия на экзамене

Сначала напишите наивное решение (двойной цикл) и прогоните на маленьком файле A — это гарантированный 1 балл и эталон для проверки.
Затем напишите эффективное (остатки/префиксы) и сверьте ответ на файле A с наивным.
Прогоните эффективное на большом файле B — оно успеет, наивное нет. Это второй балл.

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

Берут один элемент дважды. Для пары с одинаковым остатком нужен второй максимум, а не тот же элемент.
Неверный нужный остаток. Партнёр имеет остаток (M − r) % M; для r = 0 это снова 0, не M.
Сдают только наивное. На большом файле оно не успевает — потеря второго балла.
Забывают cnt[0] = 1 в префиксных суммах. Пустой префикс нужен, чтобы учесть подотрезки от самого начала.

Итог

Задание 27 — за полный балл нужен ЭФФЕКТИВНЫЙ алгоритм (один-два прохода), наивный двойной цикл даёт лишь 1 балл.
Пара, кратная M: для каждого остатка храним два максимума, партнёр имеет остаток (M−r)%M.
Подотрезки, кратные M: префиксные суммы по модулю; пары равных остатков считаем словарём, не забыв cnt[0]=1.