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

за последние три дня я продолжил изучать 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. различайте правильность и эффективность.

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

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

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

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