Соревновательное программирование - Competitive programming

Петр Митричев (слева) и Геннадий Короткевич (справа), два выдающихся программиста-конкурсанта, во время соревнований.

Соревновательное программирование — это интеллектуальный спорт, обычно проводимый через Интернет или локальную сеть , в котором участники пытаются программировать в соответствии с предоставленными спецификациями. Участников называют спортивными программистами . Соревновательное программирование признано и поддерживается несколькими многонациональными программными и интернет-компаниями, такими как Google и Facebook .

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

История

Одним из старейших известных конкурсов является ICPC , который зародился в 1970-х годах и вырос до 88 стран в своем выпуске 2011 года.

С 1990 по 1994 год Оуэн Астрачан , Вивек Кера и Дэвид Котц проводили одно из первых распределенных интернет-соревнований по программированию, вдохновленное ICPC.

Интерес к соревновательному программированию значительно вырос с 2000 года и тесно связан с развитием Интернета, который облегчает проведение международных соревнований онлайн, устраняя географические проблемы.

Обзор

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

Независимо от категории задачи процесс решения задачи можно разделить на два основных этапа: построение эффективного алгоритма и реализация алгоритма на подходящем языке программирования (набор разрешенных языков программирования варьируется от конкурса к конкурсу). Это два наиболее часто проверяемых навыка на соревнованиях по программированию.

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

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

Известные соревнования

Существует два типа форматов соревнований: краткосрочные и долгосрочные. Каждый раунд краткосрочного соревнования длится от 1 до 5 часов. Долгосрочные соревнования могут длиться от нескольких дней до нескольких месяцев.

Короткий срок

• International Collegiate Programming Contest (ICPC) — одно из старейших соревнований, для студентов вузов в группах по 3 человека.
• Международная олимпиада по информатике (IOI) — одна из старейших олимпиад для учащихся средних школ.
• Американская лига компьютерных наук (ACSL) - соревнование по информатике с письменными частями и программированием для учащихся средних и старших классов.
• CodeChef - конкурс проводится с 2009 года, каждый месяц проводится три конкурса и ежегодный конкурс CodeChef SnackDown.
• Codeforces Round — обычно двухчасовое соревнование, проводимое каждую неделю.
• Facebook Hacker Cup - соревнование, проводимое с 2011 года, организованное и спонсируемое Facebook .
• HackerRank - несколько соревнований
• Gridwars - четыре соревнования, проведенные в период с 2003 по 2004 год.
• Google Code Jam - соревнование, проводимое с 2003 г., организованное и спонсируемое Google .
• IEEEXtreme Programming Competition — ежегодное соревнование для студентов-членов IEEE, проводимое IEEE с 2006 года .
• Topcoder Open (TCO) - соревнование по алгоритмам, проводимое Topcoder с 2001 года.

В большинстве вышеперечисленных соревнований, поскольку количество участников довольно велико, соревнования обычно организуются в несколько туров. Обычно они требуют онлайн-участия во всех раундах, кроме последнего, который требует участия на месте. Особым исключением является IEEEXtreme, ежегодное 24-часовое соревнование по виртуальному программированию. Лучшие участники IOI и ICPC получают золотые, серебряные и бронзовые медали, а на других соревнованиях лучшие участники получают денежные призы. Также попадание на первые места в рейтинговых таблицах таких конкурсов может заинтересовать рекрутеров из софтверных и интернет-компаний.

Долгосрочные

• Неделя кода HackerRank
• ICFP Programming Contest - ежегодное трехдневное соревнование, проводимое с 1998 года Международной конференцией по функциональному программированию .
• Матчи Topcoder Marathon
• Codechef Long Challenges — проводится каждый месяц — длится до 10 дней

Искусственный интеллект и машинное обучение

• Kaggle — соревнования по машинному обучению.
• CodeCup — соревнование по ИИ в настольных играх, которое проводится ежегодно с 2003 года. Правила игры публикуются в сентябре, а финальный турнир проводится в январе.
• Google AI Challenge - двухгодичные соревнования для студентов, которые проводились с 2009 по 2011 год.
• Halite — задача по программированию ИИ, спонсируемая Two Sigma, Cornell Tech и Google.
• Кубок России по программированию искусственного интеллекта

Конкурсы, посвященные технологиям с открытым исходным кодом

• Список может быть неполным

Онлайн-конкурс и обучающие ресурсы

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

Известные участники

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

• Геннадий Короткевич (турист)
• Петр Митричев (Петр)
• Макото Соэдзима (rng_58), один из бывших администраторов и авторов проблем Topcoder и один из основателей Atcoder.
• Тяньчэн Лу (ACRush), двукратный победитель Google Code Jam (2008 и 2009), соучредитель Pony.ai
• Адам Д'Анджело , технический директор Facebook и основатель Quora .
• Скотт Ву (scott_wu), технический директор Lunchclub .
• Матей Захария (Matei), доцент Стэнфордского университета и основатель Databricks .

Преимущества и критика

Участие в олимпиадах по программированию может повысить интерес студентов к изучению компьютерных наук . Навыки, полученные на соревнованиях по программированию, подобных ICPC, также улучшают карьерные перспективы, поскольку помогают пройти «технические собеседования», которые часто требуют от кандидатов решения сложных программных и алгоритмических задач на месте.

Также была критика конкурентного программирования, особенно со стороны профессиональных разработчиков программного обеспечения. Одним из важных моментов является то, что многие быстро развивающиеся соревнования по программированию учат участников плохим привычкам программирования и стилю кода (например, ненужному использованию макросов , отсутствию абстракции ООП и комментариев, использованию коротких имен переменных и т. д.). Кроме того, предлагая только небольшие алгоритмические головоломки с относительно короткими решениями, соревнования по программированию, такие как ICPC и IOI, не обязательно учат хорошим навыкам и практикам разработки программного обеспечения, поскольку реальные программные проекты обычно состоят из многих тысяч строк кода и разрабатываются большими командами в течение более чем одного года. длительные периоды времени. Питер Норвиг заявил, что, судя по имеющимся данным, победитель конкурсов по программированию отрицательно коррелирует с эффективностью работы программиста в Google (хотя у победителей конкурсов были более высокие шансы получить работу). Позже Норвиг заявил, что эта корреляция наблюдалась на небольшом наборе данных, но ее нельзя было подтвердить после изучения большего набора данных.

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

Литература

• Халим, С., Халим, Ф. (2013). Соревновательное программирование 3: Новая нижняя граница соревнований по программированию . Лулу.
• Лааксонен, А. (2017). Руководство по конкурентному программированию (темы бакалавриата по информатике). Чам: Springer International Publishing.

Смотрите также

• Категория:Конкурсы по информатике
• Код гольф
• Хакатон

использованная литература

внешняя ссылка

Проект с открытым исходным кодом для проведения конкурсов

• Система управления соревнованиями Инструмент с открытым исходным кодом на Python для запуска и управления соревнованиями по программированию на сервере IOI 2012 и IOI 2013 .