Всем привет!

За последние три дня я почти полностью сосредоточился на BFS по матрицам. Вместо решения большого количества разных тем я старался разобраться именно в том, почему алгоритм работает, где появляются TLE и почему некоторые реализации оказываются значительно быстрее при тех же идеях.

мультистартовый BFS вместо множества отдельных обходов

Главная идея, которую я наконец понял, — если источников несколько, не нужно запускать BFS отдельно от каждого.

Изначально я рассматривал вариант, где после нахождения каждого источника запускался свой обход. Такой подход может проходить по одним и тем же клеткам много раз.

Если источников $$$k$$$, то в худшем случае получается

Правильный вариант — сразу добавить все источники в очередь, присвоить им расстояние 0 и выполнить только один BFS.

from collections import deque

q = deque()

for i in range(n):
    for j in range(m):
        if a[i][j] == 2:
            dist[i][j] = 0
            q.append((i, j))

После этого волны распространяются одновременно от всех источников.

Сложность становится

где это применяется

Такой приём встречается очень часто:

• несколько выходов;
• несколько источников заражения;
• несколько пожаров;
• несколько стартовых вершин графа;
• поиск расстояния до ближайшего объекта.

Если в условии написано «есть несколько одинаковых стартовых точек», почти всегда стоит подумать о мультистартовом BFS.

почему первое найденное расстояние уже минимальное

Ещё один момент, который я раньше понимал не до конца.

BFS обрабатывает вершины слоями.

Сначала обрабатываются все клетки с расстоянием 0.

Потом — все клетки с расстоянием 1.

Потом — расстояние 2 и так далее.

Из-за этого, если вершина впервые получила значение

dist[nx][ny] = dist[x][y] + 1

то более короткий путь уже не сможет появиться позже.

Поэтому достаточно проверять только непосещённые клетки.

if dist[nx][ny] == -1:
    dist[nx][ny] = dist[x][y] + 1
    q.append((nx, ny))

Это намного проще, чем постоянно пытаться улучшать расстояния.

типичная ошибка

Во время реализации я использовал конструкцию вида

if dist[nx][ny] > dist[x][y] + 1:
    ...
elif dist[nx][ny] == -1:
    ...

Для обычного BFS она не нужна.

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

Лишние проверки только усложняют код и могут запутать при отладке.

небольшая диагностическая задача

После блока по BFS я начал проверять базовые навыки на более простых задачах.

Например, была задача на поиск самого длинного неубывающего непрерывного отрезка массива.

Во время решения получилось несколько вариантов с WA.

Полезный вывод оказался простым: перед тем как менять код, стоит проверить несколько крайних случаев вручную:

• массив полностью возрастающий;
• массив полностью убывающий;
• ответ заканчивается последним элементом;
• несколько максимальных отрезков одинаковой длины.

Именно такие тесты чаще всего находят ошибки в индексах и обновлении ответа.

что дальше

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

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

Всем привет!

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

Сейчас я начал смотреть на такие задачи немного иначе. Вместо того чтобы сразу писать код или пытаться представить все вызовы функции, я сначала разбираю смысл состояния.

Что я начал делать перед написанием рекурсии

Теперь перед кодом я стараюсь ответить на четыре вопроса:

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

Например, если функция решает задачу для числа $$$n$$$, то следующий вызов обычно должен работать с меньшим значением: $$$n-1$$$, $$$n/2$$$ или другой более простой версией состояния.

Самое важное — рекурсия не должна вызывать сама себя бесконечно. Поэтому нужен базовый случай.

Простой пример:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Здесь функция решает задачу для $$$n$$$ через уже более простую задачу для $$$n-1$$$.

Формула выглядит так:

Базовый случай:

Раньше я просто запоминал такой код. Сейчас уже лучше понимаю, зачем нужна каждая его часть.

Ветвящаяся рекурсия

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

Хороший пример — биномиальные коэффициенты.

Для них используется формула:

Базовые случаи:

• $$$k=0$$$;
• $$$k=n$$$.

В обоих случаях ответ равен $$$1$$$.

def combinations(n, k):
    if k == 0 or k == n:
        return 1
    return combinations(n - 1, k - 1) + combinations(n - 1, k)

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

Именно на таких задачах я начал лучше понимать, почему правильная формула ещё не гарантирует быстрое решение.

Мемоизация и повторяющиеся состояния

Некоторые рекурсивные решения у меня получали TLE, хотя сама идея была правильной.

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

Например, при вычислении биномиальных коэффициентов вызов с одинаковыми значениями n и k может появляться снова и снова.

Для таких случаев можно использовать мемоизацию:

from functools import cache

@cache
def combinations(n, k):
    if k == 0 or k == n:
        return 1
    return combinations(n - 1, k - 1) + combinations(n - 1, k)

Теперь результат каждого состояния сохраняется.

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

После этого я начал задавать себе полезный вопрос:

Не решаю ли я одну и ту же маленькую задачу несколько раз?

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

Ханойские башни

Долгое время я не мог нормально понять задачу о Ханойских башнях.

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

Мне помогло визуальное объяснение на YouTube. После него я наконец увидел три основных шага:

1. перенести $$$n-1$$$ дисков с начального стержня на вспомогательный;
2. перенести самый большой диск на конечный стержень;
3. перенести $$$n-1$$$ дисков со вспомогательного стержня на конечный.

То есть задача для $$$n$$$ дисков сводится к двум задачам для $$$n-1$$$ дисков.

Количество действий задаётся рекуррентной формулой:

Итоговое количество перемещений:

После того как я понял именно эти три шага, код уже стал намного понятнее:

def hanoi(n, start, finish, auxiliary):
    if n == 1:
        print(start, finish)
        return

    hanoi(n - 1, start, auxiliary, finish)
    print(start, finish)
    hanoi(n - 1, auxiliary, finish, start)

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

Первое настоящее понимание DFS

После обычной рекурсии я начал разбирать обходы графов.

Одна из задач была связана с комнатой или лабиринтом, представленным в виде таблицы.

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

• каждая доступная клетка — это вершина графа;
• переход в соседнюю клетку — это ребро;
• вся доступная область — компонент связности.

Функция DFS делает примерно следующее:

1. проверяет, можно ли зайти в клетку;
2. отмечает её как посещённую;
3. запускается для соседних клеток.

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return 0

    if grid[x][y] == '#':
        return 0

    if visited[x][y]:
        return 0

    visited[x][y] = True

    result = 1
    result += dfs(x + 1, y)
    result += dfs(x - 1, y)
    result += dfs(x, y + 1)
    result += dfs(x, y - 1)

    return result

Идею можно записать так:

где $$$u$$$ — ещё не посещённые соседи вершины $$$v$$$.

Зачем отмечать посещённые клетки

Раньше я не до конца понимал, почему массив visited настолько важен.

Теперь вижу сразу две причины.

Во-первых, без отметки посещённых вершин алгоритм может ходить по кругу:

A -> B -> A -> B -> ...

Во-вторых, одна и та же клетка может быть посчитана несколько раз.

Поэтому вершину нужно отмечать посещённой сразу после входа в неё, а не после обхода всех соседей.

Это небольшая деталь, но без неё DFS может работать неправильно или вообще не завершиться.

Деревья и правильное хранение данных

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

Изначально данные было удобно читать в виде:

сообщение -> родитель

Но для удаления всех потомков это хранение неудобно.

Гораздо полезнее построить обратную структуру:

родитель -> список детей

Например:

children = [[] for _ in range(n)]

for child, parent in relations:
    children[parent].append(child)

После этого удаление всех ответов превращается в обычный обход поддерева:

def remove_subtree(v):
    removed[v] = True

    for child in children[v]:
        remove_subtree(child)

Это помогло мне понять важный принцип:

Иногда главная сложность задачи не в алгоритме, а в том, как представить исходные данные.

Если хранение выбрано правильно, само решение может оказаться очень коротким.

Какие ошибки я исправил

За эти дни я заметил несколько повторяющихся ошибок в своём коде.

1. Печать вместо возврата значения

Иногда я писал рекурсивную функцию, которая сразу что-то печатала, хотя дальше результат нужно было использовать в вычислениях.

Теперь стараюсь разделять:

• вычисление результата через return;
• вывод результата через print.

Например, лучше так:

def sum_digits(n):
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)

print(sum_digits(12345))

2. Лишние глобальные переменные

Глобальные переменные могут сделать решение сложнее для понимания и отладки.

Теперь стараюсь передавать нужные данные в аргументах функции или возвращать результат.

3. Неправильный выбор структуры данных

Если нужны быстрые проверки принадлежности, лучше использовать set.

used = set()

if value in used:
    ...

В среднем проверка через множество работает за $$$O(1)$$$, тогда как поиск в списке занимает $$$O(n)$$$.

4. Попытка изменить строку

Я ещё раз закрепил, что строки в Python неизменяемые.

Так делать нельзя:

s[0] = 'a'

Нужно создавать новую строку или сначала преобразовывать её в список.

s = list(s)
s[0] = 'a'
s = ''.join(s)

5. Слишком раннее написание кода

Иногда я начинал писать решение, ещё не определив:

• что является вершиной;
• какие существуют переходы;
• что хранит функция;
• какие состояния уже посещены.

Теперь стараюсь сначала построить модель задачи, а потом переходить к реализации.

Практические советы для других новичков

Вот несколько вещей, которые действительно помогли мне лучше понять рекурсию.

Сначала придумайте смысл функции

Не начинайте с первой строки кода.

Сначала сформулируйте словами:

dfs(v) возвращает размер области, достижимой из вершины v.

Или:

solve(n) возвращает ответ для задачи размера n.

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

Не пытайтесь держать в голове всё дерево вызовов

Рекурсивная функция должна правильно решать текущую задачу, предполагая, что меньшая задача уже решается правильно.

Это намного легче, чем вручную представлять сотни вызовов.

Проверяйте уменьшение задачи

Каждый рекурсивный вызов должен приближаться к базовому случаю.

Например:

solve(n - 1)

обычно безопаснее, чем:

solve(n)

Второй вариант может привести к бесконечной рекурсии.

Рисуйте маленькие примеры

Для $$$n=3$$$ или маленькой таблицы удобно нарисовать дерево вызовов на бумаге.

Это помогает увидеть:

• повторяющиеся состояния;
• порядок вызовов;
• момент возврата из функции;
• необходимость visited.

Всегда оценивайте сложность

Даже правильная рекурсия может быть слишком медленной.

Если из каждого состояния появляются два новых вызова, сложность может быть близка к $$$O(2^n)$$$.

Если все состояния сохраняются и каждое вычисляется один раз, решение часто ускоряется до $$$O(n)$$$ или $$$O(nk)$$$.

Что дальше

В следующие дни хочу закрепить:

• DFS на графах;
• DFS на двумерных таблицах;
• поиск компонент связности;
• обход деревьев;
• BFS и очередь;
• первые задачи на динамическое программирование.

Особенно хочу научиться быстрее определять модель задачи ещё до написания кода:

• массив;
• граф;
• дерево;
• сетка;
• состояние динамического программирования.

Главный вывод за эти три дня:

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

функции, множества и почему правильного решения иногда недостаточно

за последние три дня я продолжил изучать python и решать задачи на informatics и atcoder. основными темами стали функции, множества, работа с вещественными числами, сортировка и оценка сложности алгоритмов.

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

много времени ушло на:

• поиск ошибок;
• чтение и понимание условий;
• разбор новых конструкций python;
• исправление WA;
• оптимизацию решений после TLE.

функции в python

я подробнее разобрал функции и понял, что функция — это не просто способ сократить программу. она помогает отделить одну логическую часть решения от другой.

общий вид функции:

def function_name(parameters):
    # действия
    return result

особенно важно понимать разницу между print() и return.

print() только выводит значение на экран, а return возвращает результат туда, откуда была вызвана функция.

например, функция проверки числа на простоту может вернуть строку prime или composite, после чего основная часть программы выведет этот результат.

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

мой первый серьёзный tle на проверке простого числа

в задаче на проверку простоты числа моё первое решение перебирало все возможные делители от 2 до n - 1.

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

первоначальная сложность была:

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

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

если число составное, его можно представить в виде:

если бы одновременно выполнялось:

и

то получилось бы:

что невозможно.

значит, хотя бы один делитель составного числа не превышает $$$\sqrt{n}$$$.

после такой оптимизации сложность становится:

для числа около двух миллиардов это примерно 45 тысяч проверок вместо миллиардов.

ещё удобнее не вычислять квадратный корень через float, а использовать условие:

divisor * divisor <= n

так алгоритм остаётся полностью целочисленным.

множества и быстрый поиск

ещё одной важной темой стали множества set.

я использовал их для:

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

пересечение двух множеств:

common = first & second

количество общих различных элементов:

len(first & second)

важный момент: множество не хранит элементы в отсортированном порядке.

если по условию общие элементы нужно вывести по возрастанию, требуется:

print(*sorted(common))

здесь sorted() создаёт отсортированный список, а * распаковывает его элементы и передаёт их в print() как отдельные аргументы.

ещё я получил TLE в задаче, где для каждого числа проверял его наличие в обычном списке.

поиск в списке в худшем случае работает за:

если делать его для каждого элемента, общая сложность становится:

правильная идея — идти слева направо и хранить уже встреченные значения в пустом множестве seen.

проверка наличия элемента в set в среднем работает за:

поэтому весь алгоритм становится линейным:

это был хороший пример того, что после TLE нужно менять не отдельную строку, а сам подход.

вещественные числа и погрешность

в задаче про индекс массы тела я сначала использовал обычные вычисления с float.

формула bmi:

на граничном тесте, где bmi математически равен ровно 25, программа могла получить значение:

24.999999999999996

из-за этого условие bmi >= 25 давало неправильный ответ.

в этой задаче оказалось лучше полностью убрать вещественные числа.

условие:

можно преобразовать в:

после этого сравниваются только целые числа, поэтому погрешность исчезает.

я также разобрал сравнение вещественных чисел через eps.

два числа можно считать равными, если:

в python:

abs(a - b) <= eps

но теперь перед использованием eps я сначала проверяю, нельзя ли преобразовать формулу и перейти к целым числам.

стабильная сортировка

ещё я подробнее разобрал sorted() и .sort().

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

например, если два ученика имеют одинаковый средний балл, тот, кто находился раньше во входных данных, останется раньше и после сортировки.

разница между способами:

• sorted() создаёт новый список;
• .sort() изменяет существующий список;
• .sort() возвращает None.

я также научился сортировать объекты сразу по нескольким признакам с помощью кортежа:

key=lambda student: (
    student.class_number,
    student.class_letter,
    student.surname
)

python сначала сравнивает номер класса, затем букву и только потом фамилию.

что я понял за эти дни

главный вывод — написать логически правильное решение недостаточно.

нужно ещё проверить:

• сколько операций оно выполнит;
• подходит ли сложность под ограничения;
• можно ли заменить вложенные циклы множеством;
• не возникает ли погрешность из-за float;
• требуется ли сохранять порядок равных элементов;
• правильно ли я понял формулировку задачи.

раньше я чаще сразу начинал писать код. теперь стараюсь сначала сформулировать идею и оценить её сложность.

советы другим новичкам

1. смотрите на ограничения до написания кода.

если $$$n$$$ около $$$10^5$$$, решение за $$$O(n^2)$$$ почти наверняка не пройдёт.

1. не используйте список для большого количества проверок x in collection.

когда порядок не важен, для быстрых проверок обычно лучше подходит set.

1. не применяйте рекурсию только потому, что задача находится в разделе про функции.

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

1. проверяйте граничные случаи при работе с float.

число, которое математически равно 25, в памяти может оказаться немного меньше.

1. по возможности переходите к целым вычислениям.

преобразование формулы часто делает решение надёжнее.

1. после tle ищите повторяющуюся дорогую операцию.

ускорение ввода не спасёт алгоритм с неправильной асимптотикой.

1. различайте правильность и эффективность.

решение может давать правильный ответ на маленьких тестах, но не выдерживать максимальные ограничения.

планы на следующие дни

• закончить задачи по функциям;
• лучше разобраться с рекурсией;
• решить задачи на быстрое возведение в степень;
• изучить рекурсивный и итеративный варианты чисел фибоначчи;
• научиться оценивать сложность решения до написания кода;
• продолжать сначала пытаться решить задачу самостоятельно и только потом брать подсказку.

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

всем привет! меня зовут коал. вчера я решил свою первую и уж точно не последнюю задачу на кодфорсес. она была А уровня и достаточна проста для див3. очень нравится этим заниматься поэтому целыми днями это делаю. сейчас решаю задачки на информатиксе и смотрю лекции Хирьянова.

в планах пройти муниципальный этап в 2026 году, а в 2027 году стать призером или победителем всероса по программированию. пару раз в неделю буду точно писать в мой блог чтобы было куда выложить свои мысли.

всем трудных, но решаемых задач <3