1. Так выходит, что у меня еще ни одна задача на графах на питоне с первого раза не проходила по времени. Но раньше получалось в итоге оптимизировать код так, чтоб ограничения проходились: уменьшение числа используемых структур, отказ от туплов, отказ от двойной индексации, отказ от вспомогательных функций etc. В этой же задаче отказ от двойной индексации вылился бы в боль при реализации перемещения квадратика, может быть это и спасло бы

2. • Медленность питона выливается в плохую константу. Но я, к сожалению, слабо представляю, как можно было бы оценивать эту константу оверхеда при разработке задач. Может можно реализовывать на плюсах и пытаться оценить как-то время расставляя множители оверхеда в операциях в зависимости от используемых структур и высчитывать результирующее время. Тогда можно было бы ставить время для разных языков свое. Но это какой-то глубокий анализ, и непонятно возможно ли такое сделать
   • Можно было бы сделать, например, более долгий тест (например, матричка не 500x500, а 800x800), где решение на плюсах с плохой асимптотикой все равно не проходило бы, а решение на питоне даже с такой константой проходило. Но опять же, хоть приблизительная оценка константы все равно нужна. И вполне возможно, что тогда тесты будут не по 3, а по 10 секунд, а это будет значить более долгое ожидание результата

Соглашусь, нужно изначально оценить сложность и научиться прикидывать константу до выбора языка реализации. Наверное, так и буду поступать. Была мысль, что буду все задачи на питоне писать. Но теперь придется пересмотреть эту мысль и учиться писать быстро на плюсах или джаве. Думаю, что все-таки для pypy соотношение не 100 к 1, а примерно 10 к 1. Это я исхожу из наблюдений к этой задаче, и что все-таки для других задач на графах я таки вкладывалась во время 1.5 секунды и максимальное время на тест было все же не в 100 раз больше максимального времени у среднего решения на плюсах.

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

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

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