Привет!

Благодаря команде Codeforces, участникам теперь доступен PyPy. Он помогает решать задачи, которые CPython ("стандартный" Python) не может (например, 523D - Statistics of Recompressing Videos). Но хотя PyPy практически полностью совместим с CPython, не всегда можно просто поменять язык в настройках и улучшить посылку. Вернемся к вышеупомянутой задаче. На момент написания данного текста я был единственным участником, сдавшим эту задачу на PyPy. На СPython решение не проходило из-за ограничений по времени. Связано это с особенностями реализации ввода/вывода в PyPy и CPython. Об этом уже упомянал hellman_. Дело в том, что чаще всего программы используют raw_input/print, которые реализованы не так эффективно в PyPy, как хотелось бы. Следует использовать sys.stdin/sys.stdout. У меня есть шаблон с таким содержанием:

def read():
    return stdin.readline().rstrip('\n')

def read_array(sep=None, maxsplit=-1):
    return read().split(sep, maxsplit)

def read_int():
    return int(read())

def read_int_array(sep=None, maxsplit=-1):
    return [int(a) for a in read_array(sep, maxsplit)]

def write(*args, **kwargs):
    sep = kwargs.get('sep', ' ')
    end = kwargs.get('end', '\n')
    stdout.write(sep.join(str(a) for a in args) + end)

def write_array(array, **kwargs):
    sep = kwargs.get('sep', ' ')
    end = kwargs.get('end', '\n')
    stdout.write(sep.join(str(a) for a in array) + end)

Изначально эти функции использовали raw_input/print :) Плюс этих функций в том, что они работают одинаково быстро и в PyPy, и в CPython. Более того, и во второй версии, и в третьей!

Второй момент состоит в том, что чем меньше отдельных выводов, тем лучше. Это может сыграть значительную роль! Сравните 2 посылки: 10293678 и 10293685. Лучше писать:

times = [...]
sys.stdout.write('\n'.join(str(t) for t im times) + '\n')
# or
write_array(times, sep='\n')

чем:

times = [...]
for t in times:
    sys.stdout.write(str(t) + '\n')
    # or
    write(t)

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

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

Этим постом я хотел напомнить о том, что есть PyPy, который может немного увеличить Ваши шансы. Если Вам известны еще какие-нибудь способы по улучшения производительности (кроме перехода на C++ или Java :)) или что-либо полезное, напишите, пожалуйста, в комментариях. Спасибо!

UPD: подправил функцию read()