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

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше? В эту статью нужно добавить как можно больше лулзов, сфейлившихся участников, фотографий, заданий и программ-решений. Также сюда можно добавить интересные факты, картинки и прочие кошерные вещи. Файл:Файл:Zhirobas.jpg Типичный участник Спортивное программирование (олимпиадное программирование, олимпиады по программированию, англ. competitive programming) — решение весёлых и неповторимых абстрактных задач задротами-школьниками и к ним приравненными. Задачи В зависимости от формата и степени доставления участникам бывают: алгоритмические — несколько задач на контест, которые возможно решить полностью или чуть менее, чем полностью. оптимизационные — одна большая задача, полного решения не существует. Оценивается насколько далеко продвинулось решение участника(ов). В некоторых задачах решения участников взаимодействуют (игры). исследовательские — как в ICFPC, где очки могут начисляются за успешное обнаружение чего-то в объекте. Решением обычно является программа на одном из установленных языков программирования. Она компилится на сервере, запускается в сандбоксе, читает ввод из stdin или файла и таким же образом выводит результат. Красота да и только. По разным форматам правил проводятся региональные и мировые онсайт-соревнования, интернет-соревнования и онсайт-финалы, ну или просто соревнование проводится один раз в год. Также существуют сайты, позволяющие задрачивать в любое время суток. Наиболее успешны обычно те, кто начинает упарываться со школьного возраста. Особо преуспел как в подготовке спортсменов-программистов, так и в распиаривании этой деятельности, Университет ИТМО. В этой стране 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 — оптимизационная или исследовательская задача. На трое суток командой. Поэтому оно больше похоже на настоящее программирование, и не нацелено на школоту. Кто соснул? — тоже командная игра, но уже нацеленная на школоту. На любимом языке программирования решается некая задача и сравнивается с решениями на ЯП оппонентов. Результат сравнения трактуется в свою пользу. В ход идут подручные предметы. Популярно в /pr/ при подготовке к олимпиадам и просто так. Работа жюри Поддерживает работу тестирующей системы, зоопарка компиляторов, пишет задачи, тесты и эталонные решения к задачам, а также отвечает на вопросы участников трёхзначной булевой логикой: YES, NO, NO COMMENT (самый частый ответ). Иногда жюри фейлит и вставляет в набор тесты, не соответствующие условию, и обнаружив это, делает повторное тестирование на исправленном наборе тестов — реджадж. Или не делает. Личности Короткевич (справа) второй раз выигрывает ICPC Билл Пучер (Паучер) — бессменный директор ACM ICPC, большой любитель классической музыки. Андрей Станкевич — вице-директор Северо-Западного полуфинала АСМ (Россия и СНГ), призёр финалов ICPC 2000 и 2001 года, и вообще тот, на ком сейчас держится вся подготовка команд ИТМО. Геннадий Короткевич aka tourist — студент ИТМО из Бульбостана, выступающий за Россию. Обычно считается самым сильным олимпиадником, что подтверждают запредельный рейтинг на этих ваших Codeforces и первые места на IOI, ICPC, Google Code Jam, VK Cup, Topcoder Open, Яндекс. Алгоритм и т. д. и т. п. А чем можешь похвастаться ты, юный падаван? Пётр Митричев aka Petr — до прихода Гены был однозначно лучшим (40+ фактов о Пете Митричеве), но вопрос о том, кто сильнейший, ещё открыт. Обе попытки в финалах ACM ICPC частично зафейлил: команда МГУ занимала 2-е места. Снарк — имеет бороду, ведёт открытый кубок (OpenCup), являющийся зеркалом разноместных онсайт-контестов по правилам ACM, также любитель придумывать новые правила для своих собственных контестов. Владислав Исенбаев aka Winger — студент ИТМО, победивший в финале ACM 2009 года и зафейливший две последующие попытки попасть в финал, проиграв другой команде собственного университета. Степан Гатилов — студент НГУ, получивший у Медведева отмазку за пропуски инъяза Томек Чайка — пшек. Выигрывал как Topcoder Open, так и ACM ICPC. Один из участников знаменитой сумасшедшей IT вечеринки (фотография сделана в 1997 году в польском математическом лагере, собравшем победителей региональных математических олимпиад для подготовки к международным олимпиадам). Ferlon — яркий пример фимоза на почве задротства. Холиворы могут ли олимпиадники заниматься настоящим программированием? нужна ли популяризация олимпиадного программирования? нужно ли использовать макросы? Аргументы за Алгоритмы нужны для разработки чего-то большого и нового. Такую систему, как поиск гугла, невозможно спроектировать с помощью обычных приёмов декомпозиции и паттернов программирования. Не удивительно потому, так как крупные корпорации уделяют особое внимание этим соревнованиям и самим олимпиадникам. Победители мировых олимпиад 2000 и 2001 годов Андрей Лопатин и Николай Дуров работали на благо этого вашего Вконтактика. Алгоритмы это наше всё!!!!1111расрас Против Олимпиадные задачи могут вообще не иметь никакого отношения к практическому программированию. Например, решение может сводиться к вычислению аналитического выражения или выводу на печать константы (да-да, и такое бывает), то есть к области чистой математики. Как правило код, написанный олимпиадниками никто, включая самого автора, потом не поймёт. В серьёзном промышленном программировании, понятный и сопровождаемый код с чёткой архитектурой ценится несравненно выше чем замысловатый и в разы более быстрый, т.к. зачастую стоимость вычислительных ресурсов ничтожна по сравнению со стоимостью разработки и поддержки. Кроме того оптимизировать, например писать ассемблерные вставки или использовать нетривиальные алгоритмы, имеет смысл только отлаженный код и только в узких местах. Задачи, имеющие отношение к компьютерной тематике (например формат PCX или скан-коды клавиатуры) часто содержат ошибки, что как бы намекает на плохие познания авторов в компьютерах. Ряд задач сводится к тому, чтобы закодить алгоритм, который есть в учебнике, но которого нет в стандартной библиотеке (типа максимального паросочетания или минимального разреза). Решения олимпиадных задач очень короткие (обычно менее 200 строк), которые можно отладить с помощью грубой силы, напильника и кувалды. Для решения используются самые базовые средства, чтобы сделать соревнования доступными для как можно большего числа участников. Поэтому можно даже не знать язык, на котором пишешь. Заюзать какую-нибудь стороннюю библиотеку хер получится. Алсо, с этим связан фап на java BigInteger, пусть и неудобный, но доступный из коробки (в связи с этим авторы изобретают особо хитрожопые задачи, где длинная арифметика есть, а этот класс бесполезен; давать задачи, где очевидно применение BigInteger считается моветоном). О звёздах прошлого обычно ничего примечательного неизвестно, разве только они переходят из участников в жюри. Вероятнее всего, у этого есть свои причины. Так Николай Дуров (брат того самого) сам убрал себя из списка создателей Контакта (возможно, опасаясь славы и троллей). Фабулы условий задач К каждой задаче обычно придумывают сюжет. Иногда сюжет для уже готовых задач ВНЕЗАПНО меняют перед самым контестом, доставляя немало сюрпризов читающему её. Сюжет как правило не имеет с содержанием ничего общего, а также вводит в заблуждение Медведева. Примеры Штирлиц и Мюллер играют в занятную игру, стреляя по очереди. После каждого выстрела кто-нибудь в очереди умирает. Если у еврея не осталось соседей, он в ужасе сам накладывает на себя руки. Пусть в очереди изначально было N человек и Штирлиц хочет убить последнего. Сможет ли он это сделать, если оба игрока будут действовать наилучшим образом? Организация «Кот в танке» хочет захватить мир. Но у них возникла проблема… Внимательный читатель может заметить, что (спойлер: «Кот в танке» — анаграмма одного хорошо известного в этой стране сайта (спойлер: ВКонтакте)) Вам дано дерево, сплошь усеянное бобрами. … «Боброжуй-0xFF» работает по следующему принципу: находясь в некоторой вершине u, он может перейти к вершине v, если они соединены ребром, и съесть ровно одного бобра из тех, что находятся в вершине v. Гарантируется, что бобры будут находиться в шоке от происходящего, поэтому не смогут перемещаться по дереву. В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение «зован». На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых — синие, а в остальных — зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Была на одном соревновании задача, в которой авторы сумели особенно отличиться: «В этой задаче нет лихо закрученной формулировки, за уши притянутой к деятельности фирмы СКБ Контур. Более того, в этой задаче вообще нет формулировки». Ну и клюква иногда тоже встречается, куда ж без неё. Галерея 13yesПоказатьСкрыть Вин Epic Win! Билл Пучер смотрит на быдлокодеров и хеллоуворлдщиков, как на… Серверы codeforces.ru. Спортивное программирование c УГ и кармадрочерством topcoder.com. Примерно то же самое acm.timus.ru. Годный архив задач с уральских соревнований spoj.pl. Пшековский сервер, задач более 9000. Можно сдавать решения на хаскеле и брэйнфаке informatics.mccme.ru. В основном создавался для школьников acm.uva.es acm.sgu.ru acm.ssau.ru opencup.ru e-olimp.com codeeval.com acmp.ru codingame.com codewars.com См. также Демосцена Спортивное программирование — это не баг, это фича! Мета DRM (SecuROM • StarForce) • Баг • Бот (Автоответчик) • Ботнет • Варез • Глюк • Гуй • Донат • Копирайт (By design) • Лог • Нюк • Рут (Не работай под рутом) • Спортивное программирование Фичи 12309 • BSOD • Cookies • Embrace, extend and extinguish • FL Studio • Sheep.exe • Winlogon.exe • Бубен • Защита от дурака • Костыль • Машинный перевод • Пасхальные яйца • Свистелки и перделки • См. рис. 1 • Съешь ещё этих мягких французских булок • Таблэтка Вредоносное Винлок • Звонилка • Китайские пингвины • Пиксель смерти • Троян • Червь Морриса Компании 1С • Apple • Denuvo • Google • Microsoft • SAP • Яндекс Движения 8-bit • Open source (Красноглазики • Линуксоиды) • Вирусная сцена • Даунгрейд • Демосцена • Моддинг Офис 3DS MAX • GIMP • GNU Emacs • Movie Maker • MS Paint • OpenOffice • PowerPoint • vi • Word • Блокнот • Фотошоп ОС Android • BSD • DOS • MenuetOS • ReactOS • Windows (Phone 7 • Phone 8 • Seven • Vista) / Маздай • Линукс • Русская ОС • Фантом ОС Браузеры Internet Explorer • Опера • Тормозилла (Огнелис • Lolifox) • Хром Интернет Flash • I2P • Low Orbit Ion Cannon • Tor • Tunatic • Чат−клиенты (Miranda • QIP • Skype • Аська • Жаббер) Разработка BrainFuck • C • C++ • Java • Haskell • Ассемблер Люди LovinGOD • Балмер • Гейтс • Генерал Фейлор • Джобс • Митник • Поттеринг • де Раадт • Спольски • Столлман • Торвальдс • Шахиджанян Костыли Cygwin • PunkBuster • T9 • Wine • Wishmaster • Антивирусы • Хакинтош Команды ^H • ^W • Alt+F4 • Ctrl+Alt+Del • man • /me • /quit • rm -rf О спорт, ты — мир! Мета Adidas • Let's get ready to rumble! • Букмекерская контора • Олимпиада (Ванкувер 2010 • Московская Олимпиада • Сочи 2014 • Специальная Олимпиада) • Перлы комментаторов • Респект таким парням • Фанаты (Remi Gaillard • Егор Свиридов) • Фитнес-центр • Хоккей Суицидальный Альпинизм • Дайвинг • Парашютизм • Парапланеризм • Сноуборд Боевые искусства Айкидо • Бокс • Брюс Ли • Валуев • Дацик • Кочергин • Схватка двух йокодзун • Тайсон • Михалок Возня вокруг мячей ru_football • Вувузела • Зидан • Моуринью • Ногомяч • Российский футбол • Футбольный хулиган • Чемпионат.ру • Яо Мин Авто/мото/вело DTM • NASCAR • Велоспорт • Монстр-трак • Мотоспорт • Ралли • Формула 1 Мыслеспорт Magic: The Gathering • Speedcubing • Го • Покер • Преферанс • Спортивное программирование (Демосцена) • Что? Где? Когда?/Спортивное ЧГК (Агняша • Барщевский • Вассерман • Друзь • Жарков • Гладиолус) • Снукер • Шахматы (Известные шахматисты) Ритм-спорт DDR • PIU • Ритмическая гимнастика • Хастл Недо-спорт Бодибилдинг (Невский • Турчинский • Шварценеггер) • Ботинкометание • Геокешинг • Дворовые игры • Кроухантинг • Крысинг • Литрбол • Паркур • Рестлинг (Масаки Сумитани • Рестлеры) • Рыбалка • Скейтинг • Диггерство / Сталкерcтво / Руфинг • Страйкбол / Пейнтбол / Хардбол • Стритрейсинг • Турникмены • Экстремальные городские игры • Электричкинг (Метроэлектричкинг) Любой программист без словаря поймёт, что такое Спортивное программирование Языки программирования Промышленные: 1С • BAT • C# • C • C++ • Java • JavaScript (AJAX) • Pascal • Perl • PHP • Python • Ruby • ABAP • Ассемблер • Васик • Фортран Эзотерические: BrainFuck • Erlang • Forth • Haskell • LISP (My other car) • Prolog • Tcl • TeX Профессии Быдлокодер • Программист • Тестировщик • Хакер • Хеллоуворлдщик Методы и стили Reverse Engineering • Анти-паттерн • Выстрелить себе в ногу • Грязный хак • Код (индусский) • Костыль • Метод научного тыка • Помолясь • Свистелки и перделки Прочее ++i + ++i • Deadline • %s • 640 килобайт • CMS • Dummy mode • ЕГГОГ • Foobar • God is real, unless explicitly declared as integer • GOTO • Ifconfig • KISS • RegExp • SICP • sql.ru • Xyzzy • Дискета • Инжалид дежице • КОИ-8 • Лог • Ман • Рекурсия • СУБД • Тест Тьюринга • Умение разбираться в чужом коде • Фаза Луны • Фатальный недостаток