Подготовка интернет-тура чемпионата по программированию на yandex. Contest

МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ

Вестник Сыктывкарского университета.

Серия 1: Математика. Механика. Информатика.

Выпуск 1 (26). 2018

УДК 37.018.4, 004

ПОДГОТОВКА ИНТЕРНЕТ-ТУРА ЧЕМПИОНАТА ПО ПРОГРАММИРОВАНИЮ НА YANDEX.CONTEST

Н. О. Котелина, Н. К. Попова

В статье обсуждается интернет-тур открытого чемпионата Сыктывкарского государственного университета им. Питирима Сорокина по программированию, проведенный в рамках проекта «Развитие сетевого взаимодействия в области математики, физики, информатики и робототехники между образовательными организациями финно-угорских республик Российской Федерации». Ключевые слова: интернет-тур, Яндекс.Контест, спортивное программирование.

1. Цели проведения и тематика интернет-тура

Интернет-тур открытого чемпионата Сыктывкарского государственного университета им. Питирима Сорокина по программированию проводился в рамках проекта «Развитие сетевого взаимодействия в области математики, физики, информатики и робототехники между образовательными организациями финно-угорских республик Российской Федерации» 10 февраля 2018 г. [5]. Предполагалось участие школьников Республики Коми и Марий Эл. Уровень участников ожидался самый разный — от начинающих до победителей и призеров ВсОШ. Это определило состав задач и тексты заданий.

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

© Котелина Н. О., Попова Н. К., 2018.

соревнования следят ответственные на местах. Примером может служить организация интернет-тура во ВКОШП [2], где предварительно проводится регистрация ответственных лиц (аккредитованных преподавателей) .

Неорганизованные участники физически могут находиться в произвольном месте — дома, в школе, кафе, лишь бы был доступен Интернет. Примером может служить организация интернет-туров на Codeforces [3]. В этом случае организаторы не могут быть уверены в соблюдении правил контеста всеми участниками. При этом правила допускают использование любых видов информации, вплоть до использования чужого кода в своем решении.

В нашем случае предполагались неорганизованные участники, интернет-тур имел учебный характер, были представлены задачи на поиск и сортировку (см. табл. 1). Подбор задач осуществлялся с учетом будущего состава участников. Задачи были подобраны разноуровневые, доступные начинающим и интересные для опытных участников (см. табл. 1). Конечно, желательно иметь свой банк задач (оригинальные задачи), но на практике в контест часто включаются ранее использованные задачи с готовыми пакетами тестов, чекеров и разборами задач. Для таких задач придумываются новые формулировки (легенды), при этом надо следить, чтобы поиск по легенде не дал решения исходной задачи. Задачи для интернет-тура были взяты из источников [1], [4], [6]. Для примера приведем формулировку (легенду) задачи «Лестница в небо» (источник — задача А. Переключение гравитации в [4]).

«Женой богатыря Перы была красавица Зарни-ань, дочь Шон-ди (Солнца). Она была воплощением зари, добродетельной хозяйкой: вставала раньше и ложилась позже мужа. И присматривала за тем, чтобы солнечный огонь не сжег все живое.

Недоволен был Шонди тем, что у его дочери муж — земной человек, и забрал Зарни-ань на небо. Решил Пера забраться на небо, вернуть жену. Забрался Пера на гору Мань-Пупу-нёр (на языке манси — «малая гора идолов»), там столбы, из каменных блоков сложенные, стоят. Вот бы из них лестницу на небо построить! Помогла ему Парма, мать-тайга, дала силу великую, блоки перемещать. Когда Пера дует, блоки перемещаются слева направо с одних столбов на другие, выстраивая лестницу. При этом, дальше правого столба блоки переместиться не могут.

На рисунке ниже показано, как было и как стало по воле Перы и матери Пармы.

Рис. 1. Задача «Лестница в небо»

Найдите и вы число блоков в каждой ступеньке лестницы, выстроенной Перой».

Таблица 1

Тематика и сложность задач интернет-тура

№ 'Название Тематика % правильных попыток % решивших

1 Лестница в небо сортировка 43 79

2 Медвежий счет сортировка, работа со строками 40 52

3 Медвежья справедливость сортировка, работа с массивами, жадные алгоритмы 51 59

4 Наследники детей Оша устойчивая сортировка, структуры 13 24

5 Лесные хозяйства сортировка, бинарный поиск по ответу, арифметика с действительными числами 33 31

6 Книга белой совы бинарный поиск по ответу, арифметика с действительными числами 12 17

7 Асъя Кыа сортировка, хэши 5 3

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

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

2. Организационные проблемы и состав участников

В заключение обсудим организационные проблемы, возникшие при проведении интернет-тура. Была проведена адресная реклама интернет-тура, осуществлена рассылка приглашений участникам, учителям. Очевидно, что необходимо было продумать и реализовать автоматическую обработку заявок участников. Поскольку число участников предполагалось небольшим, то мы ограничились ручной обработкой: после получения всех заявок создали группу пользователей, которую добавили в число участников соревнования, сменили «отображаемые имена» участников и сделали рассылку логинов, паролей по электронной почте. Однако на интернет-тур зарегистрировалось 40 участников, и ручная рассылка оказалась трудоемкой. В будущих контестах для создания регистрационной формы с необходимыми полями и автоматической обработки заявок предполагается заранее осуществлять запросы в службу поддержки Яндекс.Контест с указанием собираемой об участниках информации. Также возможным решением является использование Google Forms и редактора скриптов или дополнений.

Для интернет-тура была специально создана открытая группа в Telegram, при помощи которой было организовано общение участников и организаторов по вопросам, связанным с контестом. Здесь же по завершении контеста прошел разбор наиболее интересных задач участниками.

Яндекс.Контест - удачный выбор для организации интернет-тура, участие в котором приняли не только студенты СГУ и школьники Сыктывкара, но и студенты ведущих вузов РФ и школьники республики Марий Эл (см. табл. 2). Сами участники, их учителя активно участвовали в обсуждении контеста, задач и подходов к их решению на организованной для них площадке в Telegram.

Таблица 2

Состав участников

Учебное заведение Количество участников

ФГБОУ ВПО "СГУ им. Питирима Соро- 6

кина"

Университет ИТМО (Санкт-Петербург) 1

НИУ МАИ (Москва) 1

НИУ ВШЭ (Москва) 2

ГОУ РК "ФМЛИ" (Сыктывкар) 9

МАОУ "ЛНД" (Сыктывкар) 1

ГОУ "КРЛ при СГУ" (Сыктывкар) 2

МОУ "Коркатовский лицей"(д. Корка- 6

тово, Марий Эл)

МБОУ "Лицей № 28 г. Иошкар- 1

Олы"

Список литературы

1. Архив материалов олимпиад / Олимпиады по информатике [Электронный ресурс]. URL: https://neerc.ifmo.ru/school/archive/index.html (дата обращения: 19.02.2018).

2. Официальный сайт Всероссийской командной олимпиады школьников по программированию / Олимпиады по информатике [Электронный ресурс]. URL: https://neerc.ifmo.ru/school/russia-team/index.html (дата обращения: 19.02.2018).

3. Правила соревнований / Соревнования по программированию 2.0 [Электронный ресурс]. URL: http://codeforces.com/blog/entry/4088?locale=ru (дата обращения: 19.02.2018).

4. Соревнования по программированию 2.0 [Электронный ресурс]. URL: http://codeforces.com (дата обращения: 19.02.2018).

5. Таблица результатов интернет-тура открытого чемпионата Сыктывкарского государственного университета им. Питирима Сорокина по программированию / Яндекс.Контест [Электронный ресурс].

URL: https://contest.yandex.ru/contest/7113/standings/ (дата обращения: 19.02.2018).

6. Timus Online Judge / Архив задач с проверяющей системой [Электронный ресурс]. URL: http://acm.timus.ru/ (дата обращения: 19.02.2018).

Summary

Kotelina N. O., Popova N. K. The preparation of the online round of the championship on programming on Yandex.Contest platform

The paper discusses the online round of the open programming championship of Pitirim Sorokin Syktyvkar State University conducted as part of a project «Development of network interaction in the field of mathematics, physics, computer science and robotics between educational organizations of the Finno-Ugric republics of the Russian Federation».

Keywords: online round, Yandex.Contest, competitive programming.

References

1. Arkhiv materialov olimpiad / Olimpiady po informatike (Archive of materials of Olympiads / Computer science Olympiads) URL: https://neerc.ifmo.ru/school/archive/index.html (date of usage: 19.02.2018).

2. Ofitsial'nyy sayt Vserossiyskoy komandnoy olimpiady shkol'nikov po programmirovaniyu / Olimpiady po informatike (Official site of the all-russian team Olympiad in programming / Computer science Olympiads) URL: https://neerc.ifmo.ru/school/russia-team/ index.html (date of usage: 19.02.2018).

3. Pravila sorevnovaniy / Sorevnovaniya po programmirovaniyu 2.0 (Competition rules / Programming competitions 2.0) URL: http:// codeforces.com/blog/entry/4088?locale=ru (date of usage: 19.02.2018).

4. Sorevnovaniya po programmirovaniyu 2.0 (Programming competitions 2.0) URL: http: //codeforces. com (date of usage: 19.02.2018).

5. Tablitsa rezul'tatov internet-tura otkrytogo chempionata Syktyvkar-skogo gosudarstvennogo universiteta im. Pitirima Sorokina po program-mirovaniyu / Yandeks.Kontest (Table of results of the online round

of the open programming championship of Pitirim Sorokin Syktyvkar State University / Yandex. Contest) URL: https: //contest. yandex. ru/contest/7113/standings/ (date of usage: 19.02.2018).

6. Timus Online Judge / Arkhiv zadach s proveryayushchey sistemoy (Timus Online Judge / The problems' archive with the testing system) URL: http://acm.timus.ru/ (date of usage: 19.02.2018).

Для цитирования: Котелина Н. О., Попова Н. К. Подготовка интернет-тура чемпионата по программированию на Yandex.Contest // Вестник Сыктывкарского университета. Сер. 1: Математика. Механика. Информатика. 2018. Вып. 1 (26). C. 73-79.

For citation: Kotelina N. O., Popova N. K. The preparation of the online round of the championship on programming on Yandex.Contest platform, Bulletin of Syktyvkar University, Series 1: Mathematics. Mechanics. Informatics, 2018, 1 (26), pp. 73-79.

СГУ им. Питирима Сорокина

Поступила 25.03.2018