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

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

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

Первая статья — про составление задач.
Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.

Да, они сделали это! Нижегородская команда Vital Lab в условиях мощнейшей конкуренции заняла второе место в самой престижной категории конкурса Microsoft Imagine Cup 2009 — Software Design! От всей души поздравляем парней. Второй команде — московской SoundStreamers — повезло чуть меньше и они сошли с дистанции, не попав в шорт-лист.



Мы все только что вернулись с церемонии награждения и у нас есть буквально 15-20 минут на то, чтобы взять у обеих команд короткое интервью. С 02:00 мск — в прямом эфире! А завтра вечером запись будет доступна здесь же, в этом же топике.

P.S.: официальные новости о прошедшем мероприятии можно прочитать в студенческом блоге Microsoft, а подробный отчет в нескольких частях — в блоге Дмитрия Сошникова.

UPD: аудиозапись оказалась непригодна для публикации, что жаль :( Так что будет просто стенограмма. Ну а там, глядишь, парни и сами что-нибудь напишут в отдельном посте.

Видео-репортажи по категории «Разработка встроенных устройств» (Embedded Development).

Сразу отвечу на вопрос «как там наши ребята с Украины»? Они там есть, смотрите видео ;)

Сегодня на финале Microsoft Imagine Cup последний день соревнований в основных категориях: Software Design и Embedded Developement. В каждой из них от России принимала участие одна команда: Vital Lab из Нижнего Новгорода и SoundStreamers из Москвы соответственно. Последние, к сожалению, сошли с дистанции еще на первых порах и не попали в топ-12 (своеобразный четверть-финал финала :)). А вот нижегородцы со своим проектом ViVa оказались не только в лучшей дюжине по итогам первых голосований судей, но и в топ-6 команд, а это означает, что от победы их сейчас отделяет всего лишь одна последняя презентация своего проекта, которая состоится в 17:00 мск уже завершилась. Результаты финала, кстати, будут известны во вторник вечером.

Я и мой коллега Дмитрий Shwars Сошников постараемся завтра или послезавтра собрать обе команды в одном из тихих уголков отеля и провести с ними совместное интервью, которое, если не подведет техника, будем транслировать в прямом эфире. Вопросов, уверен, у нас хватит и у самих, однако рады будем видеть и ваши: задавайте их здесь в комментариях.

Ссылка на прямую трансляцию появится позже.

UPD: кстати, не забываем поздравлять украинскую команду Intellectronics, которая вошла в топ-6 в категории Embedded Developement. Если получится, пригласим их на наше интервью.

^{P.S.: Студенты, которые приехали сюда побеждать, проделали огромную работу: они разработали интереснейшие проекты, придумали отличные презентации, прекрасно выступили и уверенно идут к победе, несмотря на некоторые неприятности. Поддержите их если и не комментарием, то хотя бы вниманием к этому событию, которое, к слову, может стать переломным в их жизни. Они в шаге от победы и им очень, очень нужна наша с вами поддержка. А минусы оставьте на потом, они вам еще пригодятся.}

ICFPC это ежегодный конкурс программистов. Здесь мой отчет об участии.

Задание описано сто раз, можно посмотреть здесь habrahabr.ru/blogs/icfpc/63279

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

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

Продолжение погружения в мир спортивного программирования уже на ваших экранах. Теперь будет самая вкуснятина. Раньше я ходил вокруг да около, теперь же пора взяться за самую суть. Посмотрим, как проходит какой-нибудь из туров, что длится в эти 5 часов азарта и креатива. Сегодня будет много всего весёлого.

Для тех, кому эта статья будет первой из цикла:

Первая статья — про составление задач.
Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.

И снова здравствуйте! Две статьи про олимпиадное программирование вообще и НГУшное в частности уже были опубликованы на Хабре. К сожалению, они слишком пестрили техническими подробностями, порой не интересными человеку со стороны (или же требующими дополнительных разъяснений). Сегодня я постараюсь исправить эту оплошность. Третья статья цикла будет об обратной стороне медали. На технике олимпиада может выехать, но без человеческого ресурса сложно. Вокруг той же Всесибирской проходит так много всего, что в пылу соревнований участники могут и не заметить. Зато всё это хорошо знакомо милым девушкам из оргкомитета, о работе которых (и не только о них) я сегодня и расскажу.

Для тех, кто только что переключился на наш канал:

Первая статья — про составление задач.
Вторая статья — про тестирующие системы.
Четвёртая статья — про тур непосредственно.

Я продолжаю свой цикл статей про спортивное программирование в НГУ. В прошлый раз я рассказал, как пишутся задачи для турниров, теперь же я хочу рассказать немного о тестирующей системе.

Первая статья — про составление задач.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.

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

В эту пятницу 26 июня стартует ежегодный конкурс программирования, International Conference on Functional Programming Contest (сокращенно ICFPC). Конкурс знаменит оригинальными заданиями, варьирующимися от «очень интересных», до «срыв башни». Не смотря на слово «функциональный» в названии, никаких ограничений на используемый язык программирования нет (абсолютно! это традиция конкурса).

В прошлом году участвовало 330 команд со всего мира. В этом году снова приглашаются все желающие.
Конкурс длится три дня (72 часа). Участвовать можно, как самому, так и командой. Есть так называемый «скоростной тур» — ответ в первые 24 часа соревнования.

Задание будет выложено в Пятницу 26 июня в 22:00:16 MSD (время Московское летнее, GMT+4) на страницу конкурса icfpcontest.org (счетчик до начала icfpcontest.org/countdown.php)

Небольшой обзор заданий за прошлые годы. Многие из них стоят того, чтобы скачать условие и покопаться самому (поверьте мне это непередаваемое удовольствие).

Следующий год будет моим пятым и последним сезоном в ACM-олимпиадах. За эти годы накопилось много разных воспоминаний и знаний об олимпиадах, благо мой университет участвует в них весьма активно. Рассказывать только со стороны участника будет не совсем правильным, поскольку поучаствовать в олимпиадах могут многие, мне же довелось и быть в составе жюри (правда, школьных олимпиад). Расскажу немного интересных вещей изнутри, приоткрою чуть-чуть наше закулисье. Рассказ будет тесно связан с Открытой Всесибирской олимпиадой, поскольку с ней у меня общение самое тесное (да и проводится она нашим университетом).

Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.

В первой статье я хочу рассказать о составлении задач к этим олимпиадам. Дело увлекательное, творческое, но порой весьма муторное.

В Лас-Вегасе завершились финалы чемпионата TopCoder Open в номинациях Algorithms и Marathon Match.

Результаты Algorithms:
1. crazyb0y — Bin Jin, Китай
2. UdH-WiNGeR — Владислав Исенбаев, Россия, СПбГУ ИТМО
3. marek.cygan — Marek Cygan, Польша
4. Petr — Пётр Митричев, Россия, МГУ
5. Im2Good — Rune Fevang, Норвегия
6. lucasr — Lucas Agustin Rearte, Аргентина
6. SnapDragon — Derek Kisman, Канада
6. syg96 — Степан Гатилов, Россия, НГУ

Напомню, что Владислав Исенбаев также недавно стал чемпионом ACM ICPC.
Условия задач можно почитать здесь (нужна регистрация).

Результаты Marathon Match:
1. KOTEHOK — Андрей Лопатин, Россия, СПбГУ
2. Psyho — Przemyslaw Debiak, Польша
3. nhzp339 — Xiaoshi Lu, Китай

Впервые победителем TCO-2009 Algorithm стал школьник. Интересно, что он является также действующим победителем TopCoder High School. Другой интересный факт — второй и третий призёры TCO-2009 Algorithm становились победителями ACM ICPC в 2009 и 2007 годах соответственно, а победитель TCO-2009 Marathon Match — в 2000 и 2001 годах.

Ссылки:
Официальный веб-сайт чемпионата
Страница на SnarkNews, посвящённая TCO 2009

30 мая 2009 года пройдёт 11-й по счёту ежегодный чемпионат по программированию Internet Problem Solving Contest. Зарегистрироваться можно на официальном сайте по адресу http://ipsc.ksp.sk. Приглашаю к участию всех хабролюдей, интересующихся спортивным программированием.

Некоторые сведения о контесте:

1. Участвовать можно одному или командой из двух или трёх человек. При этом можно использовать для решения задач любое число компьютеров и любые языки программирования. Ведутся отдельные рейтинги для команд из одного человека и команд из школьников. Более подробно читайте в правилах.
2. Задачи по тематике схожи с задачами ACM ICPC, т.е. в основном алгоритмического плана. Отличие от ICPC состоит в том, что в качестве решений на проверку отсылается не исходный код, а выходные данные для заданных входных. У каждой задачи есть два набора входных данных — простой и сложный. За решение простого набора даётся 1 очко, сложного — 2. Задачи, входные/выходные данные и решения прошлых лет можно посмотреть в архиве.
3. Этот контест очень популярен среди «спортивных» программистов. Участвуя в нём, вы имеется шанс посоревноваться с лучшими в мире. Для примера почитайте отзыв Дениса Остапенко об IPSC 2008.
4. Контест длится 5 часов. Даётся 10-15 задач. Время начала в вашей временной зоне можно узнать здесь. По Москве это 16:00.

Хабрасообщество поддержало идею написания обзоров игр для программистов, поэтому я продолжаю эту серию статей. Напомню, в прошлый раз я рассказал Вам про игры Colobot и Ceebot.

Сегодня Вы узнаете про отличную игру Robocode. Она предназначена для продвинутому обучения Java, и имеет большие функциональные возможности, несмотря на кажущуюся внешнюю простоту.

Robocode — это обучающая игра с открытыми исходными кодами, разработанная Mathew Nelson и Flemming Larsen. Ее единственной целью было облегчение изучения языка программирования Java.

Для тех кто не только читает новости о acm турнирах но и сам не прочь поучаствовать в них…
Для тех у кого найдётся пара свободных часов на выходных для интересных задач…

В эту субботу, 25 апреля, пройдёт пятый по счёту, открытый чемпионат г. Харькова по спортивному программированию. Запись на чемпионат продлена до 24 апреля.

В Стокгольме подведены итоги XXXIII финала Чемпионата Мира по программированию.

Команда СПбГУ ИТМО получает золотые медали и становится чемпионом мира и Европы 2009 года!
Команда Tsinghua U заняла 2 место и получила золотые медали.
Команда СПбГУ заняла 3 место и получила золотые медали.
Команда Саратовского ГУ заняла 4 место и получила золотые медали.
Команда Oxford U заняла 5 место и получила серебряные медали.
Команда Zhejiang U заняла 6 место и получила серебряные медали.
Команда MIT заняла 7 место и получила серебряные медали.
Команда Алтайского ГТУ заняла 8 место и получила серебряные медали.
Команда Warsaw U заняла 9 место и получила бронзовые медали.
Команда U Waterloo заняла 10 место и получила бронзовые медали.
Команда Тбилисского ГУ заняла 11 место и получила бронзовые медали.
Команда Carnegie Mellon U заняла 12 место и получила бронзовые медали.

Чемпионом Африки и Ближнего Востока стала команда German University in Cairo.
Чемпионом South Pacific стала команда Melbourne U.
Чемпионом Южной Америки стала команда?..
Чемпионом Северной Америки стала команда MIT.
Чемпионом Азии стала команда Tsinghua U.
Чемпионом Европы стала команда СПбГУ ИТМО.
Сейчас в Стокгольме начался финал студенческого чемпионата мира по программированию.

Условия задач здесь: http://cm2prod.baylor.edu/resources/pdf/2009Problems.pdf

Команда СПбГУ ИТМО стала второй раз подряд чемпионами, притом разными составами команд!

Стали известны официальные результаты чемпионата.

4 команды сдали по 9 задач:

Saratov SU 1 (Bondarenko, Matov, Pak)
Moscow SU 3 (Angelyuk, Astakhov, Maksimenko)
Moscow SU 4 (Gusakov, Kornakov, Razenshteyn)
Saratov SU 2 (Ivanov, Klenov, Rakhov)

12 команд сдали по 8 задач:

SPb SU 1 (Davydov, Kopeliovich, Petrov)
SPb IFMO 1 (Buzdalov, Isenbaev, Kapun)
Tbilisi SU 1 (Bogdanov, Jimsheleishvili, Lekveishvili)
Ural SU 1 (Ayzenshteyn, Chevdar, Samsonov)
Belarusian SU 1 (Pronin, Rudol, Tsikhan)
Novosibirsk SU 1 (Atuchin, Butyugin, Sorokin)
Moscow SU 2 (Khalyavin, Miniailau, Shavlyugin)
Altai STU 1 (Akinshin, Izbyshev, Kolosovskiy)
Southern Ural SU (Bich, Mayorov, Vasilenko)
NTU of Ukraine KPI (Kasitskyi, Korduban, Sliusarenko)
SPb SU 2 (Bankevich, Gladkikh, Smirnov)
Belarusian SU 2 (Aliaksei, Mikhail, Tolstsikau)

В минувшую пятницу в главном офисе компании Google в Маунтин-Вью (Калифорния) состоялся мировой финал престижного соревнования по спортивному программированию Google Code Jam 2008. В этом году лучше всех представителей постсоветского пространства выступили белорусские программисты. Два выпускника факультета прикладной математики и информатики БГУ заняли 8 и 13 места в личном зачёте, в то время как лучшие из россиян финишировали только на 15, 18 и 19 местах.

Это при том, что по результатам отборочного этапа в финал попало аж 20 россиян, то есть каждый пятый из 100 финалистов был родом из России. По этому показателю Россия опередила даже Китай (19 финалистов) и США (15), не говоря уже об остальных.

Победили на конкурсе двое представителей Китая. Неожиданно хорошо выступили поляки (6 и 7 места). Полную таблицу с результатами можно посмотреть здесь.

С 13 по 15 мая в Лас-Вегасе (США) состоялись очные состязания завершающего этапа TopCoder Open 2008, фактически являющегося чемпионатом мира по программированию в личном зачёте. Состязания проходят в категориях Algorithm (спортивное программирование), Marathon (исследовательское программирование), Component (прикладное программирование) и Studio (графический и веб-дизайн).

Традиционно TopCoder Open (или TCO) привлекает тысячи участников со всего мира. В этом году в отборе на TopCoder Open в наиболее популярной категории Algorithm участвовало 3980 сильнейших программистов. Из них на очные полуфиналы в Лас-Вегас отправилось 72 лучших по итогам квалификации и четырех отборочных онлайн-туров. Среди этих 72 в мировой столице развлечений и были выявлены 10 финалистов категории Algorithm. А всего для участия во всех четырех категориях в этом году прибыло 120 человек.

Победителем TopCoder Open Algorithm в третий раз стал tomek (Tomasz Czajka, Польша). На втором месте Petr (Пётр Митричев, Россия, МГУ), на третьем — Eryx (Eryk Kopczynski, Польша). Burunduk1 (Сергей Копелиович, Россия, СПбГУ) занял 5 место, andrewzta (Андрей Станкевич, Россия, СПбГУ ИТМО) и vlad89 среди разделивших 6-9 места.

В финал TopCoder Open 2008 Algorithm вышло три российских участника, два польских, и по одному участнику из Украины, Китая, Австралии, Индонезии и Швеции.

К сожалению, Митричев не победил(. В 2006 году он победил.

Инфа взята с SnarkNews.
Итоговые результаты.

Интересные факты о ТопКодер Опен

А вообще финал был очень напряженным.

К примеру — With 20s left, Petr gets a third challenge to take the lead.
But 5s later tomek gets a successful challenge also, moving back into the lead! Real last-second excitement, the crowd was really making some noise.

Почитать текстовую трансляцию можно тут.

А вообще было классно.

Дорогой хабрапипл!

Я тут договариваюсь с командами, получившими золотые медали, на интервью. Завтра вечером буду беседовать с командой ИТМО. Если есть что-то такое, что вы всегда хотели про них знать :) или вообще о спортивном программировании, пишите в коменты. Лучшие вопросы я задам с указанием авторства вопроса. Напоминаю, что золото у нас у команд питерского ИТМО, MIT, ИжГТУ и Львовского НУ им. Ивана Франка.