Почему TLE: как ускорить решение на Python

TLE (Time Limit Exceeded) означает, что программа не успела ответить за отведённое время. Ответ при этом может быть правильным — судья просто не стал его ждать. Начинать надо со сложности алгоритма: ускорение чтения и печати даёт секунды, а смена способа решения — порядки.

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

Что смотреть по порядку

Сложность алгоритма

Двойной цикл по массиву из 100 000 элементов — это 10 миллиардов шагов, столько не успевает ни один язык. Ускорять надо не строки кода, а сам способ: сумма на отрезке берётся префиксными суммами, поиск значения — бинарным поиском или множеством, пары — двумя указателями.

Медленный ввод

input() в цикле на сотне тысяч строк заметно медленнее, чем sys.stdin.readline или чтение всего потока разом через sys.stdin.read().split(). Это не решает задачу с плохой сложностью, но снимает лишние секунды у хорошей.

Печать по одной строке

print внутри длинного цикла тратит время на каждый вызов. Ответы собираются в список и печатаются одним '\n'.join(...).

Строка, которая растёт в цикле

s += кусок внутри цикла каждый раз собирает новую строку. Куски копятся в списке и склеиваются один раз в конце.

Поиск в списке вместо множества

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

Рекурсия там, где хватает цикла

Глубокая рекурсия в Python стоит дорого и упирается в предел глубины; обход в ширину или явный стек и быстрее, и не падает.

Как прикинуть, успеет ли решение

Грубая оценка, которой хватает на школьном этапе: за секунду Python успевает порядка 10 миллионов простых операций. Возьмите максимальный размер данных из условия и посчитайте, сколько шагов делает ваш цикл. Сто тысяч элементов и один проход — это 100 тысяч шагов, укладывается с огромным запасом; сто тысяч и вложенный цикл — 10 миллиардов, не укладывается ни при какой оптимизации строк.

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

Частые вопросы

Python слишком медленный для олимпиад?

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

Поможет ли sys.stdin.readline?

Поможет, если задача упирается в объём ввода: чтение сотни тысяч строк через input() заметно дороже. Задачу с квадратичным алгоритмом это не спасёт.

TLE или бесконечный цикл?

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

Рядом

почему WA — неверный ответ, что значат вердикты судьи. Разобрать приём целиком — каталог задач с разбором; маршрут с нуля — «С нуля до олимпиады».