Личные инструменты

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

Материал из Lurkmore

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

Спортивное программирование (олимпиады по программированию, англ. programming contests) — потенциальная дисциплина специальной олимпиады. Заключается в решении весёлых и неповторимых абстрактных задач задротами-школьниками или студентами на скорость, хотя иногда играют и взрослые дядьки.

Содержание

Задачи бывают трёх типов (зависит от формата и степени доставления участникам):

  • алгоритмические — несколько задач на контест, которые возможно решить полностью или чуть менее, чем полностью.
  • оптимизационные — одна большая задача, полного решения не существует. Оценивается насколько далеко продвинулось решение участника(ов). В некоторых задачах решения участников взаимодействуют (игры).
  • исследовательские — как в ICFPC, где очки могут начисляются за успешное обнаружение чего-то в объекте.

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

По разным форматам правил проводятся региональные и мировые онсайт-соревнования, интернет-соревнования и онсайт-финалы, ну или просто соревнование проводится один раз в год.

Также существуют сайты, позволяющие задрачивать в любое время суток.

Типичный спортивный программист[ЩИТО?]

Наиболее успешны обычно те, кто начинает задрачивать со школьного возраста. Особо преуспел как в подготовке спортсменов-программистов, так и в распиаривании этой деятельности, СПбГУ ИТМО.

В этой стране ICFPC широко популяризировался после этого поста. В 2010 году в топ 100 ICFPC русских комманд было сильно дохуя.

[править] Форматы правил

ACM — для студентов вузов. Длительность 5 часов. Сдача решений проводится интерактивно, то есть отправленное решение сразу компилируется на сервере и сообщается результат прогона на тестах. Участвовать в финале чемпионата мира студент может только 2 раза (в отборочных региональных — 5 раз), поэтому топовый вуз будет терять до 3 лучших участников 2 раза в год и должен готовить новое мясо. Правила ACM являются наиболее популярными также и для разных местных, не связанных с ACM, соревнований (как личных, так и командных).

ACM плюс — то же самое, что и ACM, но за успешно задачу начисляется не одно очко, а 1 минус 0.2*количество неудачных попыток по ней, поэтому задача, сданная с 6-й попытки или после, ухудшает результат участника.

IOI — для школьников. Решений можно слать много, уже несколько лет можно узнать результаты проверки прямо на контесте и в случае фейла засабмитить с еще одним костылём. К сожалению, чтобы не превращать в ACM, были придуманы токены — две шняги с регеном в полчаса, которые сообщают полные резы (без них доступно только на части тестов). Количество баллов за задачу зависит от количества пройденных тестов (максимальное = 100, иногда дотягивают до 110).

Topcoder algorithm — для всех желающих. Уникально тем, что вполне полноценно можно играть в одном java-клиенте и не имея у себя никаких компиляторов. Проверка же решений неинтерактивная, то есть о фейле можно узнать в самом конце. Есть веселая возможность попытаться сфейлить решение другого участника, скормив ему неудобоваримые входные данные (но соответствующие условию задачи). Алсо, самый благоприятный для читеров формат.

Google Code Jam — участники получают на каждую попытку рандомно сгенерированный тест и прогоняют его у себя. Поэтому можно использовать почти любой язык.

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

[править] Работа жюри

Поддерживает работу тестирующей системы, зоопарка компиляторов, пишет задачи, тесты и эталонные решения к задачам, а также отвечает на вопросы участников трёхзначной булевой логикой: YES, NO, NO COMMENT (самый частый ответ). Иногда жюри фейлит и вставляет в набор тесты, не соответствующие условию, и обнаружив это, делает повторное тестирование на исправленном наборе тестов — реджадж. Или не делает.

[править] Личности

  • Билл Пучер — директор ACM ICPC, большой любитель классической музыки.
  • Пётр Митричев — обычно считается самым сильным олимпиадником (40+ фактов о Пете Митричеве), однако зафейлил обе попытки в финалах ACM ICPC, где команда МГУ занимала 2-е места.
  • Андрей Станкевич — вице-директор Северо-Западного полуфинала АСМ, вице-чемпион России 1999 и 2000 гг., серебряный призер финала ACM 2000 года, золотой призер финала ACM 2001 года, ит.д. ит.п. А чем можешь похвастаться ты, мой юный падаван?
  • Степан Гатилов — студент НГУ, получивший у Медведева отмазку за пропуски инъяза
  • Томек Чайка — пшек. Выигрывал как Topcoder Open, так и ACM ICPC.
  • Геннадий Короткевич aka tourist — школьник-вундеркинд из Бульбостана. На этих ваших Codeforces имеет рейтинг выше самого Пети Митричева, что кагбе намекает.
  • Снарк — имеет бороду, ведёт открытый кубок (OpenCup), являющийся зеркалом разноместных онсайт-контестов по правилам ACM, также любитель придумывать новые правила для своих собственных контестов.

[править] Холиворы

Темы специальных олимпиад:

  • могут ли олимпиадники заниматься настоящим программированием?
  • нужна ли популяризация олимпиадного программирования?
  • нужно ли использовать макросы?

Аргументы сторон:

За:

  • Алгоритмы нужны для разработки чего-то большого и нового. Такую систему, как поиск гугла, невозможно спроектировать с помощью обычных приёмов декомпозиции и паттернов программирования.
  • Не удивительно потому, так как крупные корпорации уделяют особое внимание этим соревнованиям и самим олимпиадникам. Победители мировых олимпиад 2000 и 2001 годов Андрей Лопатин и Николай Дуров работает на благо этого вашего Вконтактика.
  • Алгоритмы это наше всё!!!!1111расрас

Против:

  • Олимпиадные задачи могут вообще не иметь никакого отношения к практическому программированию. Например, решение может сводиться к вычислению аналитического выражения или выводу на печать константы (да-да, и такое бывает), то есть к области чистой математики.
  • Задачи, имеющие отношение к компьютерной тематике (например формат PCX или скан-коды клавиатуры) часто содержат ошибки, что как бы намекает на плохие познания авторов в компьютерах.
  • Ряд задач сводится к тому, чтобы закодить алгоритм, который есть в учебнике, но которого нет в стандартной библиотеке (типа максимального паросочетания или минимального разреза).
  • Решения олимпиадных задач очень короткие (обычно менее 200 строк), которые можно отладить с помощью грубой силы, напильника и кувалды.
  • Для решения используются самые базовые средства, чтобы сделать соревнования доступными для как можно большего числа участников. Поэтому можно даже не знать язык, на котором пишешь.
  • Заюзать какую-нибудь стороннюю библиотеку хер получится. Алсо, с этим связан фап на java BigInteger, пусть и неудобный, но доступный из коробки (в связи с этим авторы изобретают особо хитрожопые задачи, где длинная арифметика есть, а этот класс бесполезен; давать задачи, где очевидно применение BigInteger считается моветоном).
  • О звёздах прошлого обычно ничего примечательного не известно, разве только они переходят из участников в жюри. Вероятнее всего, у этого есть свои причины. Так Николай Дуров (брат Того Самого) сам убрал себя из списка создателей Контакта (возможно, опасаясь славы и троллей).

[править] Фабулы условий задач

К каждой задаче обычно придумывают сюжет. Иногда сюжет для уже готовых задач ВНЕЗАПНО меняют перед самым контестов, доставляя немало сюрпризов читающему её. Сюжет как правило не имеет с содержанием ничего общего, а также вводит в заблуждение Медведева (пруфлинк) условия с лулзами [1] [2]

Примеры:

Штирлиц и Мюллер играют в занятную игру, стреляя по очереди. После каждого выстрела кто-нибудь в очереди умирает. Если у еврея не осталось соседей, он в ужасе сам накладывает на себя руки. Пусть в очереди изначально было N человек и Штирлиц хочет убить последнего. Сможет ли он это сделать, если оба игрока будут действовать наилучшим образом?

Организация "Кот в танке" хочет захватить мир. Но у них возникла проблема...

Внимательный читатель может заметить, что (спойлер: "Кот в танке" - анаграмма одного хорошо известного в этой стране сайта (спойлер: ВКонтакте) )

Вам дано дерево, сплошь усеянное бобрами. ... «Боброжуй-0xFF» работает по следующему принципу: находясь в некоторой вершине u, он может перейти к вершине v, если они соединены ребром, и съесть ровно одного бобра из тех, что находятся в вершине v. ... Гарантируется, что бобры будут находиться в шоке от происходящего, поэтому не смогут перемещаться по дереву.

[править] Галерея

вин

Epic Win!

Билл Пучер смотрит на быдлокодеров и хеллоуворлдщиков, как на...

[править] Серверы

[править] См. также

Источник — «http://lurkmore.ru/Спортивное_программирование»