Спортивное программирование *

Друзья, как вы уже знаете 14 апреля в Москве состоится Российский финал Imagine Cup 2012, в рамках которого будет выбрана студенческая команда, которая со своим проектом поедет представлять Россию на международном финале в Австралии.

Друзья! Мы провели региональные финалы конкурса Imagine Cup в 5 городах России, и отобрали 10 студенческих проектов из почти 80, которые будет соревноваться на российском финале! Подробности — ниже, но уже сейчас можно зарегистрироваться на мероприятие! Кроме выступлений проектов, там будет много интересного — мы действительно постарались приготовить для вас технологический праздник!

Сайт Brainbench.com, который занимается on-line сертификацией, с сегодняшнего дня запустил Bench Games, что для простых смертных означает возможность сдать на халяву любые тесты (а их там чего-то порядка 600). Да, это не распространяется на бумажные версии сертификатов, так что если захотите свою гениальность получить в персистентном виде, то дать им денег все равно придется.



Я прекрасно осознаю ограниченность любых формальных методов оценки специалистов, но, согласитесь, иногда померяться чем-нибудь очень даже интересно. Насколько я помню, в последний раз подобное мероприятие проводилось сайтом brainbench.com где-то лет 5 назад, после этого, они периодически делали часть своих экзаменов бесплатными (что тоже хорошо), но сейчас можно попробовать свои силы даже в том, что «не знал», «знал, да забыл», или «вообще что-это-за-хрень, но мне все равно интересно».

В общем, let the game begin.

З.Ы. Старовало это добро сегодня и длиться будет до 9-го марта.

UPDATE: я хз, как дать прямую ссылку на все тесты, похоже, чтобы по ней перейти нужно вначале залогиниться на brainbench-е. В общем, вот ссылка на все тесты. Если не получится зайти по ссылке, то логинимся, и потом сюда: Skills Center > Test Center > All Tests.

Соревнования по программированию становятся все более и более популярными; к внушительному списку разнообразных уже существующих турниров и чемпионатов недавно добавился еще один — VK Cup 2012. Вкратце его самые важные особенности:

• чемпионат проводится совместно компанией ВКонтакте и проектом Codeforces. Регистрация ВКонтакте для участия не требуется :-)
• ограничение на возраст участников — от 14 до 23 полных лет на момент регистрации (23 года и 11 месяцев — добро пожаловать). Таким образом, целевая аудитория — школьники старших классов и студенты.
• зато нет ограничений на страну проживания (условия доступны на русском и английском языках).
• довольно затейливая структура отборочных раундов, сконцентрированных в марте (первая квалификация — 4 марта) и начале апреля:
  
  • два квалификационных раунда, каждый из которых идет 24 часа и отбирает 800 лучших участников для раунда 1. Не пугайтесь длительности раундов — сидеть за компом сутки подряд не нужно, это означает только то, что сдавать задачи можно в любой момент этих 24 часов. Квалификации содержат несколько несложных задач, и обычно для прохождения в следующий раунд достаточно решить часть задач, штрафа за позднюю сдачу нет.
  • три отборочных раунда, проходящих по традиционным правилам Codeforces;
  • два wildcard-раунда, которые позволяют людям, выступившим в первом и втором отборочных раундах неудачно, попробовать еще раз. Для разнообразия wildcard'ы проводятся по другим правилам, чем основные раунды, и это довольно необычно для турниров по спортивному программированию.
• наконец, финал чемпионата для 50 лучших участников по результатам третьего раунда пройдет в июле в Санкт-Петербурге — поездка за счет организаторов.

Я продолжаю писать необычные раунды для Codeforces: позвольте представить вам Surprise Language Round #5, который состоится 22 февраля в 19:00 по московскому времени.

Это соревнование продолжает серию Unknown Language Round-ов, в котором участникам предлагается решать несложные задачи на единственном языке программирования, который становится известен за несколько минут до начала раунда. В этом и заключается прелесть таких раундов: можно сосредоточиться не на изобретении алгоритмов, как обычно, а на новом неслыханном языке. Во всяком случае, такова задумка авторов; мы не исключаем, что кто-то мог раньше видеть язык раунда или даже что-то на нем писать, но для большинства участников язык должен быть сюрпризом. Как видите, Brainfuck отпадает :-)

Прошлый раунд такого типа, который тоже проводила я, вынуждал людей с головой погрузиться в Befunge — достаточно известный эзотерический язык. Десять задач покрывали достаточно широкий диапазон сложности, начиная с «утешительной задачи» вычисления шестиугольных чисел (чисел вида N*(2*N-1)):

&:2*1-*.@

Уже не первый год мы проводим конкурс Imagine Cup. IC — это система международных соревнований для студентов технических специальностей. Ближайший прием заявок на участие в главном конкурсе программных проектов закрывается 15 февраля, и к нему накопилось уже очень много вопросов. В топике я постараюсь объяснить, зачем вообще нужны эти конкурсы для студентов, чем конкретно они помогают в жизни, что нужно сделать для победы и какие ошибки наиболее часто совершают участники.

Про конкурс в целом

Imagine Cup — это самое крупное соревнование в мире в области IT и программирования, которое проводится в этом году в десятый раз. Обычное количество участников — около 300 тысяч человек из 70 стран. В международный финал прошлого года в Нью-Йорке вышло три российских команды; в 2008 российская команда RedDevils взяла первое место в категории Project Hoshimi, в 2009 — Viva заняла второе место в Software Design, в 2010 — команде Robonyanya покорилось второе место в Embedded Development.

Итак, времени с момента запуска квеста прошло достаточно, выкладываю прохождение и кое-какие ответы на «критику». В целом, положительных отзывов значительно больше, чем отрицательных. После разгадывания последней загадки предлагалось сообщить мне о прохождении квеста. Это сделали около 10 человек. Сколько людей скачали файл – не знаю.

Здравствуй, Хабрадруг!

Мне понравилась идея создания квестов с помощью zip-архива, как это было сделано в этом посте. По указанной ссылке Мария (Nicolette) предложила квест, для прохождения которого требуется немного знать про эзотерические языки программирования. Я постарался сделать квест с таким же принципом, но в нём требуется немного уметь программировать и владеть некоторыми инструментами работы с файлами. Также пригодятся навыки нестандартного мышления и поиска информации в поисковиках. Обычно этими способностями вместе умеют пользоваться программисты, поэтому пост я решил положить в «спортивное программирование», так как больше никуда не подходит по смыслу.

Кому интересно потратить несколько часов на разгадывание моих загадок, прошу под кат.

Некоторые хабраюзеры уже участвовали в олимпиадах по программированию.
Например, в мае проходил ABBYY Cup. Сейчас на том же сервере проходит олимпиада факультета управления и прикладной математики МФТИ для школьников. Могут участвовать и студенты, но только вне конкурса, тем более, что сейчас сессия. Для студентов будут другие контесты.

Победители получат призы и сувениры от факультета и спонсоров. Турнир доступен до 15 января.

Турнир привлекал своей простотой и собрал широкую аудиторию. Идея пришлась по вкусу и старшеклассникам и умудренным опытом гуру, помнящим еще чемпионат мира по компьютерным шахматам 1972-го года.

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

После четырехмесячного перерыва Unknown Language Round возвращается на Codeforces: четвертый раунд этого типа состоится в воскресенье 20 ноября в 19:00 по московскому времени.

Соревнования этого формата предлагают участникам решить десяток задач за три часа времени. Все было бы довольно обычно, если бы не одно «но»: эти задачи можно решать только на одном языке программирования. Каком? О, это будет известно только в самом начале раунда. В том-то и прелесть формата, что выбирается язык, неизвестный большинству участников, и за отведенное время нужно не просто решить как можно больше задач, но еще и выучить заданный язык в объеме, достаточном для их реализации. Задачи подбираются простые и не требующие продвинутых алгоритмов, чтобы можно было сосредоточиться на новом языке.

На трех предыдущих раундах неизвестными языками оказались Tcl, Io и Pike; я участвовала только в первом, и, смею заверить, это было весело. В этот раз я раунд провожу и приглашаю всех в нем поучаствовать — особого опыта спортивного программирования для этого не нужно, а интересно будет (читатели моего блога здесь уже знают, какая я любительница языков позатейливее, а для такого случая грех было бы не подобрать что-нибудь особенное).

Для полноты картины приведу хабраанонс предыдущего раунда.

В этой заметке я расскажу как написать довольно неплохого бота для Google AI Challenge. Примечательно, что сложные технологии связанные с ИИ не понадобятся, а базовая реализация умещается в тысячу строчек кода на языке C++. Сами методы в совокупности могут быть рассмотрены как некоторый Generic алгоритм, и на базе них можно построить бота, учитывающего некоторые стратегические особенности, который возможно будет играть еще лучше. В любом случае — хороший «быстрый старт» для тех, у кого пока ничего не получилось.

Многие на Хабрахабр приняли участие в Google AI Challenge. Скачали инструменты для локального тестирования и уже ощутили прелесть и удобство их:

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

Сидел я так, сидел и в один прекрасный день задумался, а почему бы не сделать мини инструмент, который бы все это объединял в одном месте и забыть про консоль.

Краткое описание:
— один раз вводишь тесты — проверяешь на всех тестах с помощью одного клика;
— включает исходный код из библиотеки;
— создает юнит-тесты при архивировании задачи;
— специальная поддержка TopCoder (работает с plugin'ом moj) и Codeforces (парсит html странички и сохраняет sample-тесты).

Полное описание и ссылка для скачивания — тут.

На хабре уже имеется много информации по этому состязанию, однако вся она освещает отдельные моменты реализации, но не картину в целом. Постараюсь исправить это положение как можно более кратко, но в целом.
Данное описание предназначено для тех, кто что-то слышал о данном мероприятии, но всё желание что-то сделать отбила необходимость разбираться в тонкостях реализации. Пост состоит частично из перевода материалов с официального сайта, частично из анализа стратегий других ботов и чистой логики. Также в конце поста будет ссылочка на PHP-бота (чуть сложнее чем из starter-pack), который позволит вам попробовать собственные силы дописав имеющийся код. Официальный сайт состязания: aichallenge.org

Продолжаем разбираться в правилах проходящего сейчас турнира Google AI Challenge. Дальше вы можете прочитать перевод официальных правил расчета результатов муравьиных боев.

Фонд Викимедиа сообщает о начале конкурса по программированию October 2011 Coding Challenge. Авторы Википедии хотят найти программистов, которым близки ценности мира, в котором каждый человек обладает свободным доступом к любому знанию. Гран-при в каждой задаче — оплата расходов на какое-нибудь (по выбору победителя) событие фонда в 2012 году. Все успешные участники получат сертификат с отличием от фонда. На мой вкус — намного более осмысленное мероприятие, нежели гонять муравьёв.

Правила турнира

• Результаты турнира определяются с помощью ПО написанного организаторами. Опубликованные результаты являются окончательными. Текущий рейтинг игроков не является официальным и может отличаться от опубликованных окончательных результатов.
• Каждый участник турнира может иметь единственную учетную запись. При выявлении участника управляющего несколькими учетными записями, и несмотря на то, что эти учетные записи зарегистрированы на других людей, нарушитель будет дисквалифицирован.
• Участники (или их программы), которые нарушают дух правил и спорта (вероятно не нарушая официального текста правил), отстраняются от участия в турнире, без возможности обжалования. В частности: сканирование памяти, умышленный проигрыш и изменение поведения в зависимости от имени оппонента — запрещены.
• Производить запись в файлы запрещено. Разрешено производить чтение из файлов которые вы высылаете для участия. Файлы располагаются в текущей директории.
• Использование нескольких процессов или потоков запрещено.
• Любая попытка нарушить нормальную работу программного обеспечения турнира или серверов приведет к немедленному привлечению сотрудников правоохранительных органов. Наш принцип — всегда преследовать нарушителей в судебном порядке.
• Организатор оставляет за собой право, изменить эти правила в любой момент, без предварительного уведомления участников турнира.

Этот топик — перевод первых двух частей руководства по написанию своего бота для Google AI Challenge.
Весь код написан на языке Python.

Шаг 1: Как избежать столкновений

План

Чтобы муравьи не сталкивались надо:
1) Предотвратить перемещение одного муравья на другого;
2) Предотвратить перемещение двух муравьев в одну и ту же точку;
3) отслеживать информацию о местонахождении всех наших муравьёв.

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