Соревнования по программированию. Где можно показать себя?
Недавно Facebook анонсировал свое соревнование по прогрммированию: Hacker Cup. Я ждал, что статья о нем на хабре появится сразу, но нет, поиск по такому запросу возвращает пустой результат.
Тогда я сделал поиск по запросу TopCoder Open и Google Code Jam, и, как и ожидалось, увидел только несколько статей с результатами соревнований. Значит надо заполнить эту нишу и написать статью о том, что же такое соревнования по программированию, с чем их едят, и как ты, дорогой хаброюзер, можешь в них поучаствовать, и что тебе это даст.
Я расскажу исключительно о так называемом «спортивном» программировании.
ICPC проводится раз в год, участвовать в нем могут только студенты.
Участие командое, команды по три человека.
Каждый тур (т.н. контест) длится пять часов, командам предлагается от 8 до 12 задач разного уровня. Задачи не отсортированы по сложности, команда должна сама определить для себя сложность задач.
Решением задачи является код, читающий входные данные из файла (формат данных описан в условии задачи) и выводящий ответ в выходной файл (формат выходного файла также описан в условии).
Команда, написавшее решение задачи, отправляет его на проверку. Проверка проводится на наборе тестов, которые команде недоступны. Решение всех команд проверяется на одном и том же наборе тестов.
Решение задачи засчитывается только если оно выдает абсолютно правильный ответ на каждый из тестов, и для каждого теста делает это не более чем за указанное время не превышая установленный лимит памяти. Если хотя бы на одном тесте ответ неверный, или превышен лимит памяти или времени, задача не засчитывается. После отправки решения на проверку, команда узнает вердикт в течение нескольких минут.
Система ранжирования команд такова, что команда, решившая больше задач, всегда выше, чем команда, решившая меньше. При равенстве количества решенных задач команды ранжируются по штрафному времени, которое тем меньше, чем быстрее команда сдавала задачи и чем меньше делала неудачных попыток сдать задачу. Неудачные попытки по задачам, которые так и не были сданы, не влияют на штрафное время.
В течение первых четырех часов (из пяти) все команды видят полностью ситуацию других команд: какие задачи сданы, с какой попытки, какие задачи не сдаются. Это добавляет интереса соревнованию.
Для участия ВУЗ подает заявку, после чего в назначенное время в октябре-ноябре команда отправлятся на четвертьфинал. Четвертьфиналы известны тем, что в большинстве регионов проводятся на ужасном уровне. После четвертьфинала, в случае успеха, команда попадает на полуфинал в Санкт-Петербург, откуда 11-13 лучших команд едут на финал. В 2013 году финал пройдет в Санкт-Петербурге.
Совсем недавно закончился полуфинал 2010 года, в котором определились финалисты от нашего региона (СНГ без Украины). Результаты доступны здесь:
http://neerc.ifmo.ru/regional/standings/standings-with-time.html
Проходят все команды до Kazakh-British TU 1 включительно. От каждого ВУЗа едет максимум одна команда. Например, занявшая третье место команда МГУ не едет, потому что выше (на втором месте) уже есть команда, представляющая этот ВУЗ. Аналогично, не едет команда СпбГУ ИТМО с четвертого места (два года назад эта команда выиграла чемпионат мира).
На ICPC доступны только два языка программирования: C++ и Java.
Помимо ICPC существует ряд неофициальных онлайн соревнований и чемпионатов мира.
Три раза в месяц на сайте проходят онлайн соревнования, так называемые Single Round Matches. В настоящий момент никаких призов за участие нет, и люди участвуют только для удовольствия. И, конечно, для того, чтобы расти в регулярном рейтинге, который на сайте ведется. Долгое время рейтинг возглавлял россиянин Петр Митричев (Petr), но сейчас он уступил это место китайцу Лу Тиан Ченгу (ACRush).
Формат соревнования заметно отличается от ICPC.
1. Соревнование длится полтора часа вместо пяти для ICPC. Мало кто готов тратить пять часов своего времени, в то время как 1.5 часа чаще всего в своем расписании можно найти.
2. Вместо восьми задач предлагаются три. Задачи отсортированы по сложности: первая (250 поинтов) — очень простая, вторая (500 поинтов) сложнее и третья (1000 поинтов) очень сложная. При составлении задач авторов просят подбирать сложность так, чтобы первую задачу решало 90% людей, вторую — 50%. На третью задачу ограничений нет, и не редко она остается нерешенной.
3. Первый час и 15 минут вы читаете задачи и пишете их решения. При отправке решения вы не узнаете вердикт до конца соревнования. За каждую задачу вы получаете несколько поинтов. Количество зависит от сложности задачи. Если вы сдадите задачу в тот же момент, когда открыли ее условие, то вы получите максимальный балл (250, 500 или 1000 соответственно). Чем больше прошло времени с открытия условия, тем меньше поинтов. Если вы уже отправили решение, и поняли, что оно неверно, за повторную отправку с вас снимут дополнительно 10% поинтов по этой задаче.
4. Через 1:15 фаза решения задач прекращается, и начинается очень интересная фаза — Challenge. На этой фазе вам открываются решения 20 случайных участников, и, если вы уверены, что в решении какого-то участника есть ошибка, вы можете предложить тест, на котором это решение, по вашему мнению, не сработает. Если решение действительно выдаст неверный ответ на предложенном тесте, или не уложится в две секунды, или превысит лимит памяти, или упадет, вы получите 50 поинтов, а участник, написавший решение, потеряет все поинты за это решение. Если же решение справится с вашим тестом, то вы потеряете 25 поинтов.
5. После Challenge начинаются системные тесты, которые проверяют все устоявшие после Challenge решения на наборе системных тестов, а также не всех тестах, которые были предложены в течение Challenge фазы, и обнуляют поинты за те решения, которые не прошли хотя бы один тест.
Соревнование видется в двух дивизионах. В первом соревнуются опытные участники, во втором — менее опытные. Поэтому, если вы решите поучаствовать, вам не придется бороться с людьми, которые выигрывали чемпионаты мира.
Для решения задачи вам не надо писать никакого чтения/записи в файлы. Вместо этого необходимо написать класс, в котором реализовать метод, который принимает определенные параметры и возвращает определенное значение.
Single Round Matches очень интересны, и не слишком сложны. Посмотрите на календарь на сайте, найдите ближайший SRM, который не в пять утра, и попробуйте поучаствовать. Обещаю, это вам очень понравится.
Писать можно на C++, C#, Visual Basic и Java. Все используемые компиляторы уже заметно устарели, особенно это чувствуется для C#.
Раз в год TopCoder проводит чемпионат мира под названием TopCoder Open. Он состоит из квалификационного раунда, нескольких онлайн раундов, и онсайт раунда. В квалификационном раунде может участвовать каждый, несколько тысяч человек выходят в первый раунд. После первого раунда в каждый последующий раунд выходит все меньше и меньше людей, пока в последнем раунде не определятся счастливчики, которые едут на онсайт в Las Vegas, NV. Количество таких счастливчиков заметно зависит от экономической ситуации в мире. До 2008 года их было 48, в 2008 — 72, в 2009 — 18, в 2010 — 24.
Возможно, у вас не получится пройти на онсайт раунд, но участие в онлайн раундах с целью пробиться как можно дальше является очень захватывающим.
В настоящее время расписание TopCoder Open 2011 еще недоступно.
На TopCoder нет почти никаких ограничений на участие.
В настоящее время CodeForces не проводит выездных соревнований.
Введенная в 2008 году система заключается в следующем:
1. Соревнование длится от двух до трех часов, за исключением квалификационных раундов, которые длятся 24 часа.
2. Для решения предлагается от трех до шести задач разной сложности. Каждая задача имеет два теста: маленький и большой. На данные в тестах накладываются разные ограничения. Например, если задача просит вас отсортировать массив во входном файле, то в маленьком тесте могут гарантировать, что количество элементов не будет превышать 100, а в большом — 100 000.
3. Тесты изначально вам не доступны. Вы пишете решение задачи, и когда вам кажется, что решение готово, вы должны на своем компьютере запустить его для тестов. Для маленького и большого теста правила разные.
3.а. Для маленького теста вы нажимаете «скачать тест», после чего у вас есть две минуты на то, чтобы запустить свой код для этого теста, получить выходной файл, и отправить его обратно. Если ответ правильный, вы сразу об этом узнаете, и получаете баллы за тест. Если неправильный, вам это также сообщается, и вы можете продолжать решать задачу. Маленький тест можно отправлять сколько угодно раз.
3.б. Для большого теста вы нажимаете «скачать тест», после чего у вас есть восемь минут на то, чтобы запустить решение и отправить ответ. Вам не сообщается вердикт по решению, отправлять в течение восьми минут можно сколько угодно раз, после восьми минут отправть решение заново нельзя. Все большие тесты проверяются сразу после завершения соревнования, и неверные посылки убираются.
Каждому тесту в соответствие поставлено некоторое заранее известное количество поинтов. Побеждает участник, набравший максимальное количество поинтов. При равенстве поинтов побеждает тот, кто сдал последний тест раньше. При этом каждая неверная попытка по маленьким тестам добавляет четыре минуты штрафного времени.
Отправляя выходной файл для теста, свое решение надо тоже отправить, чтобы после соревнования организаторы могли убедиться, что оно у вас есть, но во время соревнования ваше решение на сервере гугла не запускается.
Решать можно на любом языке — любите перл, питон, actionscript, javascript? Пожалуйста! Если написанный код организаторы потом могут запустить у себя используя свободно доступные компиляторы и интерпретаторы. Вы можете использовать для решения Excel, Матлаб, даже листочек с ручкой, если задача совсем простая.
Расписание отборочных раундов очень похоже на расписание у топкодера. Сначала квалификацонный раунд, затем несколько онлайн раундов, затем онсайт раунд. В 2008 и 2009 году онсайт раунд проходит в штаб-квартире Google в Mountain View. В 2010 — в Ирландии. Квалификационный раунд отличается от остальных тем, что он длится 24 часа, участвовать можно в любой момент в течение этих 24 часов. Достаточно решить один любой маленький и один любой большой тест для того, чтобы пройти в первый онлайн раунд.
В 2011 году квалификационные раунды пройдут в Май и Июне, а финал — 29 июля. Место проведения пока не известно. В онсайт раунд выйдут 25 сильнейших по результатам последнего онлайн раунда.
http://www.facebook.com/note.php?note_id=467531498919&id=9445547199
Пока что не известно, каков будет формат проведения соревнований, но расписание настолько похоже на расписание Google Code Jam, что есть все основания полагать, что будет что-то очень близкое.
Регистрация открывается 20 декабря, квалификационные онлайн раунды пройдут в январе, 11 Марта пройдет финал в штаб-квартире Facebook в Пало-Альто, Калифорния. В финал выйдут 25 сильнейших по результатам отборочных раундов.
Тогда я сделал поиск по запросу TopCoder Open и Google Code Jam, и, как и ожидалось, увидел только несколько статей с результатами соревнований. Значит надо заполнить эту нишу и написать статью о том, что же такое соревнования по программированию, с чем их едят, и как ты, дорогой хаброюзер, можешь в них поучаствовать, и что тебе это даст.
Я расскажу исключительно о так называемом «спортивном» программировании.
ICPC
Самым известным соревнованием этого рода, наверное, является ACM ICPC. Оно же, скорее всего, будет наименее интересно среднему хаброюзеру из-за ряда ограничений. Тем не менее, я напишу о нем немного.ICPC проводится раз в год, участвовать в нем могут только студенты.
Участие командое, команды по три человека.
Каждый тур (т.н. контест) длится пять часов, командам предлагается от 8 до 12 задач разного уровня. Задачи не отсортированы по сложности, команда должна сама определить для себя сложность задач.
Решением задачи является код, читающий входные данные из файла (формат данных описан в условии задачи) и выводящий ответ в выходной файл (формат выходного файла также описан в условии).
Команда, написавшее решение задачи, отправляет его на проверку. Проверка проводится на наборе тестов, которые команде недоступны. Решение всех команд проверяется на одном и том же наборе тестов.
Решение задачи засчитывается только если оно выдает абсолютно правильный ответ на каждый из тестов, и для каждого теста делает это не более чем за указанное время не превышая установленный лимит памяти. Если хотя бы на одном тесте ответ неверный, или превышен лимит памяти или времени, задача не засчитывается. После отправки решения на проверку, команда узнает вердикт в течение нескольких минут.
Система ранжирования команд такова, что команда, решившая больше задач, всегда выше, чем команда, решившая меньше. При равенстве количества решенных задач команды ранжируются по штрафному времени, которое тем меньше, чем быстрее команда сдавала задачи и чем меньше делала неудачных попыток сдать задачу. Неудачные попытки по задачам, которые так и не были сданы, не влияют на штрафное время.
В течение первых четырех часов (из пяти) все команды видят полностью ситуацию других команд: какие задачи сданы, с какой попытки, какие задачи не сдаются. Это добавляет интереса соревнованию.
Для участия ВУЗ подает заявку, после чего в назначенное время в октябре-ноябре команда отправлятся на четвертьфинал. Четвертьфиналы известны тем, что в большинстве регионов проводятся на ужасном уровне. После четвертьфинала, в случае успеха, команда попадает на полуфинал в Санкт-Петербург, откуда 11-13 лучших команд едут на финал. В 2013 году финал пройдет в Санкт-Петербурге.
Совсем недавно закончился полуфинал 2010 года, в котором определились финалисты от нашего региона (СНГ без Украины). Результаты доступны здесь:
http://neerc.ifmo.ru/regional/standings/standings-with-time.html
Проходят все команды до Kazakh-British TU 1 включительно. От каждого ВУЗа едет максимум одна команда. Например, занявшая третье место команда МГУ не едет, потому что выше (на втором месте) уже есть команда, представляющая этот ВУЗ. Аналогично, не едет команда СпбГУ ИТМО с четвертого места (два года назад эта команда выиграла чемпионат мира).
На ICPC доступны только два языка программирования: C++ и Java.
Помимо ICPC существует ряд неофициальных онлайн соревнований и чемпионатов мира.
TopCoder SRMs и TopCoder Open
http://TopCoder.com/tc — это известный сайт, на котором проводятся различные соревнования по программированию. Помимо спортивного программирования можно поучаствовать в дизайне, разработке, сборке ПО, отлове багов, архитектуре и разных других. Но я остановлюсь только на спортивном программировании.Три раза в месяц на сайте проходят онлайн соревнования, так называемые Single Round Matches. В настоящий момент никаких призов за участие нет, и люди участвуют только для удовольствия. И, конечно, для того, чтобы расти в регулярном рейтинге, который на сайте ведется. Долгое время рейтинг возглавлял россиянин Петр Митричев (Petr), но сейчас он уступил это место китайцу Лу Тиан Ченгу (ACRush).
Формат соревнования заметно отличается от ICPC.
1. Соревнование длится полтора часа вместо пяти для ICPC. Мало кто готов тратить пять часов своего времени, в то время как 1.5 часа чаще всего в своем расписании можно найти.
2. Вместо восьми задач предлагаются три. Задачи отсортированы по сложности: первая (250 поинтов) — очень простая, вторая (500 поинтов) сложнее и третья (1000 поинтов) очень сложная. При составлении задач авторов просят подбирать сложность так, чтобы первую задачу решало 90% людей, вторую — 50%. На третью задачу ограничений нет, и не редко она остается нерешенной.
3. Первый час и 15 минут вы читаете задачи и пишете их решения. При отправке решения вы не узнаете вердикт до конца соревнования. За каждую задачу вы получаете несколько поинтов. Количество зависит от сложности задачи. Если вы сдадите задачу в тот же момент, когда открыли ее условие, то вы получите максимальный балл (250, 500 или 1000 соответственно). Чем больше прошло времени с открытия условия, тем меньше поинтов. Если вы уже отправили решение, и поняли, что оно неверно, за повторную отправку с вас снимут дополнительно 10% поинтов по этой задаче.
4. Через 1:15 фаза решения задач прекращается, и начинается очень интересная фаза — Challenge. На этой фазе вам открываются решения 20 случайных участников, и, если вы уверены, что в решении какого-то участника есть ошибка, вы можете предложить тест, на котором это решение, по вашему мнению, не сработает. Если решение действительно выдаст неверный ответ на предложенном тесте, или не уложится в две секунды, или превысит лимит памяти, или упадет, вы получите 50 поинтов, а участник, написавший решение, потеряет все поинты за это решение. Если же решение справится с вашим тестом, то вы потеряете 25 поинтов.
5. После Challenge начинаются системные тесты, которые проверяют все устоявшие после Challenge решения на наборе системных тестов, а также не всех тестах, которые были предложены в течение Challenge фазы, и обнуляют поинты за те решения, которые не прошли хотя бы один тест.
Соревнование видется в двух дивизионах. В первом соревнуются опытные участники, во втором — менее опытные. Поэтому, если вы решите поучаствовать, вам не придется бороться с людьми, которые выигрывали чемпионаты мира.
Для решения задачи вам не надо писать никакого чтения/записи в файлы. Вместо этого необходимо написать класс, в котором реализовать метод, который принимает определенные параметры и возвращает определенное значение.
Single Round Matches очень интересны, и не слишком сложны. Посмотрите на календарь на сайте, найдите ближайший SRM, который не в пять утра, и попробуйте поучаствовать. Обещаю, это вам очень понравится.
Писать можно на C++, C#, Visual Basic и Java. Все используемые компиляторы уже заметно устарели, особенно это чувствуется для C#.
Раз в год TopCoder проводит чемпионат мира под названием TopCoder Open. Он состоит из квалификационного раунда, нескольких онлайн раундов, и онсайт раунда. В квалификационном раунде может участвовать каждый, несколько тысяч человек выходят в первый раунд. После первого раунда в каждый последующий раунд выходит все меньше и меньше людей, пока в последнем раунде не определятся счастливчики, которые едут на онсайт в Las Vegas, NV. Количество таких счастливчиков заметно зависит от экономической ситуации в мире. До 2008 года их было 48, в 2008 — 72, в 2009 — 18, в 2010 — 24.
Возможно, у вас не получится пройти на онсайт раунд, но участие в онлайн раундах с целью пробиться как можно дальше является очень захватывающим.
В настоящее время расписание TopCoder Open 2011 еще недоступно.
На TopCoder нет почти никаких ограничений на участие.
CodeForces Beta Rounds
Codeforces — это портал, разработанный саратовскими финалистами ICPC прошлых лет и спонсируемый ВКонтактом. Формат соревнования похож чем-то на TopCoder SRMs, но немного более запутан. Общая идея также сводится к решению задач и попытке уронить решения других участников с тем отличием, что это все происходит одновременно, а не поделено на две фазы. На сайте тоже ведется регулярный рейтинг.В настоящее время CodeForces не проводит выездных соревнований.
Google Code Jam
До недавнего времени Google Code Jam проводился на системе TopCoder, и был фактически еще одним TopCoder Open. В 2008 году они написали свою систему, на которой с тех пор прошло три онсайт раунда. Сайт соревнования: http://code.google.com/codejamВведенная в 2008 году система заключается в следующем:
1. Соревнование длится от двух до трех часов, за исключением квалификационных раундов, которые длятся 24 часа.
2. Для решения предлагается от трех до шести задач разной сложности. Каждая задача имеет два теста: маленький и большой. На данные в тестах накладываются разные ограничения. Например, если задача просит вас отсортировать массив во входном файле, то в маленьком тесте могут гарантировать, что количество элементов не будет превышать 100, а в большом — 100 000.
3. Тесты изначально вам не доступны. Вы пишете решение задачи, и когда вам кажется, что решение готово, вы должны на своем компьютере запустить его для тестов. Для маленького и большого теста правила разные.
3.а. Для маленького теста вы нажимаете «скачать тест», после чего у вас есть две минуты на то, чтобы запустить свой код для этого теста, получить выходной файл, и отправить его обратно. Если ответ правильный, вы сразу об этом узнаете, и получаете баллы за тест. Если неправильный, вам это также сообщается, и вы можете продолжать решать задачу. Маленький тест можно отправлять сколько угодно раз.
3.б. Для большого теста вы нажимаете «скачать тест», после чего у вас есть восемь минут на то, чтобы запустить решение и отправить ответ. Вам не сообщается вердикт по решению, отправлять в течение восьми минут можно сколько угодно раз, после восьми минут отправть решение заново нельзя. Все большие тесты проверяются сразу после завершения соревнования, и неверные посылки убираются.
Каждому тесту в соответствие поставлено некоторое заранее известное количество поинтов. Побеждает участник, набравший максимальное количество поинтов. При равенстве поинтов побеждает тот, кто сдал последний тест раньше. При этом каждая неверная попытка по маленьким тестам добавляет четыре минуты штрафного времени.
Отправляя выходной файл для теста, свое решение надо тоже отправить, чтобы после соревнования организаторы могли убедиться, что оно у вас есть, но во время соревнования ваше решение на сервере гугла не запускается.
Решать можно на любом языке — любите перл, питон, actionscript, javascript? Пожалуйста! Если написанный код организаторы потом могут запустить у себя используя свободно доступные компиляторы и интерпретаторы. Вы можете использовать для решения Excel, Матлаб, даже листочек с ручкой, если задача совсем простая.
Расписание отборочных раундов очень похоже на расписание у топкодера. Сначала квалификацонный раунд, затем несколько онлайн раундов, затем онсайт раунд. В 2008 и 2009 году онсайт раунд проходит в штаб-квартире Google в Mountain View. В 2010 — в Ирландии. Квалификационный раунд отличается от остальных тем, что он длится 24 часа, участвовать можно в любой момент в течение этих 24 часов. Достаточно решить один любой маленький и один любой большой тест для того, чтобы пройти в первый онлайн раунд.
В 2011 году квалификационные раунды пройдут в Май и Июне, а финал — 29 июля. Место проведения пока не известно. В онсайт раунд выйдут 25 сильнейших по результатам последнего онлайн раунда.
Hacker Cup
И, наконец, новое соревнование, о котором недавно объявил Facebookhttp://www.facebook.com/note.php?note_id=467531498919&id=9445547199
Пока что не известно, каков будет формат проведения соревнований, но расписание настолько похоже на расписание Google Code Jam, что есть все основания полагать, что будет что-то очень близкое.
Регистрация открывается 20 декабря, квалификационные онлайн раунды пройдут в январе, 11 Марта пройдет финал в штаб-квартире Facebook в Пало-Альто, Калифорния. В финал выйдут 25 сильнейших по результатам отборочных раундов.
0 комментариев