Олимпиады по программированию
Олимпиада по программированию (олимпиада по информатике) — интеллектуальное соревнование по решению различных задач на ЭВМ, для решения которых необходимо придумать и применить какой-либо алгоритм или программу на одном из языков программирования. Как правило, участникам выдаётся комплект из нескольких задач. Задача считается решённой, если участники смогли составить программу, которая правильно работает на тестах, подготовленных жюри. Тесты участникам неизвестны.
Олимпиады бывают личные и командные. В командных олимпиадах обычно участвует 3 человека и им на всё время олимпиады предоставляется 1 компьютер для решения задач. Для проведения подобных соревнований используются специализированные программные турнирные системы.
Формат задач
[править | править код]Задачи по спортивному программированию уникальны тем, что ответом на них является программа, оптимально решающая задачу сразу для всех возможных входных данных.
Например, если самая простая задача по математике звучит как «Сложите два числа: 4 и 5», то самая простая задача по программированию прозвучит как «Напишите программу, которая складывает любые два числа». В этом случае от участника потребуется написать программу, которая считывает два числа через стандартный поток ввода, и выводит одно число — ответ на задачу — в стандартный поток вывода. Иногда организаторы соревнований предлагают считывать и выводить данные другим способом, например, через файлы. A+B — классическая задача для знакомства с таким форматом.
Конечно, жюри соревнований должно как-то убеждаться в том, что программа участника работает верно для любых данных. Для этого перед соревнованием готовится набор тестов, на которых будут запускаться решения участников, и набор ответов на них. Если у жюри и участника совпадут ответы на все тесты — решение получит полный балл, если нет — частичный или нулевой. На большинстве олимпиад проверка автоматизирована и производится сразу после отправки решения участником, что позволяет быстро сообщить ему результат и дать шанс доработать программу.
Часто решение проверяется не только на правильность, но и на эффективность. Для этого в тестирующей системе вводится ограничение на количество процессорного времени, которое может использовать загруженная программа, а входные данные в части тестов подбираются так, чтобы неэффективное решение работало слишком долго. В результате такое решение не проходит данные тесты и получает неполный балл.
Авторы стараются подбирать входные данные таким образом, чтобы время работы неэффективного решения во много раз превышало установленный лимит, что исключает влияние на результат различий в характеристиках процессора, погрешности измерений, влиянии Turbo Boost и других факторов. При этом замеряется процессорное, а не реальное время выполнения, так что загруженность процессора тестирующего сервера другими задачами так же не должна влиять на результат.
Тексты условий
[править | править код]В мире спортивного программирования существует определённый формат условий задач. Хотя он никем официально не стандартизируется, де-факто соревнования по всему миру делят условия задач на следующие подпункты:
- Легенда. Содержит основную информацию об условии задачи. Как правило, представляет собой короткий рассказ со своим сюжетом, героями и конфликтом. В условиях редко ведётся речь о структурах данных и алгоритмах, приводящих к решению. Таким образом, на этом этапе участник составляет математическую модель событий, и уже по ней будет строить подходящий алгоритм.
- Входные и выходные данные. Описывает формат, в котором записаны данные в тестах, и формат, в котором программа участника должна выводить ответ. Кроме того, содержит информацию о диапазоне значений, которые могут содержаться в тестах. Как правило, для форматирования данных используются только символы пробела и переноса строки. Например, массив из трёх чисел наверняка будет записан не как
[1, 2, 3], а как1 2 3. Это связано с тем, как в большинстве языков программирования работает ввод данных, и позволяет участникам быстрее считать их, не затрачивая время на парсинг. - Примеры. Показывает участнику данные из нескольких первых тестов. Это помогает не только точно понять формат входных и выходных данных, но и удостовериться, что на сервере программа компилируется и работает нужным образом: если на компьютере участника программа даёт правильные ответы на тесты из примеров, а на сервере — нет, можно сразу понять, что проблема в настройках компиляции или неопределённом поведении, и не искать ошибку в логике программы.
- Примечание (необязательно). Используется в сложных задачах для разбора примеров.
- Система оценки (необязательно). Некоторые задачи могут быть решены частично, поэтому авторы нередко награждают такие решения частичными баллами. Этот подпункт содержит информацию о том, сколько баллов получит программа, верно работающая лишь для определённых наборов входных данных.
- Протокол взаимодействия (необязательно). Нужен в задачах с необычной системой проверки для описания её тонкостей.
Олимпиады в СССР и России
[править | править код]Среди школьников
[править | править код]Первая олимпиада по программированию среди школьников г. Москвы прошла в 1981 году (на ней было всего 4 участника), а первая олимпиада в СССР (под названием олимпиада по информатике) прошла среди школьников и состоялась в 1988 году в Свердловске[1]. В дальнейшем олимпиады по информатике стали частью всесоюзных (а после распада СССР — всероссийских) предметных олимпиад школьников.
Традиционно олимпиады школьников являются личными соревнованиями, проводятся по многоуровневой системе, в несколько этапов: районные, городские, региональные, национальные олимпиады. Победители всероссийской олимпиады получают право участия в международных олимпиадах по информатике.
Перечневые олимпиады
[править | править код]Каждый год Российский Совет Олимпиад Школьников (РСОШ) составляет специальный перечень олимпиад, в числе которых могут находиться и личные олимпиады по спортивному программированию. Такие соревнования всегда проходят в два этапа: отборочный (онлайн) и заключительный (очно, но допускались исключения из-за пандемии COVID-19). Правом проведения перечневых олимпиад обладают только органы власти в сфере образования и высшие учебные заведения.[2]
Высокие результаты, показанные на таких олимпиадах, могут давать некоторые привилегии при поступлении в вуз, в том числе поступление без вступительных испытаний или округление результатов ЕГЭ по информатике до 100 баллов (если школьник набрал хотя бы 75 баллов).
Командные соревнования школьников
[править | править код]Также проводятся многоуровневые командные олимпиады среди школьников, по правилам аналогичным правилам международных студенческих олимпиад[3][4].
Самой известной командной олимпиадой является Всероссийская командная олимпиада школьников по программированию[5] (ВКОШП). Она обычно проводится в начале декабря в разных городах России: Санкт-Петербург, Барнаул и городах в других странах. На эту олимпиаду нужно отобраться в своём регионе, от Москвы обычно проходят 10—20 команд, от Санкт-Петербурга — чуть меньше[6].
Студенты
[править | править код]Есть мнение, что олимпиады по информатике среди студентов СССР в масштабах всей страны не проводились. Но это не так. В 1987 году в Тбилиси была такая олимпиада, на которую поехали несколько участников — призёров Московской городской олимпиады по программированию. Олимпиада запомнилась применением местной системы интерактивного доступа к компьютеру и тестирования программ, а также тем, что при вылете обратно в Москву Тбилиси окутал эпический туман и студенты 8 дней просидели в аэропорту, ожидая лётной погоды. В предыдущие годы московские студенты также боролись за право поехать на Всесоюзную олимпиаду по программированию. Московские городские олимпиады успешно проходили, как мининум, в период с 1979 по 1987 год с участием многих вузов.
Начиная с 1996 года студенты российских вузов начали участвовать в соревнованиях входящих в систему командного чемпионата мира по программированию среди студентов, проводимого американской ассоциацией ACM.
Также энтузиастами организовывались различные внутри- и межвузовские олимпиады. Обычно эти олимпиады проводятся при финансировании какой-либо фирмы, занимающейся разработкой программного обеспечения и заинтересованной в привлечении талантливых студентов на работу к себе.
Тестирующие системы и платформы
[править | править код]Процесс проверки решений требует вычислительных мощностей, точного измерения потребляемых ресурсов, поддержи большого количества компиляторов, изоляции выполняемых программ и многих других сложных технических решений. В России разработано несколько систем и платформ, предназначенных для проведения соревнований по программированию:
| Название | Состояние | Написано на | Примечание |
|---|---|---|---|
| ejudge | Поддерживется, распространяется по лицензии GPL | Си | Система с открытым исходным кодом, разработанная в 2000-х.
Из-за особенностей архитектуры не поддерживает многоядерную проверку, что сильно замедляет тестирование. Тем не менее, всё ещё используется на соревнованиях. |
| PCMS | Поддерживется | Java | Создан в 2004 году в Университете ИТМО для проведения собственных олимпиад и продолжает развитие в его стенах.
На этой тестирующей системе проводится Всероссийская Олимпиада Школьников. |
| Sort Me | Поддерживается | Go | Проект запущен 1 октября 2021 года.
Согласно утверждениям создателей, является самой быстрой в мире тестирующей системой, умеющей ускорять не только проверку, но и компиляцию программ.[7] Единственный в России проект, развивающийся без поддержки какого-либо университета, фонда или корпорации. |
| Codeforces | Поддерживается | Java | Создан в 2010 году в Саратовском Государственном Университете.
Самая популярная платформа для спортивного программирования. Библиотека testlib.h, созданная Codeforces, де-факто является стандартом для разработки задач. Проект локализован на английский язык, развивается при поддержке Университета ИТМО и зарубежных спонсоров. |
| Яндекс Контест | Поддерживается | Python | Проект компании Яндекс. Можно использовать для проведения собственных соревнований. Используется в основном для перечневых олимпиад и локальных тренировок. |
| Contester | Проект закрыт | Delphi / FreePascal | Создан в Ковровской Государственной Технологической Академии в 2008 году. Являлся standalone-сервером, содержащим около 130 задач. |
| Timus Online Judge | Поддерживается, но не развивается | Неизвестно | Большой онлайн-архив задач, разработанный в 2000-м году в Уральском Федеральном Университете. |
| acm.sgu.ru | Проект закрыт | Неизвестно | Сайт для тренировки студентов Саратовского Государственного Университета. |
| acmp.ru | Поддерживается | .NET | Большой архив задач, с 2006 года разрабатываемый при поддержке Красноярского Дворца Пионеров. На этом сайте проводятся школьные и муниципальные этапы Всероссийской Олимпиады Школьников (только для Красноярского Края). |
Олимпиады в Белоруссии
[править | править код]Олимпиады среди школьников
[править | править код]В Белоруссии олимпиады по программированию (по информатике) среди школьников проходит в несколько этапов.
Первый этап — внутришкольная олимпиада. Проводится среди учеников конкретного учреждения образования. В результате соревнования, победители проходят на следующий этап. Для проведения таких олимпиад используются системы тестирования (турнирные системы). Какую именно систему использовать решают организаторы олимпиады. Например, в Бресте используется система Brain Training, в некоторых заведениях система eJudge
Второй этап — муниципальная олимпиада (иногда её называют городской). Такая олимпиада проводится среди победителей предыдущего этапа, представленных каждой школой определённого района города. Например, в Бресте проводятся две районные олимпиады: для Московского и Ленинского района. Победители от каждого района проходят на следующий этап. Обязательные условия для продолжения участия в олимпиаде (переход на следующий этап) — набрать более 50 % возможных баллов (в 2014—2015 учебном году это правило отменено).
Третий этап — областная олимпиада. Здесь принимают участие победители предыдущего этапа (районной олимпиады). Вся Белоруссия разделена на 6 областей (Брестская, Витебская, Могилёвская, Гродненская, Гомельская и Минская), а также город Минск. Кроме того, в качестве отдельной команды выступает ГУО «Лицей Белорусского государственного университета». В каждой из них происходит отбор участников на следующий этап олимпиады.
Четвёртый этап — республиканская олимпиада (заключительный этап). Победители областных олимпиад соревнуются за звание лучшего программиста среди школьников.
Лучшие участники республиканской олимпиады (обычно только из 9-11 классов), отбираются на сборы по подготовке к международной олимпиаде по информатике. В течение сборов из них отбирается окончательная команда.
ACM International Collegiate Programming Contest
[править | править код]Крупнейшая международная студенческая командная олимпиада по программированию — ACM International Collegiate Programming Contest. Генеральными спонсорами чемпионата выступают такие компании как Microsoft и IBM. В 2004 году в ней участвовало 3150 команд из 75 стран.
Команды из России неоднократно становились победителями этого престижного соревнования[8][9][10][11][12]. По итогам удачных выступлений команды удостаивались встречи с Президентом РФ[13][14][15]. Один из тренеров и организаторов этих олимпиад в России был награждён Премиями Президента РФ и Правительства РФ в области образования[16].
Другие известные соревнования
[править | править код]Многие состязания по спортивному программированию не связаны напрямую с системой образования, то есть в них также принимают участие и профессиональные программисты. Популярное состязание по спортивному программированию в мире — ресурс TopCoder, на котором регулярно проводят раунды (SRM), по результатам которых формируется рейтинг участников, а также ежегодный TopCoder Open. Появившийся позднее российский ресурс Codeforces[англ.] также проводит регулярные раунды[16], по результатам которых формируется свой рейтинг. В конце 2021 года в России набрала популярность платформа Sort Me, ежемесячно проводящая Sort Me Round[17] по модифицированным правилам ACM[18].
Крупные ИТ-компании проводят регулярные и как правило личные соревнования по программированию, среди таковых — Google Code Jam (2003—2022), Facebook Hacker Cup (2011-настоящее время), Russian Code Cup (2011—2017), Codemasters Code Cup (2020-настоящее время).
Примечания
[править | править код]- ↑ Олимпиады — История олимпиады. Дата обращения: 9 сентября 2011. Архивировано из оригинала 10 августа 2011 года.
- ↑ Порядок проведения олимпиад школьников. Российская газета. Дата обращения: 25 января 2022. Архивировано 25 января 2022 года.
- ↑ Уральская региональная олимпиада по программированию. Центр классического образования УрФУ им. Б. Н. Ельцина (УрГУ). Дата обращения: 9 ноября 2011. Архивировано из оригинала 6 октября 2010 года.
- ↑ Олимпиады по информатике. Санкт-Петербург, Россия. Дата обращения: 9 ноября 2011. Архивировано 17 ноября 2011 года.
- ↑ Олимпиады по информатике. Санкт-Петербург, Россия. neerc.ifmo.ru. Дата обращения: 27 июля 2016. Архивировано 24 августа 2016 года.
- ↑ SN on ВКОШП - 2015 (англ.). vkoshp2015.snarknews.info. Дата обращения: 27 июля 2016. Архивировано 8 августа 2016 года.
- ↑ Sort Me. Telegram. Дата обращения: 9 мая 2022. Архивировано 9 мая 2022 года.
- ↑ SnarkNews. Дата обращения: 18 марта 2022. Архивировано 14 апреля 2021 года.
- ↑ Чемпионы мира из ИТМО в новостях РЕН ТВ :: :: Видео на RuTube (недоступная ссылка)
- ↑ В Петербурге открылась академия программирования — Наталья Шергина — «Чемпионы мира получили кластер» — Российская Газета — В Северной столице открылась … Дата обращения: 2 мая 2020. Архивировано 1 декабря 2017 года.
- ↑ Студенты ИТМО стали чемпионами мира по программированию. Дата обращения: 9 сентября 2011. Архивировано 3 ноября 2010 года.
- ↑ Дмитрий Медведев встретился с победителями чемпионата мира по программированию — Первый канал
- ↑ Президент сегодня встретился со студентами — победителями чемпионата мира по программированию — Первый канал
- ↑ Президент России Дмитрий Медведев продолжит традицию встреч с российскими студентами-победителями Чемпионата мира по программированию среди сборных команд вузов. — РИА Новости … Дата обращения: 9 ноября 2011. Архивировано 18 января 2012 года.
- ↑ Три золотых медали привезли в РФ победители первенства планеты по программированию — Первый канал. Дата обращения: 9 ноября 2011. Архивировано 8 августа 2013 года.
- ↑ 1 2 Станкевич Андрей Сергеевич (недоступная ссылка)
- ↑ sort-me.org - Resource - CLIST. clist.by. Дата обращения: 25 января 2022. Архивировано 25 января 2022 года.
- ↑ Sort Me, Sort Me. Правила Sort Me Round. Teletype (24 октября 2021). Дата обращения: 25 января 2022. Архивировано 25 января 2022 года.
