Конкурс по программированию от Яндекса
В последние дни в жизни творился бардак. В пятницу по непонятным причинам проспал 12 часов и установил антирекорд сна: подъем в 16 часов (предыдущий был в 15:20 или 15:30). Скорее всего, повлияло солнечное затмение. Вообще, не раз замечал, что во время затмений, даже не видимых у нас, в жизни творится разная ерунда. Интересно, почему? Следующей ночью спать не хотелось совсем где-то часов до четырех, и, в итоге, засиделся до 6 утра. Суббота выпала из-за сходки, которую описывал в предыдущем сообщении. После сходки попытался лечь рано, но результат оказался совершенно не тем: проснулся около трех часов ночи, и сидел в Сети до 9 утра, потом снова вырубился. А осттаок дня провел в совершенно неработоспособном состоянии.
И только сегодня режим начал начала налаживаться: пронулся бодрым, довольным и работоспособным. Воспользовавшись этим, решил принять участие в конкурсе по программированию от Яндекса, напоминание о котором пришло еще в пятницу. Но перед этим немного подготовился: сначала посидел в медитации, чтобы достичь максимальной сосредоточенности, потом — сделал небольшую зарядку, чтобы разогнать кровь, потом — пообедал, чтобы потом не отвлекаться, так как на выполнение заданий дается пять часов. И только после этого пошел на сайт конкурса.
Наученный опытом предыдущих конкурсов, прочитал условия всех задач сразу. Достаточно быстро понял, что две — легкие, одна — под вопросом, и одна — относительно сложная. Поразмыслив еще немного и поискав информацию по третьей задаче, решил приступить ко второй. Конкретно эту задачу стал решать на C (причем чистом, не C++), так как ограничение памяти в 64 Мб казалось довольно серьезным, и хотелось контролировать ее распределение явно. (Впрочем, потом стало ясно, что памяти там давалось с большим запасом, это я, прикидывая объем, перепутал порядки, поэтому и решил, что мало.) И где-то через час задача №2 была решена. Из предыдущего опыта я знал, что в Яндексе никак нельзя выводить отладочную информацию, поэтому загружая решение на сайт, очень опасался, а вдруг что-то пойдет не так. Но не так пошло только одно: я сначала неправильно указал язык программирования — Python вместо C. Но тут же это исправил, и с удивлением увидел, что задача решена правильно и полностью!
После этого взялся за задачу №1. Сначала казалось, что решить ее тоже достаточно просто. Но когда я написал код и отладил его на локальном компьютере, обнаружил, что придуманный мной алгоритм не справляется с ситуацией, когда в качестве максимумов оказываются несколько расположенных рядом одинаковых значеий. В этом случае он находит неоптимальное решение. В результате задача проходила только два первых теста. Я решил ее отложить, и переключился на задачу №3, благо к тому времени уже пришло понимание, как ее решать. Как водится, в самом начале, читая условие, я все усложнил (так как по опыту предыдущего конкурса ожидал более сложных задач). В реальности там все было достаточно просто, но в какой-то момент возникла заминка с выполнением поворота фигуры относительно центра координат. Очевидно, что это надо было делать через полярные координаты. Формул их я, конечно же, не помню, поэтому потратил какое-то время на поиск решения. А когда нашел, сделал небольшой тест, и несколько затупил, анализируя результаты. Потом оказалось, что я неправильно рисовал фигуру на бумаге, а программа как раз поворачивала все правильно. Но на осознание этого ушло минут десять.
Но вот наконец задача №3 была готова, когда до конца оставалось еще 2 часа времени. Я думал, что все под контролем, успею и попробовать решить четвертую, и доделать первую, но тут случилось непредвиденное. Моя программа для задачи №3 не прошла седьмой тест! Причем, в отличие от CodinGame, в Яндексе нельзя посмотреть тесты, и понять, с чем алгоритм не справляется. Остается только лишь гадать. Я подумал, что, возможно, нужно было сделать еще зеркальные отображения фигуры, срочно добавил их, потом предположил, что накапливается погрешность из-за чисел с плавающей точкой, и принял меры против этого, но все было безрезультатно. Так и осталось для меня загадкой, что же такого было в этом седьмом тесте…
Тем не менее, на все эти доделки я потерял еще минут двадцать. Но, самое главное, если до этого я только слегка нервничал из-за времени, теперь стал паниковать уже серьезно. Кроме того, домой пришел отец и стал меня отвлекать. Да и вообще, нервы были на пределе, и любой шум очень раздражал. Пришлось даже окно закрыть. После этого я взялся за задачу №4, на оптимизацию. Перечитав ее условие еще раз, понял, что она тоже проще, чем я подумал изначально, так как сначала не обратил внимание на одно существенное уточнение. Потом сделал так: сначала применил «жадный» алгоритм, который искал минимум для каждого оставшегося свободным варианта. Прогнал тесты, но они были составлены хитро: жадные алгоритмы на них сразу же проваливались. Но я был к этому готов, и сразу же дописал вторую часть, которая искала худший вариант и делала перестановку с кем-либо из других кандидатов, если это приводило к улучшению результата у одного и не сильно ухудшало результат другого. Увы, это привело к тому, что алгоритм стал зацикливаться. С этим я провозился до момента, когда до конца оставалось чуть больше 20 минут. К этому врмени уже плохо соображала голова, и я путался в куче сущностей, даже навводил кучу вспомогательных переменых, чего обычно не делаю. И то до конца не решил, а скорее сделал решение из категории «костыль». Увы, то, что получилось, не работало корректно даже на третьем примере из предложенных Яндексом. Тем не менее, я все же загрузил полученное решение, и оно прошло целых шесть тестов.
После этого я вернулся на задачу №1. Пришла в голову мысль сделать другой алгоритм, более простой, но увы, не успел. Голова уже не соображала, я опять переусложнил себе задачу, и в итоге новый вариант так и не дописал. А минуты за четыре до конца отведенного времени и вовсе бросил все попытки что-либо сделать. Хотя сейчас, успокоившись, понял, что алгоритм был бы довольно простым. И будь у меня в запасе не 20 минут, а еще час, задача была бы решена.
В общем, самая главная сложность в конкурсах Яндекса — это страх перед ограниченностью времени. Из-за этого я паникую и действую неэффективно. А еще непонятно, как там считаются баллы: только по числу пройденных тестов или за решение задачи полностью тоже что-то дается дополнительно? Если первое, то у меня еще остаются хоть какие-то шансы прорваться в финал.
А еще сегодня попытался искать халяву в другом направлении: поучаствовал в акции Яндекса по розыгрышу призов за три произведенные оплаты через Яндекс.Деньги — продлил домены, срок которых начал подходить к концу. Причем, по-моему, мне регистратор еще тариф понизил…
И только сегодня режим начал начала налаживаться: пронулся бодрым, довольным и работоспособным. Воспользовавшись этим, решил принять участие в конкурсе по программированию от Яндекса, напоминание о котором пришло еще в пятницу. Но перед этим немного подготовился: сначала посидел в медитации, чтобы достичь максимальной сосредоточенности, потом — сделал небольшую зарядку, чтобы разогнать кровь, потом — пообедал, чтобы потом не отвлекаться, так как на выполнение заданий дается пять часов. И только после этого пошел на сайт конкурса.
Наученный опытом предыдущих конкурсов, прочитал условия всех задач сразу. Достаточно быстро понял, что две — легкие, одна — под вопросом, и одна — относительно сложная. Поразмыслив еще немного и поискав информацию по третьей задаче, решил приступить ко второй. Конкретно эту задачу стал решать на C (причем чистом, не C++), так как ограничение памяти в 64 Мб казалось довольно серьезным, и хотелось контролировать ее распределение явно. (Впрочем, потом стало ясно, что памяти там давалось с большим запасом, это я, прикидывая объем, перепутал порядки, поэтому и решил, что мало.) И где-то через час задача №2 была решена. Из предыдущего опыта я знал, что в Яндексе никак нельзя выводить отладочную информацию, поэтому загружая решение на сайт, очень опасался, а вдруг что-то пойдет не так. Но не так пошло только одно: я сначала неправильно указал язык программирования — Python вместо C. Но тут же это исправил, и с удивлением увидел, что задача решена правильно и полностью!
После этого взялся за задачу №1. Сначала казалось, что решить ее тоже достаточно просто. Но когда я написал код и отладил его на локальном компьютере, обнаружил, что придуманный мной алгоритм не справляется с ситуацией, когда в качестве максимумов оказываются несколько расположенных рядом одинаковых значеий. В этом случае он находит неоптимальное решение. В результате задача проходила только два первых теста. Я решил ее отложить, и переключился на задачу №3, благо к тому времени уже пришло понимание, как ее решать. Как водится, в самом начале, читая условие, я все усложнил (так как по опыту предыдущего конкурса ожидал более сложных задач). В реальности там все было достаточно просто, но в какой-то момент возникла заминка с выполнением поворота фигуры относительно центра координат. Очевидно, что это надо было делать через полярные координаты. Формул их я, конечно же, не помню, поэтому потратил какое-то время на поиск решения. А когда нашел, сделал небольшой тест, и несколько затупил, анализируя результаты. Потом оказалось, что я неправильно рисовал фигуру на бумаге, а программа как раз поворачивала все правильно. Но на осознание этого ушло минут десять.
Но вот наконец задача №3 была готова, когда до конца оставалось еще 2 часа времени. Я думал, что все под контролем, успею и попробовать решить четвертую, и доделать первую, но тут случилось непредвиденное. Моя программа для задачи №3 не прошла седьмой тест! Причем, в отличие от CodinGame, в Яндексе нельзя посмотреть тесты, и понять, с чем алгоритм не справляется. Остается только лишь гадать. Я подумал, что, возможно, нужно было сделать еще зеркальные отображения фигуры, срочно добавил их, потом предположил, что накапливается погрешность из-за чисел с плавающей точкой, и принял меры против этого, но все было безрезультатно. Так и осталось для меня загадкой, что же такого было в этом седьмом тесте…
Тем не менее, на все эти доделки я потерял еще минут двадцать. Но, самое главное, если до этого я только слегка нервничал из-за времени, теперь стал паниковать уже серьезно. Кроме того, домой пришел отец и стал меня отвлекать. Да и вообще, нервы были на пределе, и любой шум очень раздражал. Пришлось даже окно закрыть. После этого я взялся за задачу №4, на оптимизацию. Перечитав ее условие еще раз, понял, что она тоже проще, чем я подумал изначально, так как сначала не обратил внимание на одно существенное уточнение. Потом сделал так: сначала применил «жадный» алгоритм, который искал минимум для каждого оставшегося свободным варианта. Прогнал тесты, но они были составлены хитро: жадные алгоритмы на них сразу же проваливались. Но я был к этому готов, и сразу же дописал вторую часть, которая искала худший вариант и делала перестановку с кем-либо из других кандидатов, если это приводило к улучшению результата у одного и не сильно ухудшало результат другого. Увы, это привело к тому, что алгоритм стал зацикливаться. С этим я провозился до момента, когда до конца оставалось чуть больше 20 минут. К этому врмени уже плохо соображала голова, и я путался в куче сущностей, даже навводил кучу вспомогательных переменых, чего обычно не делаю. И то до конца не решил, а скорее сделал решение из категории «костыль». Увы, то, что получилось, не работало корректно даже на третьем примере из предложенных Яндексом. Тем не менее, я все же загрузил полученное решение, и оно прошло целых шесть тестов.
После этого я вернулся на задачу №1. Пришла в голову мысль сделать другой алгоритм, более простой, но увы, не успел. Голова уже не соображала, я опять переусложнил себе задачу, и в итоге новый вариант так и не дописал. А минуты за четыре до конца отведенного времени и вовсе бросил все попытки что-либо сделать. Хотя сейчас, успокоившись, понял, что алгоритм был бы довольно простым. И будь у меня в запасе не 20 минут, а еще час, задача была бы решена.
В общем, самая главная сложность в конкурсах Яндекса — это страх перед ограниченностью времени. Из-за этого я паникую и действую неэффективно. А еще непонятно, как там считаются баллы: только по числу пройденных тестов или за решение задачи полностью тоже что-то дается дополнительно? Если первое, то у меня еще остаются хоть какие-то шансы прорваться в финал.
А еще сегодня попытался искать халяву в другом направлении: поучаствовал в акции Яндекса по розыгрышу призов за три произведенные оплаты через Яндекс.Деньги — продлил домены, срок которых начал подходить к концу. Причем, по-моему, мне регистратор еще тариф понизил…