Изучите ограничения и выберите сложность

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

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

Если n не превышает 20, даже экспоненциальный полный перебор укладывается в ограничение. Малые ограничения позволяют без опасений проверить все комбинации.

Если n достигает нескольких сотен, решение с O(n^3) всё ещё проходит. Здесь вполне уместны тройные циклы или простой DP по парам.

При n около 5000 стремитесь к O(n^2). Вложенные циклы по массиву требуют примерно 2,5 · 10^7 шагов, что всё ещё укладывается в бюджет.

Если n достигает 10^5 или 10^6, нужна сложность O(n log n) или O(n). Сортировка, префиксные суммы и два указателя станут Вашими основными инструментами.

Если n равно миллиарду, ни один цикл по n не выдержит. Вам нужна сложность O(log n) или O(1), основанная на математике или двоичном поиске по ответу.

Ограничения на значения тоже важны. Большие числа предупреждают о возможном переполнении в других языках и могут намекать на применение арифметики по модулю.

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

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

Держите эту таблицу в памяти. Связь ограничений со сложностью превращает быстрый взгляд на ограничения в мгновенный план во время соревнований.

Пусть n подскажет Вам подходящую сложность.

Теперь Вы воспринимаете ограничения как цель: малое n допускает полный перебор, для 10^5 нужна сложность n log n, а 10^9 требует логарифма или математики. Пусть n выбирает подход. 🗺️