Plz add whitespace between nickname and bracket

Смотрю я доту и вижу на сцене подозрительно знакомое лицо, но никак не могу вспомнить, кто это... Слышу, что обращаются к нему "Якуб". Опа, да это ж наш родной Якуб meret Пачочки (-хоцки? -чоки?)! Вот это внезапненько.

https://www.youtube.com/watch?v=yK5SxX3Ujs0&feature=youtu.be&t=12m15s

https://openai.com/the-international/

Я написал маленький юзерскрипт для Codeforces, который сортирует комментарии по количеству плюсов/минусов. В результате дерево комментариев выглядит так же, как на развлекательных ресурсах вроде Reddit или Pikabu. Так что самые полезные комментарии шутки Bredor всегда будут собраны сверху.

Добавить юзерскрипт можно с помощью Greasemonkey в Firefox, с помощью Tampermonkey в Chrome. В других браузерах не тестил, но наверно в любой с помощью чего-нибудь добавить можно.

Вот он: Codeforces comment sorter.

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

http://screeps.com/

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

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

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

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

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

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

Всем привет.

31 марта в стенах Самарского государственного аэрокосмического университета прошла VI Межвузовская олимпиада по программированию. Мы приглашаем вас принять участие в тренировке по задачам этой олимпиады.

Авторы задач — команда Samara SAU Teddy Bears. Тестировал комплект ashmelev, за что ему еще раз спасибо.

Сложность такая же, как в предыдущих наших контестах — три звезды. Продолжительность — 5 часов.

Начало — в эту субботу (27 апреля) в 14:00 (MSK).

UPD. Видеоразбор.

Расскажу о своем участии в 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. Год ждать не придется. Песочница продолжит функционировать через некоторое время.

197A - Игра с тарелками

Если первый игрок своим ходом не может поставить тарелку на стол (стол слишком маленький, и тарелка не помещается, т.е. 2r > min(a, b)), выигрывает второй игрок.

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

197B - Предел

Решение задачи — разбор случаев.

Легко понять, что важны лишь степени многочленов и их коэффициенты при старшем члене, остальные числа в инпуте — для отвода глаз.

1. Если степень знаменателя больше, ответ равен "0/1".
2. Если степень числителя больше, ответ — бесконечность. Чтобы понять, какая именно, надо посмотреть на знаки при старших коэффициентах. Если знаки одинаковые, то положительная, иначе — отрицательная.
3. Если степени числителя и знаменателя равны, ответ, как известно из курса математики, равен . Чтобы дробь была несократимой, надо a₀ и b₀ поделить на их gcd. Также надо быть внимательным, если один или оба из этих чисел отрицательные и не вывести "1/-2" вместо "-1/2".

196A - Лексикографически максимальная подпоследовательность

Очевидно, что сначала нам надо выписать все буквы 'z', если они есть — ответ от этого хуже точно не станет. Теперь множество доступных букв сократилось — мы не можем использовать те буквы, что находятся левее последней буквы 'z'. Поэтому выпишем все буквы 'y', что встречаются правее последней буквы 'z'. Множество доступных букв еще сократится, теперь это будут буквы, находящиеся правее самой правой из букв 'z' и 'y'. Продолжаем так, пока не выпишем все подходящие буквы.

196B - Бесконечный лабиринт

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

Осталось проверить наличие таких клеток. Запустим поиск в глубину по бесконечному лабиринту из стартовой точки. Пусть он при посещении точки (x, y) сохраняет в visit[x%n][y%m] значение (x, y). Теперь если поиск пытается прийти в клетку (x, y) такую, что в visit[x%n][y%m] уже что-то есть, причем оно не равно (x, y), значит две требуемые клетки найдены — клетка (x, y) и та, что сохранена в visit[x%n][y%m]. Отметим, что этот поиск посетит не более nm + 1 клеток (принцип Дирихле). Асимптотика решения — O(nm).

196C - Нарисуйте дерево

Т.к. никакие три точки не лежат на одной прямой, решение всегда существует.

Сначала подвесим дерево за какую-нибудь вершину и dfs-ом посчитаем размеры всех поддеревьев. Теперь будем рекурсивно строить ответ. Найдем самую левую нижнюю точку и поставим ей в соответствие корень дерева. Ничего плохого от этого не случится, ведь эта точка — крайняя в множестве. Отсортируем все остальные точки по углу относительно этой самой левой нижней точки. Теперь пусть размеры поддеревьев корня равны s₁, s₂, ..., s_k. Запустим алгоритм рекурсивно, передав первому поддереву корня первые s₁ точек (в уже отсортированном порядке), второму поддереву — следующие s₂ точек после первых s₁, ..., последнему поддереву — последние s_k точек. Легко видеть, что ребра, принадлежащие разным поддеревьям, в этом случае не будут пересекаться. На каждом этапе рекурсии надо сопоставлять самую крайнюю из выбранных точек с корнем поддерева и сортировать все остальные точки относительно нее. Тогда никакие два поддерева не будут иметь попарно пересекающихся ребер. Асимптотика решения — .

196D - Следующая хорошая строка

Сразу заметим, что нас интересует только наличие подпалиндромов длины d и d + 1: любой подпалиндром большей длины будет содержать их, а если нет длины d и d + 1, нет и больших. Назовем их, для краткости, плохими.

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

Увеличим s[pos]. Продолжим увеличивать, пока s[pos] является концом плохого палиндрома. Если пытаемся увеличить символ 'z', значит надо переходить к увеличению предыдущего символа. Если таким образом дошли до начала строки и увеличивать некуда, решения нет. Заметим, что при этом будет выполнено не более O(n) операций увеличения.

Пусть теперь pos — позиция самого левого измененного символа. Мы знаем, что префикс s[0..pos] не содержит плохих палиндромов. Теперь суффикс s[pos + 1..n - 1] можно заполнить жадно, перебираем позицию i по возрастанию, полагаем s[i] = 'a', и увеличиваем s[i], пока он является концом плохого палиндрома. Несложно понять, что на роль любого символа суффикса подойдет один из символов 'a', 'b' или 'c' — так как каждой позиции могут "помешать" лишь два символа находящихся левее на d и d - 1 позиций.

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

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

Итак, пусть дерево Фенвика поддерживает величины h[i] = s[i]Pⁱ, где P — простое число, используемое для хеширования. Тогда хеш подстроки s[L..R] равен (h[L] + h[L + 1] + ...h[R])P^- L. (Разумеется, можно не домножать на P^- L а просто при сравнении хешей домножать один из них на нужную степень) Если требуется изменить s[i] на c, прибавляем Фенвиком в i-ую позицию число (c - s[i])Pⁱ.

Существует более быстрое решение, без хешей и структур данных, оно будет опубликовано немного позже.

196E - Открытие порталов

Сперва заметим, что если порталы расположены во всех вершинах графа, то ответ — сумма длин ребер в минимальном остовном дереве, которое можно найти алгоритмом Краскала. Это довольно очевидно.

Однако порталы расположены не во всех вершинах. Попробуем это исправить.

Сделаем небольшой предпросчет: запустим алгоритм Дейкстры одновременно из всех порталов. Таким образом можно посчитать 2 массива: d[i] — расстояние от вершины i до ближайшего портала, и p[i] — ближайший к вершине i портал.

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

Пусть такой кратчайший путь — из портала x в портал y. Заметим, что можно найти путь не длиннее, такой, что p[i] на нем будет меняться ровно один раз. Действительно, p[x] = x, p[y] = y, значит, на кратчайшем пути хотя бы раз меняется значение p[i]. Пусть оно меняется на ребре , причем p[i] = x. Поскольку путь от j до p[j] — кратчайший путь от j до портала, путь не длиннее пути из x в y.

Тогда, т.к. p[i] = x, p[j] = y, можно рассчитать длину этого пути: она равна d[i] + w(i, j) + d[j] (w(i, j) — вес ребра (i, j)). Алгоритм Краскала прибавит эту величину к ответу и объединит порталы x и y. При этом объединятся поддеревья ближайших к ним вершин.

А теперь видим, что ничего не изменилось, и следующее по весу ребро можно найти точно таким же способом — . Если это ребро снова лежит между вершинами x и y, то DSU не даст посчитать это ребро, иначе это ребро соединяет другую пару порталов и войдет в ответ.

Как это считать. Из определения ребер в новом графе нетрудно понять, что их столько же, сколько и в исходном: каждому ребру (i, j) веса w(i, j) в старом графе соответствует ребро (p[i], p[j]) веса d[i] + w(i, j) + d[j] в новом графе. Поэтому построим новый граф и запустим на нем алгоритм Краскала — он посчитает вес минимального остовного дерева в графе, где вершины — порталы.

Осталось заметить, что если в стартовой вершине есть портал, то мы нашли ответ, а если нет — то надо сначала дойти до ближайшего портала, чтобы можно было начать считать миностов. Для этого можно просто в конце прибавить к ответу число d[1].

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

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

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

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

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

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

http://mirror.codeforces.com/ratings/countries

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

Приглашаю всех желающих принять участие в моем первом контесте. Он будет проведен сегодня в 19:00(мск) на базе Codeforces тренировок.

Этот контест - часть эпической серии "Тренировки Самарского Международного Аэрокосмического Лицея", с которой некоторые из вас уже успели познакомиться. Проведен он был 12 ноября прошлого года.
Если dalex выложил свои два контеста просто в режиме тренировки, я хочу испытать на своем контесте возможности Codeforces тренировок для проведения соревнований.

Контест довольно легкий, наиболее интересен он будет, пожалуй, участникам второго дивизиона. Но если к нам заглянут красно-желтые участники и решат все пять задач за полчаса, я буду только очень рад =)

P.S. В для ввода/вывода будут использоваться файлы input.txt и output.txt - если вы получаете вердикт "решение зависло на первом тесте", значит вы забыли об этом.
Условия будут доступны в виде pdf файла.
Регистрация уже открыта.

UPD: Меня тут спросили, по каким правилам будет проводиться контест. Напоминаю: пока что тренировки поддерживают только ACM контесты.

UPD2: Если вдруг кто-то опоздал к началу, но хочет поучаствовать - знайте, что регистрация НЕ закрывается с началом тренировки.

UPD3: Тренировка была отложена на полчаса. Начало в 19:30.

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

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

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

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

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

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

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