Hohol's blog

By Hohol, history, 13 months ago, In English,

Plz add whitespace between nickname and bracket

Read more »

 
 
 
 
  • Vote: I like it
  • +67
  • Vote: I do not like it

By Hohol, history, 2 years ago, translation, In English,
 
 
 
 
  • Vote: I like it
  • +178
  • Vote: I do not like it

By Hohol, 5 years ago, translation, In English,

I have created a small userscript for Codeforces, which sorts comments by comment rating. As a result, the comment tree is sorted just like in Reddit. So the most useful comments funniest jokes will always be at the top.

You can add it to Firefox with Greasemonkey, or to Chrome with Tampermonkey. Or to any browser with corresponding addon — I hope any modern browser supports userscripts in some way.

Here it is: Codeforces comment sorter.

Read more »

 
 
 
 
  • Vote: I like it
  • +48
  • Vote: I do not like it

By Hohol, 5 years ago, In Russian,

Лень пересказывать, просто кидаю ссылку на официальный сайт:

http://screeps.com/

И на кампанию проекта на indiegogo:

https://www.indiegogo.com/projects/screeps

Я поигрался немного в доступную сейчас часть игры, мне она показалась добротной и симпатичной. Особенно понравилась система конструирования юнитов из запчастей — возможности открываются просто огромные. Печалит, что единственный доступный на данный момент язык разработки — JavaScript.

Думаю, даже реализовать такое в режиме похожем на классические RTS (pvp, относительно короткий матч, развитие с нуля в каждом матче) — было бы офигенно. Но создатели обещают что-то еще более крутое — MMO игру. Очень интересно, как именно это будет выглядеть, пока подробностей на этот счет мне показалось маловато.

В общем, выглядит проект многообещающе. Хотя и есть серьезные опасения, что система монетизации в итоге окажется Pay to Win. Надеюсь, создатели все же придумают что-нибудь получше (хотя, возможно, я просто неправильно понимаю, что именно будут означать их CPU credits).

Сознаюсь, продонатил кампанию на indiegogo на 13 драгоценных долларов, чтобы показать свою заинтересованность. Очень уж хочется, чтобы проект был успешен.

Read more »

 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

By Hohol, 6 years ago, translation, In English,

Hello everyone.

We invite you to take part in the training on problems of VI Samara Regional Intercollegiate Programming Contest. It was held March 31 in Samara State Aerospace University.

Problem writers are members of team Samara SAU Teddy Bears. Problem tester is ashmelev.

Difficulty is the same as in our previous contests: 3 stars. Duration — 5 hours.

Contest starts this Saturday (April 27) at 02:00 PM (MSK).

Read more »

 
 
 
 
  • Vote: I like it
  • +76
  • Vote: I do not like it

By Hohol, 7 years ago, In Russian,

Расскажу о своем участии в Russian AI Cup.

Когда мы прочитали объявление о начале конкурса, первая реакция была: "Опять саратовские танки! Сколько можно-то?".

Кто не в курсе — объясняю. Организаторы Russian AI Cup — Одноклассники и Саратовский Государственный Университет. На четвертьфинале ACM ICPC в Саратове каждый год проходит неофициальный игровой конкурс Code Game Challenge. Суть все та же — напишите бота, который всех порвет. И хотя боты оказываются то волшебниками в шляпе и с посохом, то гоночными автомобилями, то суднами на воздушной подушке — мы всегда звали их танчиками.

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

Но познакомившись с правилами поближе, решил, что все-таки конкурс мне все же интересен. Привлекали следующие пункты:

  1. Большая чем обычно была в CGC сложность игрового мира. Гусеницы танка управляются по-отдельности. Башня движется отдельно от корпуса. Объекты мира прямоугольные, а не круглые. И самое крутое — управление несколькими танками сразу. Все это обещало значительную глубину игры, разнообразие тактик, возможность сделать что-то нереально классное.
  2. Продолжительность — месяц. За это время стратегии должны очень сильно развиться. Даже если не участвовать, наблюдать за прогрессом участников будет очень интересно.
  3. Ясно, что участников будет очень много. Спортивный интерес очень велик.
  4. Приятные призы)

Начав подробнее разбираться с происходящим, заметил, что организаторы постарались сделать порог вхождения низким. Для просмотра боев на сервере не нужно вообще ничего кроме браузера. Языковой пакет после скачивания сразу просто работает (по крайней мере в моем случае — C#, Windows). Интерфейс сайта простой и понятный (мне чем-то напоминает Codeforces, что тоже приятно). Низкий порог вхождения положительно скажется на количестве участников. А чем больше участников, тем веселее.

Раунд 1

Напомню, конкурс начался в полночь. Я для ознакомления с системой отправил какой-то трешак, крутящийся на месте и пытающийся стрелять по врагам. Почему-то попадал он примерно в нуле случаев (оказывается, для определения, нужно ли стрелять, я использовал self.GetAngleTo, а нужно было self.GetTurretAngleTo). Впрочем, я убедился, что бот шевелится, не падает, и лег спать. За ночь мой рейтинг был слит в минус бесконечность.

На следующий день я заменил этот трешак на чуть допиленного квикстартгая. Он уже выбирал бонусы по соотношению полезность/расстояние и стрелял во врагов с упреждением, считая что они двигаются равномерно прямолинейно. Этого с моим слитым рейтингом хватало, чтобы выигрывать почти все системные бои. Но тут я столкнулся с проблемой, которая уже много обсуждалась: первые несколько сражений рейтинг изменяется сильно, а последующие — слабо. Соответственно, на трешовую стратегию пришлись все резкие скачки рейтинга, а далее, несмотря на победы, рейтинг рос очень-очень медленно.

Занялся движением. Научился подъезжать к бонусам задом, если так ближе. Это резко повысило выживаемость. Пытался улучшить траекторию, чтобы ездить не по ломаным, как квикстартгай, а по красивым кривым. Пробовал делать усилие на гусеницу пропорционально углу, пропорционально квадрату угла, пропорционально всяким функциям от угла и расстояния — ничего хорошего не получалось. Танк упорно водил хороводы вокруг бонусов, а подбирать стеснялся. Забил и оставил движение квикстатгайским.

К тому времени возникла проблема более важная, чем кривое движение. Появилась мода разъезжаться по углам и расстреливать тех кто в центре. Я долго не хотел вливаться в эту мейнстримовскую волну, бродил по центру и быстро умирал. В конце концов пришлось смириться и пойти на поводу у моды — в угол.

Следующая проблема — танк часто застревал, вписавшись носом в край карты. Пришлось проифать это — если мы уже много тиков стоим на месте, и при этом не находимся в теплом уютном углу, кажется мы застряли, давайте-ка отъедем к центру карты.

Заметил, что пушка моего танка слишком уж часто простаивает из-за того, что не успевает повернуться к врагу. Вот вроде почти повернулась, уже готова стрелять, но тут мы подобрали бонус, поворачиваемся к следующему, пушка отклоняется от врага, и стрелять опять некуда. Решил, что нужно помогать повороту пушки еще и гусеницами. Если скорости поворота пушки недостаточно для поворота к цели за оставшееся время перезаряда, повернемся к цели всем корпусом. Теперь пушка никогда не простаивала, количество очков, набираемых за партию, заметно возросло. Также это забавно исказило траекторию движения — теперь все повороты стали чуть более плавными, чтобы пушка всегда была нацелена на врага. Казалось, что танк стал лучше ездить, хотя вроде бы изменение относилось к совсем другой части стратегии.

Вроде бы описание почти всех фич на тот момент уместилось в пару абзацев, но этого уже было достаточно, чтобы подняться где-то до 10 места. Да, после слива рейтинг рос очень медленно, но верно. На несколько дней я уехал домой в деревню, где не было интернета, и про танки подзабыл. Когда вспомнил, решил заглянуть с телефона — посмотреть, насколько танк за эти дни слился, и как сейчас выглядит топ. Мой танк был на первом месте. Это кривое, ездящее как квикстартгай создание, каким-то чудом добралось до верхней строчки рейтинга. Тогда я понял, что назад пути нет. Если я побывал на первом месте, нужно выводить свои танки в финал.

Близился первый раунд.

Я решил вновь заняться улучшением движения. Слишком уж часто по квикстартгаевскому алгоритму ехал мимо спасительного бонуса. Вновь перебираю зависимости усилий на гусеницы от угла. Пропорционально углу — уже пробовал, чушь получается. Пропорционально квадрату угла — та же фигня. Что бы еще попробовать? Пропорционально кубу что ли? Ну ок, давайте. Внезапно выясняю, что это выглядит совсем неплохо. Издалека танк по довольно красивой линии устремляется к бонусу. Лишь если бонус близко, и танк повернут не к нему, плохо двигается. Ну что ж, если бонус близко, будем двигаться как умеем — как квикстартгай. Больше мимо бонусов не ездил.

Топы уже умели более или менее нормально уворачиваться. Я в этом плане безнадежно отставал. Место в песочнице понизилось. Попытался реализовать уворот, используя некие странные эвристики, но ничего хорошего не получалось. В результате пришлось все попытки откатить, и входить в первую половину раунда, отставая от топов на столетие в техническом плане.

К началу перерыва я был где-то на 25 месте. Это, конечно, проход в следующий раунд, но быть очевидно отсталым как-то неприятно. Было ясно, что для реализации нормального уклонения мне не хватало знаний о местной физике. Я знал, по какому закону происходило изменение скорости снарядов, но вот законов движения танка не знал. Значит, нужно их выяснить. Тут я воспользовался помощью I_love_natalia. Я ставил простые опыты — движение по прямой вперед, движение назад — и находил характеристики танка в каждый тик. И I_love_natalia по этим характеристикам выяснял законы движения. Я решил, что для начала мне вполне хватит уворотов с использованием полного газа назад/вперед. После выяснения этих законов я готов был к написанию простейшего уклонения.

Реализовал я его так: представлял, что мой танк движется прямолинейно равномерно, проверял, ударит ли в меня пуля в ближайшие 100 тиков, и если да, проверял, а ударит ли, если я прямо сейчас включу газ вперед/назад.

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

Эти меры позволили мне подняться уже до 8 места к концу первого раунда. Пришло время боев 2на2на2.

Раунд 2

Просматривая сражения из первого раунда, заметил несколько случаев, когда танк пытался уклоняться, но пуля несмотря на это его настигала. При этом никаких помех при уклонении не было. Ожидаемое поведение — либо уклониться, либо не пытаться уклоняться вообще. Очевидно, бага. Прогоняю бой в Repeater, дебажу. Выясняю, что ускорение танка при движении было сильно меньше предполагаемого. Но почему? В грязь он заехал чтоли, буксует? Отправляю лог движения танка I_love_natalia — так и так, проверь, не туплю ли я. Подтверждает, что ускорение тут слишком маленькое. "А у тебя танк при этом случайно не подбит был? — Ну, хп экипажа на половине было, а какая разница? — А движение танка от хп экипажа как раз зависит. — Что??? Движение зависит от экипажа? Откуда ты вообще такое такое взял? — В правилах написано..."

Открываю правила, читаю:

"С уменьшением здоровья экипажа эффективность управления танком падает: он начинает медленнее двигаться, поворачивать башню, увеличивается также время перезарядки орудия."

Почему-то, перечитывая правила несколько раз, я ни разу не заметил этой фразы. И в боях ни разу не обратил внимания, что подбитые танки приторможенные какие-то. RTFM, товарищи.

И все-таки, что за фигня? Экипаж педали крутит, чтобы гусеницы двигались? Башню руками поворачивает? Снаряды вручную перезаряжает? 21 век на дворе вроде бы. Хорошо хоть снаряды руками не бросают, а то падали бы прямо под свои гусеницы при низком хп.

В общем, выяснив зависимость мощности движка от хп экипажа, я исправил уклонение.

Пришло время еще раз улучшить движение. Заметил, что танк часто начинает странно покачивать носом при движении к бонусу, если этому движению предшествовал резкий поворот. Из-за этого сильно снижалась скорость движения. Это происходило вот почему: мы только что оказались лицом к бонусу и сейчас газуем вперед, но перед этим мы к нему поворачивались с большой угловой скоростью, и угловая скорость по инерции поворачивает нас от бонуса, причем довольно сильно. Тогда мы вновь с силой поворачиваемся к бонусу, на этот раз в обратную сторону, и все повторяется снова. Тогда я начал гасить угловую скорость, если сейчас направлен к бонусу. Колебания прекратились, скорость движения к бонусам повысилась.

Как ни размышлял, как ни экспериментировал, но я так и не понял, как оптимально располагать два танка. Если мы спавнимся сбоку, то вроде бы вдоль вертикальной стенки хорошо получается. Ну да в случае спавна сбоку вообще все хорошо получается, ибо поспавнившиеся с другой стороны противники убивают друг друга. А вот если выпал спавн между врагами, или хотя бы на вертикальной линии с врагом — не понимаю что делать. В конце концов стал неким образом забиваться двумя танками в угол, но ничего особо хорошего из этого не получилось.

То есть это сейчас я знаю, что ничего хорошего не получилось. А тогда я в песочнице был в первой пятерке, и думал что все в шоколаде. Подошел второй раунд, и по результатам первой его половины я был на 75 месте. В финал же проходило 50.

Итак, перерыв. Нужно срочно что-то улучшать.

Топы явно уворачивались лучше меня. Я умел уворачиваться только газуя назад или вперед. Этого было недостаточно. Но чтобы правильно уворачиваться с поворотом, нужно знать физику мира гораздо более подробно. Я приготовился к новому этапу реверс инжиниринга, который занял бы у меня кучу времени. Но тут Noob дал мне ссылку на обсуждение конкурса на gamedev.ru — многостраничную тему, начавшуюся одновременно с конкурсом. Люди там уже давно выяснили всю физику мира опытами либо декомпиляцией локал раннера. Понятно, что если эти данные были выложены в открытом доступе, многие уже, возможно, пользовались ими. И я, скрепя сердце, воспользовался этими готовыми данными для написания точного предсказателя движения.

Отныне, зная текущее состояние танка, и какие усилия будут приложены к гусеницам, я мог точно определить его состояние через несколько тиков. Теперь я перебирал не два возможных способа уворота от снаряда, а 121 — по 11 различных усилий на левую и правую гусеницу. Также было добавлено уклонение рикошетом — для этого просто нужно было определять, под каким углом пуля ударит в броню. Эффективность уворота резко возросла.

Надоело промазывать по хорошо уклоняющимся врагам. Часто было понятно: если выстрелить сейчас, враг легко увернется; однако через несколько тиков он оказывался в таком положении, из которого увернуться уже не сможет. Может, попробовать стрелять только если враг точно не может увернуться? Благо у нас есть идеальный предсказывальщик его положения при различных выбранных путях отступления. Реализовал это. Попадать стал лучше, был доволен. Но через некоторое время заметил, что почему-то стал бысрее умирать. Что за чушь? Я же улучшил стрельбу, почему это ухудшило мою выживаемость? Сравнив несколько боев до и после улучшения, понял в чем дело. Оказывается, спамя пулями, я часто сбивал летящие в меня пули, от которых я не мог увернуться. Это происходило с самых первых версий, я никогда не задумывался об этом и попросту не замечал, что такое происходит. А оказалось, что таким образом сбивается очень много опасных снарядов. Теперь, редко стреляя, я часто попадал под пули. Обескураженный, я выпилил фичу для обычных снарядов, оставив лишь для премиумных — уж для них она была совершенно уместной.

Научил танки не брать бонус, который нужнее тиммейту. До этого приоритет был всегда у имеющего TeammateIndex = 0, что, конечно, чушь.

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

И вот, подошло время второй половины раунда. Насколько помню, первые 8 часов тестирования я пошатывался где-то в районе 65 места, без каких-то видимых шансов на повышение. Я готов был уже распрощаться с конкурсом и продолжить жить нормальной жизнью, но головокружительная череда побед в последние часы подняла меня на 48 место.

Жаль, что не прошли в финал некоторые запомнившиеся мне сильные игроки: MrDindows, twrlx, ulitochka.

Финал

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

Возвращаемся к идее точной стрельбы. Я отказался от нее, так как с ней плохо сбивал опасные пули. Но что мешает мне проверить, является ли эта пуля опасной, и собью ли я ее выстрелом? Ничто не мешает, непонятно почему сразу в голову не пришло. Реализовал, стрелять стал намного лучше.

Теперь можно было полностью сосредоточиться на дуэлях. На данный момент каждый из трех моих танков считал себя частью команды из двух танков. Они странно блуждали в поисках бонусов и смешно копошились в углу, пытаясь разместиться там, не понимая, что их трое, а не двое. Пришлось таки создавать отдельную трехтанковую стратегию. Но чем будет заниматься эта стратегия? Вновь обратился к опыту текущих топов. Выяснил, что очень модной является тактика "занять стену и стоять у нее, уворачиваясь". Как бы скучно это ни выглядело, эта стратегия, видимо, была оптимальнейшей по отношению сложности реализации к эффективности.

Итак, решено — танки равномерно расставляем вдоль вертикальной стены. Поначалу я попробовал ориентировать их лицом к середине карты — возможно, получится эффективно уворачиваться рикошетом. Но получилось лишь эффективно ловить попадания в лоб. Пришлось располагать вертикально. Уже на этом этапе получилась версия, практически неотличимая от финальной невооруженным взглядом. Но на самом деле работы предстояло еще много.

Последний день перед финалом.

Стало понятно, что недавно улучшенная система стрельбы больше не работает. Стрелял я только когда был уверен в попадании. До того как я перешел к стратегии дальнего боя, такая стрельба работала хорошо. Но теперь враг почти всегда был далеко. Получается, в попадании я не был уверен почти никогда, и не стрелял почти никогда. В то же время враг, издалека спамящий выстрелами в меня, хоть иногда, но попадал. Пришлось пойти на компромисс — если враг близко, стрелять только если уверен в попадании, иначе спамить. Со стрельбой на этом закончил.

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

Было очевидно, что текущие топы опять уворачиваются лучше меня. В чем же проблема? Проанализировав бои, я выяснил это.

Расскажу чуть подробнее, как я уворачивался в это время. У меня имелся список из 121 возможных пар усилий. Была булева функция, определяющая, попадет ли в меня пуля, если я буду ближайшие 100 тиков применять данную пару усилий. Получается, что пуля, пролетающая от меня на расстоянии 1 пикселя, мне не угрожала. В результате почти все пули касались танка, но рикошетили. Только и слышно было всю партию характерное дзыньканье рикошета от моих танков.

Проблема была в том, что при любой случайности — стена помешала повернуться, тиммейт толкнул, танк сам выстрелил — движение танка немного отклонялось от рассчитанного, и вместо рикошета происходило четкое попадание.

Как же уворачивались топы? Рикошеты у них были редки. Они старались держаться от пули подальше, с запасом расстояния. Как мне добиться того же? Может, просто считать свой танк на 10 пикселей больше по всем направлениям? Да, в таком случае танк действительно старается быть от пули хотя бы на расстоянии 10. Но представим, что в нас летит пуля, и мы можем увернуться от нее, оставшись в лучшем случае на расстоянии 5 от нее. Танк, думающий что он на 10 пикселей больше, посчитает, что увернуться от нее шансов нет. И со спокойной душой позволит ей попасть в себя.

Я нашел следующий выход: прекратить считать опасность пули булевской величиной и считать ее вещественной. Пусть minDist — минимальное расстояние от танка, на котором побывает пуля. Тогда будем считать, что ее опасность равна max(0,20-minDist). Проблема решена. Теперь танк держится подальше от любой пули, пролетающей на расстоянии хотя бы 20 пикселей.

Тестовые бои показали, что новая система уворота действительно работает значительно лучше. Теперь я практически стабильно обыгрывал всех, кроме самых топов — Milanin, Mr.Smile, SDiL, Romka.

Два часа до начала первой половины финала. Раз за разом просматриваю бои, в которых я сливаю SDiL, в поисках вещей, которые можно быстро улучшить. Выясняю, что большинство попаданий по мне происходит, когда в меня летят несколько пуль. Танк уворачивается только от ближайшей, и ловит попадания последующих. Нужно писать уворот от нескольких снарядов одновременно. Успею за два часа? Написать успею. А потестить? Для этого надо отправить стратегию на сервак. А вдруг он после этого залагает (бывало уже перед началом раунда), версия окажется багнутой, и не успею переотправить? Рискнем.

Через некоторое время код готов. Тестирую в локал раннере. Багов не видно, работает ли то что нужно, непонятно — смартгаи не особо дружно стреляют. Отправляю на сервак, создаю бои с пятью топами, отлучаюсь на некоторое время от компа. Возвращаюсь, обновляю страничку, и дух перехватывает, когда вижу, что все пять боев выиграны. Создаю еще раз, обыгрываю всех кроме Mr.Smile. Смотрю бои — уворачивается отлично. Что ж, к началу финала танки готовы.

С началом тестирования сразу оказался на первом месте. Понаблюдав некоторое время, довольный лег спать. Утром обнаружил себя на втором, Mr.Smile на первом. Действительно, винрейт у него выше, и меня убивает стабильно. Кажется, тут уже ничего не сделать, постараемся удержать второе.

Начался перерыв, пора улучшать стратегию. Я опасался, что вслед за Mr.Smile многие начнут рашить стратегии дальнего боя. Это означало бы необходимость внесения серьезных изменений в случае высокой эффективности таких рашей. Но пока ничего подобного вроде не происходило. Решил подождать изменений в тактиках противников, чтобы было ясно, на что реагировать. А пока поискать явные недостатки в существующей стратегии.

Просмотрев несколько слитых боев, заметил в нескольких случаев очень странное верчение своих танков — не в ту сторону, в которую хотелось бы в данный момент. Repeater, debug. Захожу в несколько вложенных вызовов функций, и вижу в одной из них такой код:

if (toy > 0)
    TurnTo(self.X, self.Y+1);
else
    TurnTo(self.X, self.Y+1);

Хм, неплохо для стратегии, находящейся на втором месте. Разумеется, в else должно быть "-1". Исправляю.

Продолжаю просмотр слитых боев. Обнаруживаю бой, в котором в мой танк летят две пули, примерно параллельно, одна летит в нижнюю часть моего танка, другая в верхнюю. Ожидаемое поведение — танк немного поворачивается и позволяет пулям пролететь по разные стороны от себя. Но вместо этого он делает какое-то странное телодвижение, уклоняется от одной, и получает в корму вторую. Repeater, debug. Спустя некоторое время понимаю в чем дело. Я считал опасность от двух снарядов как сумму их опасностей по отдельности. Которая, напомню, равна max(0,20-minDist). Но тогда получается, что пара пуль с расстояниями (19,1) имеет ту же опасность, что и пара с расстояниями (10,10). Очевидно, первая пара все же куда опаснее. Значит, будем считать итоговую опасность как максимум отдельных опасностей, а не сумму.

Больше в тот день почти ничего не менял. Решил лечь спать пораньше, проснуться утром и проверить, не написали ли противники за ночь чего-нибудь контрящего меня.

Утром вижу сообщение Megabyte на gamedev.ru, в котором он говорит, что проифал меня, Mr.Smile и Romka — теперь он будет сразу рашить нас. Хм, интересно, проверим. Создаю пять боев с ним, и с отвисшей челюстью наблюдаю, как он выносит меня во всех боях. Его танки совершенно внаглую подходят вплотную к моим, и методично по-очереди расстреливают их. Проверил несколько других игроков — радикальных изменений вроде нет. Лишь у Romka я нашел кое-что интересное. Если начальное расположение танков таково, что один из игроков находится прямо над бункером, другой под бункером, Romka горизонтальной цепочкой едет в ту же сторону, что и я, занимает один из моих углов раньше меня, расстреливает танк, который едет в этот угол, после чего расправляется с остальными.

В общем, пришлось в срочном порядке допиливать тактику ближнего боя. Впрочем это допиливание свелось всего лишь к увеличению приоритета бонусов (особенно премиумных снарядов), когда мы находимся под атакой. Причем я считал, что я под атакой, если на моей половине поля есть хотя бы два вражеских танка. Megabyte я все еще сливал. Как мне показалось, из-за того, что слишком поздно реагировал на его раш. Пришлось добавить в функцию, определяющую, под атакой ли мы, следующий код:

if(enemies[0].PlayerName == "Megabyte")
    return true;

После такого хака скорость реагирования повысилась, и винрейт улучшился.

Вторая половина тестирования никаких сюрпризов не преподнесла. Была лишь интрига, кто же займет 6 место — Romka или Commandos. Все-таки Romka удержал место за собой.

На самом деле, немножко разочарован собственной стратегией в дуэлях. Скучновато бои выглядят.

Типичный бой с такой же как и моя дальнобойной стратегией:

Начало эпичной битвы


Обстановка накаляется


Нервы напряжены до предела


Победила дружба

То ли дело Mr.Smile — его раши в дуэлях просто прекрасны. Убийство практически любого оппонента быстрее чем за половину отведенного времени — это нечто.

Призы мне и Romka вручили прямо на церемонии награждения NEERC — за это организаторам отдельное спасибо, строчу последние строки этого повествования с новенького макбука эйр)

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

Все, пора заканчивать этот гигантский пост. Еще раз спасибо организаторам за прекрасный конкурс. Ждем продолжения через год.

upd. Год ждать не придется. Песочница продолжит функционировать через некоторое время.

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it

By Hohol, 7 years ago, translation, In English,

197A - Plate Game

If first player can't make first move (table is too small and plate doesn't fit it, i.e. 2r > min(a, b)), second player wins. Else first player wins. Winning strategy for first player: place first plate to the center of table. After that he symmetrically reflects moves of second player with respect to center of table. If second player has move, first player has symmetrical move, too. If not, first player won.

197B - Limit

From math lessons we know, that only higher degrees of polinomials matter in this problem.

  1. If denominator degree is larger than numenator degree, answer is "0/1".
  2. If numenator degree is larger, answer is infinity. But what is sign of this infinity? To get it consider signs of highest degree factors of polinomials. If they are same, answer is positive infinity, else — negative infinity.
  3. If degrees of numenator and denominator are equal, answer is . To get irreducible fraction, you should divide this numbers by gcd(a0, b0). And don't forget that denominator of answer must be positive.

196A - Lexicographically Maximum Subsequence

Solution is greedy. First, write all 'z' letters (if there is any) — answer must contain them all for sure. Now it's time for 'y' letters. We can use only those of them which are on the right of last used 'z' letter. Then write 'x' letters — they must be on the right of the last used 'y' and 'z' letters. And so on.

196B - Infinite Maze

Answer is "Yes" iff there are two distinct, reachable from start position cells, which correspond to same cell in initial labyrinth.

Proof: If these cells exist, move to first of them, and infinitely repeat moves leading from first to second. On the contrary, if infinite far path exist, on this path we obviously can find such cells.

How to find out if they exist? Start DFS from initial cell. For each cell visited, let visit[x%n][y%m] = (x, y). Now, if DFS tries to go to cell (x, y), visit[x%n][y%m] contains something, and (x, y) ≠ visit[x%n][y%m], we found these cells: they are (x, y) and visit[x%n][y%m]. Notice that DFS will visit no more than nm + 1 cells (Dirichlet's principle). So the asymptotic is O(nm).

196C - Paint Tree

No three points are in the same line, so the solution always exists.

First, choose any one vertex as the root of tree. Find size of each subtree using dfs.

Then, we can build the answer recursively.

Put the root of tree to the most lower left point.

Sort all other points by angle relative to this lower left point.

Let us name the sizes of subtrees of the root as s1, s2, ..., sk.

Run the algorithm recursively, giving first s1 points (in sorted order) for the first subtree of root, next s2 points for the second subtree and so on.

Obviously, no two edges from different subtrees can intersect now.

At each step of recursion we are to put the root of current subtree to the first point in sorted-by-angle order, and then sort other points by angle relative to it.

So, no two subtrees will have any intersecting edges.

The asymptotic of solution is .

196D - The Next Good String

Notice, that only palindromes with length d and d + 1 matter. Any palindrome with greater length contains one of them. Let's call these palindromes bad.

First, find leftmost position pos, in which we surely should increase value of symbol. If there are no bad subpalindromes, pos = |s| - 1, else pos is leftmost position amongst all ends of bad palindromes.

Increase s[pos]. Increase it more, while s[pos] is end of bad subpalindrome. If you try increase 'z' symbol, you should proceed to increasing previous symbol. If this way you reached situation when you need to increase first symbol, and it is 'z', answer is "Impossible".

Now, let pos be position of leftmost changed symbol. We know, that prefix s[0..pos] doesn't contain bad palindromes. Now we can greedily fill suffix s[pos + 1..length(s) - 1]: go over positions i in ascending order, assign s[i] = 'a', and increase it, while s[i] is end of bad palindrome. Obviously, any of suffix symbols will be 'a', 'b' or 'c'.

So we got algorithm, which requires fast implementation of next operations — assigning single symbol, and query: is given substring palindrome? You can perform this operations using hashes and Fenwick tree.

Let's learn, how to get hash of substring in dynamically changing string. If we can it, we will keep string s and it's reversed copy. For query of second type we just need to compare hashes of substring in s and hash of corresponding substring in reversed copy.

Let Fenwick tree store values h[i] = s[i]Pi, where P is the prime number used for hashing. Then hash of substring s[L..R] equals to (h[L] + h[L + 1] + ...h[R])P - L. For assigning s[i] = c, add value (c - s[i])Pi to h[i]. Both these operations Fenwick tree does in .

Also we have faster solution without hashes and data structures, it will be published soon.

196E - Opening Portals

First of all, we can note that if each graph vertex is portal, the answer will be a sum of all edges' weights in MST (minimal spanning tree). We can find MST by using Kruskal's algo.

In this problem, not an every vertex is portal. Let's fix this.

Start with a precalculation. Run Dijkstra's algo from all the portals, simultaneously. We will get d[i] — a distance between vertex i and p[i] — the nearest portal to vertex i.

Let's trace Kruskal's algo on a graph of portals. On the first iteration, it will choose the edge with the minimal cost, i.e. a shortest path between all the portals in the original graph.

Let the path leads from portal x to portal y. Note that there exists a path with the same length such as p[i] changes only once through it. Indeed, p[x] = x, p[y] = y, i.e. p[i] changed on the path. If it happens on edge , p[i] = x, a path will not be longer than the path from x to y.

As p[i] = x and p[i] = y, we can see that the length of this path will be d[i] + w(i, j) + d[j], where w(i, j) is the weight of edge (i, j). Kruskal's algo will add this value to the answer and merge portals x and y. The shortest-path trees of vertexes x and y will also be merged.

Note, that almost nothing changed. The next edge for Kruskal's algo can be find in a similar way — . If this edge connects x and y again, DSU makes us not to count this edge, otherwise this edge connects a different pair of edges and will be counted in an answer.

We can easily implement this. Just create a new graph of portals, with an edge (p[i], p[j]) of weight d[i] + w(i, j) + d[j] for every edge (i, j) of weight w(i, j) from original graph and run Kruskal's algo.

Finally, note that if the starting vertex is not a portal, we shall add d[1] to the answer.

Read more »

 
 
 
 
  • Vote: I like it
  • +59
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

Здравствуйте, извините за очередную оффтопную тему. Сегодня мне стало интересно, как много спортивных программистов были отчислены из универа, и если такие есть(кроме меня :D), то какие действия, на ваш взгляд, наиболее этому способствуют.

Read more »

 
 
 
 
  • Vote: I like it
  • +33
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

Нужен аналог std::set::lower_bound/upper_bound в C#. Например, для решения чего-нибудь такого: timus 1414

Погуглив, не нашел аналога, работающего за логарифм. SortedSet — ближайший родственник std::set — ничего подобного не умеет. Как будто бы остается только самому дерево писать.

Но на всякий случай спрошу еще здесь: кто-нибудь знает, можно ли это сделать?

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

Контест закончился, давайте пообсуждаем. Как решать C?

Read more »

 
 
 
 
  • Vote: I like it
  • +25
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

Наконец-то! Белоозёрск вырвался на второе место в рейтинге Codeforces среди стран!

http://codeforces.ru/ratings/countries

UPD: уже исправлено)

Read more »

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

By Hohol, 8 years ago, translation, In English,

Hi there. I invite you to participate in my first contest. It will take place in Codeforces::Gym at 19:30 (Moscow timezone — UTC+4).

Problems are rather easy, so it will be more interesting for div2 participants.

Warning: now statements are only in russian. But later we will translate all our trains in english, so everybody will be able to run them in virtual contest mode.

Read more »

 
 
 
 
  • Vote: I like it
  • +62
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

В числе последних изменений на КФ было введение постраничного показа в архиве задач, списке соревнований и в результатах соревнований. Меня это бесит. Раньше я легко и быстро находил интересующую задачу/соревнование/участника с помощью ctrl + F. Теперь это превратилось в непростую задачу. Приходится делать поиск по каждой странице по-отдельности, или узнавать ID соревнования, или добавлять участника в друзья с последующим удалением - в общем, не юзер-френдли.

Я хотел бы, чтобы вернули полные, длиннющие страницы - думаю, скорости интернета у всех на это хватит. Если же все-таки кому-то ее не хватает, или это создает слишком много трафика, можно оставить показ по умолчанию таким как сейчас, а переход на полную страницу сделать по дополнительной ссылке - это можно потерпеть.

А что думаете по этому поводу вы?

Read more »

 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

Сегодня писали школьный контест в кабинете Центра Олимпиадной Подготовки СГУ, и были приятно удивлены работой Visual Studio. Я давно привык, что студия жутко долго компилит проект, и считал, что это фича. А тут увидел, что она способна делать это за нулевое время.

Откройте секрет, как настроить ее, чтоб она так летала?

Еще, при выводе в файл при каждом запуске она обычно спрашивает, обновить ли output файл, так вот, в ЦОП она и от этого отучена, как сделать так же?

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By Hohol, 8 years ago, In Russian,

Прочитал отличный цикл статей  от Skiminok о дерамиде.

Хотелось бы применить полученные знания на практике.
Сам могу указать две задачи с тимуса: War Games 2 и Battle with You-Know-Who. Но в них используются лишь относительно простые операции, хотелось бы чего-нибудь повеселее.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it