🃏 Разбор карточной задачки: от O(k²) к O(k)!

Пришло время разобрать нашу задачу про карточный турнир.

🤔 Распространённый подход: полный перебор

Самая очевидная стратегия — перебрать все возможные комбинации взятых карт. Мы можем взять:
- k карт слева, 0 справа
- k-1 карт слева, 1 справа
- k-2 карт слева, 2 справа
- ...
- 0 карт слева, k карт справа

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

def max_score_slow(card_points, k):
    max_sum = 0
    n = len(card_points)

    for i in range(k + 1):
        # i - сколько карт берем справа
        # k-i - сколько карт берем слева
        left_sum = sum(card_points[:k - i])
        right_sum = sum(card_points[n - i:])
        max_sum = max(max_sum, left_sum + right_sum)

    return max_sum

Главный минус здесь — многократный вызов sum() внутри цикла. Каждая такая операция сама по себе занимает время, пропорциональное количеству элементов. В итоге общая сложность алгоритма получается O(k²), что может быть медленно на больших данных.

А можно ли быстрее? Конечно!


🚀 Эталонное решение: Скользящее окно за O(k)

Вместо того чтобы каждый раз пересчитывать сумму с нуля, мы можем вычислить её один раз, а затем "сдвигать" наш выбор, обновляя сумму за константное время O(1).

Как это работает?
1. Сначала считаем, что мы взяли первые k карт слева. Это наша первоначальная max_sum.
2. Затем в цикле k раз делаем "обмен": убираем одну карту с конца левой группы и добавляем одну карту справа.
3. На каждом шаге обновляем текущую сумму и сравниваем её с максимальной.

def max_score_fast(card_points, k):
    n = len(card_points)
    
    current_sum = sum(card_points[:k])
    max_sum = current_sum

    for i in range(1, k + 1):
        # Обновляем сумму за O(1):
        # отнимаем крайний левый элемент и прибавляем крайний правый
        current_sum = current_sum - card_points[k - i] + card_points[n - i]
        max_sum = max(max_sum, current_sum)
            
    return max_sum

⏳ Время: O(k). Один начальный подсчет суммы sum(card_points[:k]) занимает O(k), и цикл также выполняется k раз с операциями за O(1).
💾 Память: O(1). Мы храним всего несколько переменных.


💡 Красивая альтернатива: инверсия задачи

Есть и другой, очень изящный способ взглянуть на проблему.

Вместо того чтобы максимизировать сумму k карт, которые мы берём, давайте минимизируем сумму n-k карт в центре, которые мы оставляем на столе.

Задача превращается в "найти непрерывный подмассив длиной n-k с минимальной суммой". Это тоже классическая задача на скользящее окно!

def max_score_inverted(card_points, k):
    n = len(card_points)
    window_size = n - k
    
    total_sum = sum(card_points)
    
    if window_size <= 0:
        return total_sum

    min_subarray_sum = current_sum = sum(card_points[:window_size])

    for i in range(window_size, n):
        current_sum += card_points[i] - card_points[i - window_size]
        min_subarray_sum = min(min_subarray_sum, current_sum)
            
    return total_sum - min_subarray_sum

Этот подход имеет сложность O(N), что тоже отлично. Он особенно хорош, когда k близко к N.

#алгособес

👨‍💻 Главный IT-навык 2025 — не AI

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

Тут издание Course Report провело исследование: проанализировали 12 миллионов (!!!) IT-вакансий на Indeed. И знаете, какой навык самый востребованный?

Держитесь за стулья:

➡️ Microsoft Excel: 531 000 упоминаний
➡️ Python: 67 000 упоминаний
➡️ SQL: 60 000 упоминаний
...
➡️ AI: жалкие 25 000 упоминаний.

Да-да, программа, выпущенная 40 лет назад, упоминается в вакансиях почти в 8 раз чаще, чем Python. И в 21 раз чаще, чем AI.

Как сказал один из экспертов в статье: "За всем блеском чат-ботов и нейросеток стоит старый-добрый Excel. Реальные решения и реальные доллары двигаются именно там".

Так и живём.

Среда — маленькая пятница, а значит, мозг уже можно нагружать по полной. Держите задачку, которая на первый взгляд кажется простой.

Есть список положительных чисел nums.

Цель — добиться минимально возможной разницы между самым большим и самым маленьким элементом в списке.

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

📉 Если число чётное — делим его на 2.
📈 Если число нечётное — умножаем на 2.

Пара примеров:

nums = [1, 2, 3, 4] → разница 1
(Например, можно превратить в [2, 2, 3, 2])

nums = [4, 1, 5, 20, 3] → разница 3
(Можно получить [4, 2, 5, 5, 3])

nums = [2, 10, 8] → разница 3

Ну что, как решать будете?

#алгособес

Разбор задачки: да поможет нам куча! 💪🏻

Самая большая сложность задачи — в двойственности операций. Числа могут как расти, так и убывать. А что, если заставить их двигаться только в одном направлении?

Ключевой трюк: любое нечётное число n можно превратить в 2n, а дальше — только уменьшать. Это значит, что для каждого числа мы можем найти его максимально возможного чётного предка.

Если мы сразу преобразуем все нечётные числа в списке, умножив их на 2, мы получим новую задачу: "Есть список чисел, любое из которых можно поделить на 2, если оно чётное. Найдите минимальную разницу".

Теперь все операции ведут только к уменьшению чисел. Это меняет всё!

⚙️ Как это работает: жадный алгоритм + max-heap

Раз мы можем только уменьшать числа, то для минимизации разницы max - min нам выгодно уменьшать именно max. Этот жадный подход здесь работает идеально.

Алгоритм получается таким:
1️⃣ Нормализация. Создаём новый набор чисел: все нечётные умножаем на 2, чётные оставляем как есть. На этом же шаге находим минимальное значение в этом наборе.
2️⃣ Max-heap. Все полученные числа кладём в max-heap. Она позволит нам получать наибольший элемент за O(1).
3️⃣ Итерации. В цикле, пока текущий максимум остаётся чётным:
- Достаём максимум из кучи.
- Вычисляем текущую разницу и обновляем наш рекорд, если она меньше.
- Делим максимум на 2 и кладём обратно в кучу.
- Не забываем обновить и общий минимум, если новое число оказалось меньше.

Когда максимум в куче становится нечётным, мы останавливаемся, так как уменьшать его больше нельзя.

Вот как эта идея выглядит в коде. Обратите внимание, как в Python эмулируется max-heap с помощью heapq (min-heap), сохраняя отрицательные числа.

import heapq

def minimum_deviation(nums):
    min_val = float('inf')
    max_heap = []

    # Шаг 1: Нормализация и инициализация
    # Превращаем все числа в "максимальных предков" 
    # и сразу находим минимум
    for n in set(nums):
        val = n * 2 if n % 2 != 0 else n
        heapq.heappush(max_heap, -val)
        min_val = min(min_val, val)

    min_deviation = -max_heap[0] - min_val

    # Шаг 2: Итеративно уменьшаем максимум
    while max_heap[0] % 2 == 0:
        max_val = -heapq.heappop(max_heap)
        
        new_val = max_val // 2
        min_val = min(min_val, new_val)
        heapq.heappush(max_heap, -new_val)
        
        current_max = -max_heap[0]
        min_deviation = min(min_deviation, current_max - min_val)

    return min_deviation

Асимптотика:
- Время: O(N * log(MAX_VAL)). Начальное построение кучи O(N). Каждое число может быть поделено log(val) раз, и каждая операция с кучей стоит log(N). Но так как N и MAX_VAL связаны, сложность можно оценить так.
- Память: O(N) для хранения кучи.

Кому хочется подробнее почитать про кучи, то залетайте: Ультимативный гайд по структурам данных и алгоритмам на Python. Часть 5: деревья, BST и heapq 👈🏻

#алгособес

Что именно прилетит в cls?

#квиз

Marimo — как Jupyter, только лучше 😎

Marimo — open-source IDE, которая похожа на привычный Jupyter, но с рядом интересных преимуществ:
🔸при запуске ячейки автоматически запускаются зависимые ячейки (вот это супер удобно!);
🔸ноутбуки сохраняются без вывода ячеек в исполняемом .py формате, что обеспечивает полную совместимость с другими IDE (тоже круто!) и удобное версионирование.
🔸интеграция с git из коробки;
🔸поддерживаются интерактивные элементы;
🔸встроенный менеджер пакетов, GitHub Copilot, AI-ассистенты, Ruff, экспорт в HTML и многое другое.

При этом поддерживает только Python 🐍

В статье разработчик рассказывает про все решения и преимущества.

Попробовать можно так:

pip install marimo && marimo tutorial intro

#тулбокс