Лог жизни

Продолжаю участвовать в конкурсе на CodinGame. Вчера открылась серебряная лига, куда я сразу же прошёл. А вот дальше откатился на 1200-1300 места и ничего не мог с этим поделать. Два дня ломал голову, что же улучшить в алгоритме, почему такие плохие результаты. Потом стал сравнивать свои действия и действия противника на первых ходах (у меня до 6-ого хода последовательность действий закодирована жёстко) и обнаружил, что даже когда я пытаюсь дублировать действия противника один в один, это не получается. Стал разбираться и обнаружил глупейшую ошибку. У меня проверка возможности совершить то или иное действие была сделана криво: количество sun points (очков действий) проверялось на строго больше, а не больше или равно. Как только это исправил, сразу же подпрыгнул до 860 места.
А вообще, недавно подумалось, что CodinGame — это один из немногих сохранившихся кусочков старого Интернета. Во-первых, все общаются под Сетевыми именами. А у многих ещё на автарах персонажи старых компьютерных игр (видел даже Rockmanа у кого-то). Во-вторых, техноэлитизм: положение в иерархии на сайте определяется через интеллектуальные показатели: знание алгоритмов, умение писать код и находить решение, а технически безграмотным там делать нечего. Ну и в-третьих, практически сведена к минимуму коммерческая составляющая, что спасает сообщество от деградации.

В четверг днём успел сделать ещё один небольшой шаг в плане поддержки IndieWeb — написал код для endpoint discovery.
А потом начался конкурс на CodinGame! Задача про засев леса меня очень порадовала! Как и ожидалось, в бронзовую лигу я поднялся в тот же вечер, буквально с двух commitов (точнее, на CodinGame правильнее называть их submitами), написав совершенно простенький алгоритм. А вот дальше немного замедлился. Попытался было написать алгоритм, играющий перебором, но при большой глубине поиска нарывался на таймаут, а при маленькой — оказался на 1700-ых местах из 4000.
Сегодня решил попробовать другой подход. Написал код с набором стратегий, где выбор между ними осуществляется по набору фиксированных правил. Сразу результат улучшился: сначала 1200-ое место, потом, после пары мелких правок, поднялся до 1000 позиции. Но всё равно код не самым оптимальным образом играет в самом начале, и продолжаю думать, что с этим делать. Но бота бронзовой лиги вроде обыгрывает без проблем, так что, скорее всего, в серебряную лигу тоже без проблем поднимусь.

Еще месяц назад узнал об очередных соревнованиях от Яндекса, и долгое время не мог определиться, участвовать или нет. У меня эти соревнования связаны со стрессом из-за очень жесткого ограничения по времени и того, что очень мало тестов, из-за чего сложно понять, что же я сделал не так. К тому же эта неделя получилась какой-то непонятной: вроде и дел особо важных не было, но время улетало неизвестно куда. И только сегодня, в последний день, все же выделил 4 часа на то, чтобы принять участие. И на этот решил, что нужно пытаться полностью дожать «одну» задачу, а не пытаться написать код для всех, а потом на всех же застрять на дальних тестах.
С самого начала все пошло не так. Во-первых, я перепутал и вместо участие в backend-конкурсе указал frontend. Впрочем, как выяснилось, задачи там все равно алгоритмические, с frontendом связанные скорее способом оформления результатов и тем, что пишутся на JavaScript. Взялся за решение самой первой задачи. Там сразу же давался готовый код, но утверждалось, что он не работает на больших объемах данных. Я стал думать, как его оптимизировать. В процессе узнал про TypedArrays, и решил применить Uint32Array. Но увы, не знаю, было ли это решение правильным. Оказалось, что Uint32Array не поддерживает операцию push, поэтому пришлось идти кривым путем — создавать второй массив, куда добавлялись элементы, порождаемые в процессе решения задачи, и в конце итерации склеивать из двух массивов один, а потом сортировать его. Это ощутимо усложнило алгоритм, и пришлось дольше возиться с отладкой. Но самое обидное — так и не помогло: пять последних тестов уходили за таймаут. А еще несколько — заканчивались wrong answer. И в итоге за эту задачу я получил всего три балла из 15 возможных.
Не будь таких жестких ограничений по времени, я пошел бы другим путем: оставил бы массив обычным, отсортировал бы его один раз, а дальше просто вставлял бы новые элементы в нужные позиции, находя их бинарным поиском. Если будет возможность потом порешать задачи в тестовом режиме, то все же попробую это сделать.
После этого я переключился на другую задачу. Там все было проще: нужно было сформировать barcode по определенным правилам и вывести его в броузер. Ошибиться там было просто негде, поэтому с первой же отправки кода я получил за нее 40 баллов.
Прочитав остальные задачи, я решил взяться за самую последнюю. Там нужно было разобраться с куском кода, который отрисовывал аналоговые часы с кнопкой сброса, и доделать его. В целом это получилось довольно быстро, но в коде было ограничение: стрелки часов при сбросе должны повернуться к нулю, двигаясь не быстрее определенной скорости. И вот тут я запутался с единицами измерения. На то, чтобы разобраться, ушло много времени, но где-то за 10 минут до окончания все же при выполнении в броузере код работал как надо. Но когда я отправил его на тестирование, тесты он не прошел. А самое главное, я вообще в упор не понимал, как они устроены (оказывается, там были положения стрелок на часах в градусах). И только через пару минут после того, как время вышло, наконец-то до меня это дошло. И только сейчас, когда писал это сообщение, понял, как вообще надо было тестировать эту задачу. В общем, получилось, что застрял всего в одном шаге от окончательного решения, и вместо 113 баллов получил всего 43. Впрочем, даже этого хватило, чтобы подняться до 65 места из 310.
Весь остаток дня пытался прийти в себя и злился на то, что так получилось. До сих пор слегка болит голова… А самое обидное то, что из-за «таймерного стресса» возникает положительная обратная связь: из-за него я задание понимаю со второго-третьего раза в лучшем случае, упускаю иногда важные детали, из-за чего напрасно тратится еще больше времени.

Вот и все, конкурс Code a la Mode на CodinGame закончился. Мне удалось совершить качественный скачок! Впервые поднялся в золотую лигу и существенно улучшил результат как в абсолютных, так и в относительных показателях. Итог — 326 место из 1548. Кроме этого, впервые применил алгоритм поиска вширь, а не вглубь, для построения пути. Почему-то раньше мне он казался намного более сложным, хотя потом оказалось, что реализуется он элементарно на основе банального списка, работающего в режиме очереди, без всяких рекурсий (видимо, сказались стереотипы, оставшиеся со времен изучения Pascal и C, где нужно было заниматься реализацией списков самостоятельно). Кроме этого, реализовал один относительно новый для себя подход, который прежде в этих конкурсах не использовал: построение своего рода «виртуальной программы».
Что любопытно, в этом конкурсе я участвовал как-то лениво. Самый первый «жесткий» алгоритм сделал только на третий день. Как это ни странно, его вполне хватило, чтобы подняться в «бронзу» до 24 места. Впрочем, если бы я его адаптировал для последнего типа заказов (TARTS), которые появились в бронзовой лиге, то вышел бы и в серебро.
А потом до четверга не было вообще никаких продвижений. В четверг более-менее серьезно засел за написание более «умного» кода, но только в субботу его закончил, и потом еще весь вечер ушел на отладку. Но сначала результат разочаровал: 42 место в бронзе, хуже, чем у «жесткого». После нескольких доработок удалось повысить позиции до первой десятки, но дальше — никак. Потом добавил одно упрощение: вместо анализа того, что есть на столах, код просто запоминал, куда он сбрасывал незаконченное блюдо, а потом забирал его обратно. И после этого произошел качественный скачок. Когда я сделал submit кода, он еще на 50% игр вышел на первое место (обычно это случается на последних 80-90%), я перешел в серебряную лигу и там тоже сразу оказался достаточно высоко: в районе 40-ой позиции (точно не помню). После некоторых мелких доработок удалось подняться на второе место, но вот бота серебряной лиги победить не получалось. Тут возник сложный выбор: либо довести до ума ту часть кода, которая анализирует столы с блюдами, либо сначала поэкспериментировать с алгоримтмом выбора заказов. Я выбрал второе и после небольших доделок все же прорвался в золотую лигу!
Но вот там алгоритм быстро уперся в предел своих возможностей: примерно 200-ая позиция. Я стал пытаться сделать некоторые мелкие усовершенствования, но эффект был незначителен, так как не понимал, за счет чего другие игроки проявляют себя лучше, что нужно добавить в алгоритм. Потом выявил один баг с расчетом дистанций, но и это помогло не сильно.
Было еще несколько идей, что можно сделать: рекурсивный поиск лучшего пути при разном порядке сбора компонентов вместо «жадного» алгоритма, который хватал то, что было ближе всего в данный момент, довести до ума тот самый алгоритм анализа столов, а также исправить ситуацию, когда мой персонаж берет блюдо, а потом снова ставит его на стол, так как для второго компонента тоже нужны свободные руки, но голова уже не соображала от слова совсем, сказывалась и эмоциональная перегрузка от прорыва, и поздняя ночь, и просто усталость. Поэтому я так и не стал их реализовывать, а взял ту версию, которая показала лучшие результаты, добавил туда пару мелких правок и сделал финальный submit где-то в районе 3:30. И первый раз за все время участия в конкурсах не сидел до последнего, а лег спать как обычно.
Еще тогда же, вечером, пришла в голову мысль, какой вообще должна быть идеальная тактика: один персонаж работает только верхней линии, другой — только на нижней, а все передачи компонентов идут через центральный стол. В этом случае значительно сокращается время на пробег вверх/вниз. Но как реализовать такое в случае, если поведение второго игрока непредсказуемо, пока за пределами моих возможностей.
Тем не менее, конкурсом я очень доволен! Жаль только, что самые интересные идеи пришли в голову слишком поздно. В принципе, их можно было бы реализовать, когда появится multiplayer-версия, но, скорее всего, к тому времени опять снесет потоком жизни, и будет не до этого… Все-таки конкурс своей ограниченностью во времени создает гораздо большую мотивацию, чем просто решение задачи в режиме multiplayerа. Отличный пример того, о чем я писал некоторое время о планах и дефиците времени.

Опять участвую в конкурсе на CodinGame под названием Code a la Mode. На этот раз задача достаточно необычная: нужно не пытаться обыграть второго игрока, а вместе с ним показать более хороший результат, чем этот же игрок в паре с третьим. При этом вторым игроком управляет алгоритм, о котором ничего не известно, кроме возможности наблюдать уже выполненные его действия.
Конкурс длится 10 дней, причем первые полдня я частично пропустил, не вспомнив о нем своевременно. Потом дело шло весьма медленно: в пятницу я только-только разобрался с условиями, в субботу набросал пробный вариант простого, достаточно жестко закодированного алгоритма, но так и не решился его протестировать (как всегда, внутренне сопротивляюсь первому запуску и связанному с ним разочарованию). В воскресенье все же собрался. Как это ни странно, заработало достаточно быстро, из третьей «дубовой» лиги я вышел с первой попытки, из второй — после некоторых достаточно быстрых доделок. Вот с первой пришлось повозиться: добавились новые правила, которые существенно изменили ситуацию.
В итоге получилось как всегда: засиделся до 5 утра, но смог подняться только до 4 места. Решил лечь спать, а утром обнаружил, что все же прошел в бронзовую лигу. Наскоро добавил в алгоритм несколько «костылей» для обработки тех правил, которые добавились при переходе, и сумел подняться до 240 места. Теперь вот думаю, что лучше: попытаться доделать уже существующий алгоритм, заменив «костыли» на нормальную обработку одной ситуации, и посмотреть, что будет (по идее, этого окажется достаточно, чтобы прорваться в серебряную лигу), или садиться писать новый, более гибкий, который пришел мне в голову вчера вечером.
Кстати, впервые мне удалось подняться в бронзовую до открытия серебряной (если не считать одного двухэтапного конкурса).

Уфф, только что закончил восьмое задание КСИ. Оно было реально сложным, на использование старинных методов шифрования! Причем, в отличие от предыдущих заданий, самым сложным вопросом был первый. Что я только с ним не делал, даже программу для перебора пытался быстро набросать. Но так и не справился (отчасти из-за того, что пошел ложным путем в самом начале, предположив неправильный метод и потратив на это 20 минут). Так и ткнул наугад в один из ответов, который казался подходящим по косвенным признакам. Но из двух часов, отведенных на задание, на него потерял где-то больше часа. Поэтому остальные пункты пришлось доделывать в спешке и в состоянии жуткой нервозности, расшифровывая лишь самое начало сообщения. Поэтому во втором пункте тоже до конца не уверен, правильно ли я его решил, так как одна из шести расшифрованных букв не совпадала. И только на третий вопрос ответил уверенно, зная, что другие варианты не подходят от слова совсем.

Сегодня закончился конкурс A*Craft на CodinGame. В отличие от предыдущих, он длился всего два с половиной дня и был не на игры, а на оптимизацию: нужно было расставить стрелки на карте так, чтобы сделать суммарный путь роботов по ней максимальным. Я занял 150-ое место из 2456! (Правда, примерно последние 500 участников — те, кто зарегистрировался, но даже не попытался прислать хоть какой-то код, и поэтому получившие 0 очков.) Это гораздо лучший показатель, чем во всех предыдущих конкурсах. Если считать в относительных показателях, то до этого мне максимум удавалось подняться до 84%, а в этот раз — до 93%, что близко к моему верхнему порогу амбициозности!
И это несмотря на то, что толком на конкурс не настроился, и до воскресенья подходил к нему как-то лениво. Впрочем, задачи по оптимизации даются мне проще сами по себе. Кроме того, код был основан примерно на том же рекурсивном алгоритме, который я впервые пытался применить еще в Code of Ctulu. Написал я его достаточно быстро, но потом обнаружился какой-то совершенно непонятный баг, на борьбу с которым ушла половина воскресенья. А причина оказалась банальной: я дважды использовал одно и то же имя result в одной функции, но подразумевая при этом две совершенно разных переменных: одну для поиска максимума, вторую — для хранения значения, которое будет возвращено из функции. В результате вместо максимума возвращался последний результат.
Из-за этого я только вечером воскресенья обнаружил, что хотя алгоритм хорошо справляется с картами из узких длинных коридоров, но дает довольно посредственные результаты на картах с большими смежными областями. Для таких карт я задумал было еще один алгоритм с совершенно другим подходом, но так его и не реализовал. Во-первых, не хватало времени, чтобы тщательно его обдумать и вытащить из зоны неуверенности. Во-вторых, нашел один случай, когда первый алгоритм (который рекурсивный) давал неоптимальный результат. Сначала казалось, что ошибка простая и ее удастся устранить быстро. Но все оказалось не так: я провозился с ней до глубокой ночи. А потом выяснилось, что ошибка действительно примитивная: я забываю вызвать .copy() при рекурсивном вызове функции, в результате чего вместо копии карты для поиска на следующем шаге передается ее исходный вариант и результаты поиска пути в разных направлениях начинают влиять друг на друга. Странно, что на остальных картах это работало! Причем выяснилось, что если на каждом шаге создавать копию карты, это занимает много времени, и в итоге на многих тестах начинается вылет по таймауту. Пришлось применить «костыльное» решение: написать условие, по которому принимается решение, делать копию или нет.
Поэтому вместо второго алгоритма сделал простую проверку: если карта с большими смежными областями, и роботов много, то для последних строить путь только до ближайшей уже размещенной стрелки. И, как это ни странно, это дало определенный результат: вместо 5400 очков, которые я набирал изначально, стало получаться 5700! А вот исправление того бага с копией дало всего лишь жалких 17 очков (впрочем, их оказалось достаточно, чтобы подняться еще на несколько мест).
Но вообще, наверное, надо было писать не на Python, а на PHP. Там и код быстрее выполняется (если в PHP 7), и копии массивов создаются автоматически (так что я бы не возился полдня с первым багом и, может быть, успел бы и второй алгоритм реализовать), причем в режиме copy-on-write, что тоже дало бы неплохую оптимизацию. Но увы, нельзя применять в качестве ключей для хеша связки из нескольких значений (то, что в Python называется tuples). Впрочем, при желании это можно было бы легко обойти.
Но в любом случае, я доволен результатом!

Прошлое воскресенье и понедельник я провел в очень подавленном состоянии. На конкурсе CodinGame дела шли очень плохо: несмотря на все мои попытки усовершенствовать алгоритм, я скатывался все ниже и ниже в рейтинге, и никак не мог понять, почему это происходит. Вроде ошибок нет, алгоритм играет нормально, а я все равно раз за разом проигрываю. Еще и чата узнал, что есть люди, которые вообще написали полноценный симулятор этой игры у себя на компьютере и провели на нем моделирование множества игр, на основании чего для каждой карты определили коэффициент ее полезности. Стало ясно, что с моим простеньким алгоритмом выбора карт с такими тягаться не по силам.
Попробовал даже быстро написать новый вариант (уже пятый по счету), но и в нем результаты отличались не сильно. Во вторник я прекратил все эти попытки, а стал искать среди уже отправленных версий те, на которых мне еще удавалось подняться хотя бы до середины лиги. И в итоге нашел такую, которая позволила снова подпрыгнуть до 202 места. Среда и четверг ушли на испытание в этой версии некоторых идей, которые возникли в воскресенье и понедельник. Еще я пытался поиграться с функцией выбора карт на этапе начальной раздачи. Но все было безрезультатно: либо изменения были несущественны, либо наоборот, я начинал падать вниз. Кроме того, так и оставался вопрос с тем багом, про который я уже писал. Почему-то при его наличии результаты получались в разы лучше, чем при его отсутствии, хотя с точки зрения здравого смысла должно было быть все наоборот. Еще пытался изучить статистику и понять, на каких именно раскладах я проигрываю, но все что удалось — это сделать предположение, что проигрыши идут на раскладах, где guard-карт мало, а противник набирает много «тяжелых» карт.
Наконец, наступил последний день конкурса — пятница. Тут мне пришло в голову (опять же, под влиянием чата) применить метод Монте-Карло, то есть выбирать ход случайно, моделировать возможный ответ противника, исходя из соображения, что он будет бить только в guard-карты и моего игрока, и оценивать результат, выбирая в итоге тот, у которого оценка оказалась лучшей. На удивление быстро я переделал под него свой старый код, но увы, такой подход тоже оказался совершенно безрезультатным: я по-прежнему оказывался на дне серебряной лиги.
Вообще, если в предыдущих конкурсах было понятно, что делать, как играть, чтобы выиграть, но у меня не хватало знаний описать это математически и закодировать, то в этом — все наоборот. Я мог написать практически любую стратегию, но никак не мог понять, как вообще надо играть, чтобы выигрывать. В частности, как именно происходит захват стратегической инициативы, когда у одной из сторон на столе оказывает на три или более карт больше, после чего дальнеший ход игры, фактически, предрешен. А не понимая этого, я мог делать функцию оценки только вслепую из общих соображений типа «health points и показатели карт на столе моего игрока должны давать плюс, health points и карты противника — минус». И, судя по всему, главный недостаток моего алгоритма заключался в том, что слишком часто он решал выложить новую карту вместо того, чтобы бить в противника. И еще я не учел ассиметричности игры, того, что оказавшись вторым по очередности хода, нужно играть иначе, чем первым (хотя как именно «иначе» — не понимаю до сих пор). Из-за этого у меня было много результатов, когда я у одного и того же противника первым игроком выигрываю, вторым — проигрываю.
Еще непростой выбор был в конце между двумя версиями кода, одна из которых была хорошо протестирована, а другая — меньше, но вроде бы давала лучший результат. В итоге менее чем за минуту я все же выбрал вторую. И вроде бы не прогадал: 203 место в серебряной лиге, 590-ое в общем зачете. То есть с небольшой погрешностью повторил свои результаты предыдущих конкурсов.
В общем, что можно сказать в итоге: переписал код целых семь раз, получил массу опыта и интересных идей, попробовал делать то, о чем прежде имел весьма смутные представления, впервые стал целенаправленно применять функциональный подход и оценил его преимущества, да и вообще стал чувствовать себя в Python так же уверенно, как и в PHP. Но увы, в плане результатов я ожидал все же большего…

Сегодня принял участие в очередном конкурсе от CodinGame. На этот раз нужно было спрограммировать бота для карточной игры по мотивам Warcraft. Уже за одно это разработчикам огромнейший респект — порадовали! Но, в отличие от предыдущих конкурсов, поменялся формат. Теперь конкурс проводится не за десять дней, как раньше состоит из двух частей, считаемых независимыми конкурсами. Первая — спринт: нужно представить решение задачи всего за 4 часа. Вторая — марафон — на ту же самую задачу (но с открытием лиг выше бронзовой) отводится 4 недели.
Сегодня был спринт. Началось все достаточно хорошо: я за час с небольшим разобрался в условиях и написал код, позволивший мне влегкую проскочить третью дубовую лигу. Причем еще решил писать на PHP, а не на Python, в расчете на то, что на этом языке никто другой писать не будет, и у меня будут шансы получить бонус за финиш первым по языку.
Но на второй правила игры немного поменялись, и бот стал играть неэффективно. Я стал обрабатывать эту ситуацию, усложнил код и в процессе переделки, как водится, насажал в нем ошибок. Поэтому следующие часа два ушли на отладку. Но даже когда удалось все отладить, оказалось, что бот все равно не может выйти в первую дубовую лигу. К тому же еще проблема была в том, что организаторы конкурса не учли, что из-за новых правил все ломанутся играть в первые четыре часа, и серверных мощностей будет просто не хватать. Расчеты боев велись с просто огромной задержкой, которая не давала толком ничего отлаживать…
Я попытался было изменить обработку одного из игровых моментов (выкладывание карт в начале игры: в первом варианте клалась первая доступна по мане карта, во втором стал искать оптимальный вариант по другим признакам и копить ману для него). Но в итоге стало еще хуже. Зато в процессе обнаружил, что бывают карты с нулевыми затратами маны, и их желательно играть сразу же. В результате откатил бота до прежней версии, добавил в него обработчик нулевых карт и отправил код за две минуты до окончания конкурса. Вскоре после этого посчитались первые результаты. Я увидел себя на 485 месте из 743, решил, что выступил ужасно, расстроился и переключился на другие дела.
Но каково же было мое удивление, когда сейчас, снова заглянув в CodinGame, обнаружил сначала сообщение о проходе в первую дубовую лигу, а потом и в бронзовую. И сейчас мой результат показывается то как 348, то как 374. Судя по всему, для кода, отправленного в самом конце соревнования, пересчеты идут до сих пор.
А мой расчет на PHP не оправдался: нашлось немало желающих писать на нем. Уж лучше бы Perl использовал: на нем всего 2 человека писало из всех семи сотен, а по трудоемкости примерно одинаково.

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