В этом году случилось уникальное событие — для большинства школьников России школьный этап всероссийской олимпиады школьников по информатике проводился по едиными правилам, общим комплектам задач (всего было 4 варианта заданий на всю страну), с использованием тестирующей системы.
Организация
Формально по порядку проведения ВсОШ за проведение школьного этапа отвечают муниципалитеты, поэтому уровень организации школьного этапа зачастую оставляет желать лучшего, а местами он и вообще не проводится. Образовательный центр "Сириус" взялся организовать школьный этап всероссийской олимпиады по шести предметам — математике, информатике, физике, химии, биологии, астрономии. В прошлом году была апробация для шести регионов. В этом году было предложено присоединиться всем регионам, "подписаться" можно было только на комплект из шести предметов.
Согласились почти все — проще перечислить регионы, которые не участвовали и решили проводить школьный этап самостоятельно (по убыванию численности населения): Московская область, Красноярский край, Вологодская область, Алтайский край, Омская область, Республика Крым, Пермский край, Пензенская область, Тверская область, Забайкальский край, Амурская область, Республика Марий Эл, Республика Карелия, Новгородская область, Республика Хакасия, Республика Ингушетия, Республика Алтай, Чукотский автономный округ, Ненецкий автономный округ. Я не включил в этот список Москву — хотя она и не "подписалась" на проект, но всё равно школьный этап по информатике для Москвы проводился по тем же заданиями и тем же правилам. На самом деле наоборот — правила и принципы составления задания были взяты московские, и московский формат проведения школьного этапа олимпиады по информатике был распространён на всю страну.
Всего вместе с Москвой участвовало свыше 80% регионов России (если считать по численности населения).
Все регионы были разбиты на четыре группы, примерно равной по численности населения, расположенные примерно в одних часовых поясах. Первая и вторая группы — это московский часовой пояс, третья группа — это MSK+1 и MSK+2, четвёртая группа — от MSK+4 до MSK+9. Тут я (и многие коллеги) впервые узнали, что в зоне MSK+3 находится всего лишь один регион — Омская область, которая не участвовала в проекте. Для каждой группы был установлен свой день проведения — с 26 по 29 октября.
Регион самостоятельно определял форму проведения школьного этапа: централизованно в школах или из дома. Логины для участия распространялись по школам через ФИС ОКО (федеральная информационная система оценки качества образования). Школам выдавались логины по числу учащихся +10% запаса. Регламент проведения олимпиады предусматривал возможность участия с 8 до 20 часов по местному времени, реально же возможность участия была от 8 утра в самом раннем регионе до 20 часов в самом позднем.
Авторы заданий
Задания разрабатывал большой коллектив авторов в четырёх рабочих группах. Огромная благодарность всем авторам за то, что они сделали четыре хороших комплекта заданий. Также отдельное спасибо MikeMirzayanov за систему полигон, которая использовалась для подготовки всех заданий, и помощь в решении технических вопросов,
Содержание заданий
Олимпиада проводилась для 5-11 классов по формату заданий, принятому в Москве в последние годы.
Для 9-11 классов предлагалось 5 задач по программированию на двухчасовой тур. Примерный план варианта — формула (целочисленная арифметика), задача на использование if, задача на цикл, задача на массив, идейная задача. Система оценивания — потестовая, все тесты независимые, хотя в условиях и выделяются подзадачи по ограничениям или частным случаям, но групп тестов и зависимостей между тестами нет. Тестирование производилось сразу после сдачи на всех тестах. Задачи доступны в тренировках: первая группа, вторая группа, третья группа, четвёртая группа.
Для 7-8 классов предлагался смешанный вариант. Статистика показывает, что лишь небольшая часть школьников 7-8 классов, участвующих в олимпиаде, умеет программировать (например, статистика этого школьного этапа — около 10% участников сдавало задачи по программированию), поэтому участникам предлагается 4 задачи с вводом ответа и 3 задачи по программированию. Задачи с вводом ответа — это по сути output-only задачи, которые, скорее всего, можно решить без использования компьютера (но не запрещается и его использование). Ответ на эти задачи нужно записать в поле ввода. Это похоже на формат олимпиад по математике в дистанционной форме, но, благодаря чекеру, можно выставлять произвольные баллы за решения, например, оценивать алгоритм для исполнителя по числу использованных команд. Об этом формате проведения олимпиады было опубликовано несколько статей. При этом считается, что 7 задач много для тура, а школьники могут выбирать понравившиеся задачи, поэтому оцениваются только 5 задач из 7 с наилучшим результатом. Продолжительность тура — 2 часа.
При этом сильные программирующие школьники 7-8 классов могли писать олимпиаду за 9 класс.
Для 5-6 классов предлагался вариант без программирования, только из 5 output-only задач. Продолжительность тура — 45 минут.
Условия задач, решения, архивы и видеоразборы опубликованы: группа 1, группа 2, группа 3, группа 4.
Тестирующая система
Тестирующая система должна удовлетворять ряду требований: держать несколько десятков тысяч пользователей одновременно, справляться с проверкой задач по программированию (в пиковые моменты использовалось порядка 40 инвокеров. Это на самом деле не очень много, т.к. при составлении задач было требование не делать много тестов, да и TL больше 1 секунды в задачах не было), поддерживать output-only задачи со сдачей ответа в поле ввода. И редкие системы удовлетворяют всем этим требованиям.
Для проведения дистанционных олимпиад по другим предметам Сириус использует собственную тестируюущую систему. Она специально была разработана для проведения подобных мероприятий, поэтому там довольно просто реализован механизм входа и регистрации (вместо пары логин-пароль используется один "ключ", затем нужно ввести фамилию-имя и можно переходить к олимпиаде) и умеет держать нужную нагрузку. В ней уже есть поддержка задач по программированию и проведены соревнования на несколько сотен участников, однако, на соревнованиях по программированию на тысячах участников система ещё не использовалась. Кроме того, поддержка output-only задач в настоящий момент не достигла нужного нам уровня, например, нет возможности выставлять в качестве оценки за решение произвольное число от 0 до 100. Поэтому от использования системы Сириуса пришлось отказаться, но я надеюсь, что в дальнейшем мы будем использовать её.
Codeforces хоть и умеет держать нужное количество пользователей (если считать число участников Div.3 раундов, которое превышает 20.000, что примерно нам и нужно), но совсем не поддерживает output-only задачи.
Яндекс-контест мы пробовали использовать в прошлом году в ходе пилотного проведения школьного этапа для нескольких регионов, с его помощью можно добиться желаемого формата проведения олимпиады, однако, это весьма неудобно делать. Например, ввод фамилии-имени участника при регистрации осуществлялся при помощи добавления в контест "нулевой" задачи, без сдачи которой нельзя перейти к следующим задачам, а это усложняет подведение результатов (нужно отдельно выгружать архив сабмитов, считывать его программно и сливать с таблицей результатов). Задачи вида output-only приходится проверять повторно после окончания тура с заменой чекера. Все массовые операции вида "создать пользователей", "выгрузить архив решений", "провести перетестирование" требуют привлечения поддержки и занимают очень много времени. Наконец, не было уверенности в том, что Яндекс.Контест сможет успешно поддерживать столько пользователей.
Поэтому использовался ejudge, который много лет использовался для проведения олимпиад в Москве. Отдельная благодарность автору ejudge Александру Чернову за систему и регулярные консультации.
Ejudge, разумеется, имеет ряд недостатков, связанных прежде всего с тем, что система разрабатывается более 20 лет и её архитектура соответствует взглядам 20-летней давности. При разработке ejudge просто не закладывалась идея, что в контесте могут быть десятки тысяч одновременных пользователей и сотни тысяч пользователей всего. Все пользовательские запросы, например, обрабатываются процессом ej-contests, который работает в один поток и никак не распараллеливается. Поэтому, кажется, предел возможностей ejudge — это около 4000 одновременных пользователей на мощном компьютере, при большем числе пользователей ej-contests уже не успевает обрабатывать запросы пользователей.
В ejudge плохо организована работа с базой пользователей, например, запуск контеста (и выполнение действия reload config files) влечёт считывание всей базы пользователей в память, что занимает ощутимое время и требует оперативной памяти для хранения ненужной базы пользователей.
Год назад в результате возникших проблем с добавлением пользователей в коде ejudge мною были найдены вшитые ограничения:
#define EJ_MAX_USER_ID 999999
#define MAX_USER_ID_32DIGITS 4
Последняя строчка ограничивает размер поля для хранения USER_ID 20 битами. При этом для проведения школьного этапа в этом году было сгенерировано порядка 10 миллионов логинов в систему. В принципе, можно с этими ограничениями справиться, но для этого, например, понадобится перекомпиляция ejudge.
Зато система ejudge проверена и предсказуема. Известно, что один сервер ejudge может держать 3000 одновременных пользователей, и распределить нагрузку можно созданием отдельных серверов так, чтобы на каждый из них приходилось не более 3.000 одновременных пользователей (и около 15.000 пользователей за день проведения тура).
Поэтому для проведения олимпиады использовалось несколько независимых серверов так, чтобы ожидаемое максимальное число пользователей составляло порядка 2000 на одном сервере. Каждая из четырёх групп регионов разбивалась на подгруппы по ожидаемому числу участников: первая и третья группы были разбиты на две подгруппы, вторая группа — на три подгруппы, четвёртую восточную группу разбивать не пришлось. Итого получилось 8 подгрупп и 24 сервера (для групп классов также использовались отдельные сервера), плюс 3 сервера для Москвы. Но для проведения туров одновременно использовались только сервера одной группы, то есть при проведении школьного этапа для второй группы + Москвы было задействовано 12 одновременно работающих фронтенд-серверов.
Все сервера находятся в облаке AWS, благодаря чему процесс клонирования серверов довольно прост.
Таким образом, для участия в олимпиаде школьник должен иметь помимо логина и пароля ещё и ссылку на вход в тестирующую систему, которая разная для разных серверов. Для этого мы в последние годы используем сервис сокращения ссылок to.click, которому мы благодарны за поддержку и всяческую помощь.
Проблемы
К сожалению, провести олимпиаду "идеально" не получилось, хотя итог оказался лучше "пессимистичного" сценария. Проблем с тестирующей системой не было, но, к сожалению, отбиться от DDOS-атак без потерь не удалось.
Проблемы с серьёзными DDOS-атаками в последние годы возникали у организаторов школьного этапа в Московской области, я же некоторое время считал, что лучший способ защиты от DDOS-атак — это просто хранить в секрете адреса серверов, не публикуя ссылки на вход в тестирующую систему в открытом доступе. Но при увеличении масштаба мероприятия этот метод перестал работать. Впервые c DDOS-атакой при проведении школьного этапа мы столкнулись год назад, тогда без видимых причин выросла нагрузка на CPU и сеть на одном из серверов и происходило ощутимое замедление отклика сервера (это было год назад на московском сервере для олимпиады 9-11 классов), но точно идентифицировать атаку по логам не удалось.
На этот раз первая DDOS-атака началась 27 октября в 20:00. В это время заканчивался тур для Москвы, поскольку для регионов проведение тура по регламенту до 20:00. Атака заключалась в загрузке страницы входа в систему, в минуту число запросов доходило до 2 миллионов. По примеру Московской области, сервера тестирующей системы находились за Cloudflare, который распознал атаку и успешно блокировал запросы, т.е. тестирующая система продолжала работать. Но часть участников (по-видимому, те участники, у которых массово совпадали IP-адреса) также были "распознаны" Cloudflare, как атака, и им тоже был заблокирован доступ в тестирующую систему. То есть Cloudflare начал "спасать" тестирующую систему от DDOS-атаки, блокируя доступ к тестирующим серверам не только атакующим, но и некоторым участникам. Такое поведение CloudFlare oказалось сюрпризом.
Вторая DDOS-атака случилась 28 октября, когда шли туры для третьей группы регионов, в 13:13 по московскому времени (если "автор" этой атаки читает этот пост, то да, мы "оценили" его шутку). Она была гораздо более длительной и продолжалась свыше 5 часов. Кажется, что вторая атака не связана с первой — первая была направлена на московский сервер, здесь атака шла на сервер для регионов. Но сценарий оказался таким же — Cloudflare начал блокировать атаку и часть участников. По моим оценкам, трудности доступа к тестирующей системе из-за блокировки Cloudflare возникли у 30% участников олимпиады, для остальных же тур продолжался, т.к. с самой тестирующей системой проблем не было.
Примерно через 1 час 10 минут после начала атаки удалось разобраться с настройками Cloudflare, и вместо блокировки атакующих была включена капча, т.е. все заблокированные участники могли добраться до тестирующей системы при помощи ввода капчи. После этого атака продолжалась ещё более 4 часов, но никаких затруднений (помимо ввода капчи) у участников уже не было. Для компенсации трудностей тур был продлён до ночи, а участникам, которые не смогли сдать решения, предлагалось сделать это повторно под новым логином.
Списывания
При таком формате проведения олимпиады задания сливаются в интернет в течение первого часа, а вскоре появляются и их решения. Главный вред этого в том, что большое число копи-пастеров вытесняют из верхней части таблицы результатов честных участников и не дают им возможности пройти на муниципальный этап, поскольку число участников муниципального этапа ограничено. Возникает необходимость в очистке результатов от "мусорных" участников. Но стандартные алгоритмы, которые используются на подобных соревнованиях (предполагающие попарное сравнение подозрительных решений членом жюри), здесь не сработают, потому что решений и списываний очень много, сравнивать попарно решения нет никакой возможности. Да и сценарий списываний тут другой — есть некоторое количество решений, которые были слиты в интернет, и участники сдавали эти решения, как правило, без каких либо модификаций. Хотя несущественные модификации возникают, например, при копи-пасте решений появляются лишние пустые строки (между двумя строками кода есть одна пустая строка, что сразу бросается в глаза). Другой типичный пример списывания: на одном популярном сайте примеры кода верстаются в виде таблицы, где в левом столбце — номера строк, а в правом столбце — код. При копировании решений с этого сайта участники зачастую копируют и номера строк из левого столбца, получается такая программа:
1
2
3
4
5
6
7
N = int(input())
K = int(input())
if 1 <= N <= 10 ** 4:
if (1 <= K <= N) and ((N % K) == 0):
print(2 * N * (N // K - 1))
else:
print(0)
Но этот код является корректным кодом на Python и набирает столько же баллов!
Поэтому проверка на списывание проводится по другой методике, цель которой — выкинуть решения, явно скопированные из интернета. Проверка весьма поверхностная, не ловит какие-либо существенные модификации кода, но в этом и нет нужды, потому что большинство списывальщиков просто делают копи-паст найденного решения, и очистка таблицы от этого мусора уже даёт результат. Например, в одном из регионов после проведения такой очистки число участников, набравших балл, примерно соответствующий прохождению на муниципальный этап, сократилось в 4 раза.
Печальная статистика заключается в том, что в целом по стране среди участников 9-11 классов, которые набрали больше 0 баллов, минимум 58% использовало чужие решения (это только то, что удалось найти поверхностной проверкой). Доля "списывальщиков" разнится от региона к региону, в отдельных регионах доходя до 90% участников.
В целом есть два довольно банальных наблюдения: в тех регионах, где участники писали в школах (а не из дома), доля списывания ниже. В тех регионах, где число участников выше среднего, т.е. было искусственное повышение числа участников, доля списывания выше (если пригнать на олимпиаду не желающих в ней участвовать школьников, то они либо ничего не сдадут, либо спишут).
Статистика
Обычно мы считаем количество ненулевых пользователей, т.к. много участников вообще ничего не сдают, и довольно много участников сдают явно не-решения (от текста "я не знаю" до копи-паста условий или стихов Пушкина). Поэтому статистика по числу ненулевых участников более точно отражает интерес к олимпиаде.
Всего участников 5-6 классов: 106311
Ненулевых участников 5-6 классов: 74195
Всего участников 7-8 классов: 132682
Ненулевых участников 7-8 классов: 86166
Число участников 9-11 классов: 153267
Ненулевых участников 9-11 классов: 49097
Невысокое число ненулевых участников в 9-11 классах объясняется проведённой проверкой на списывание.
Публикую два файла со статистикой (нажмите на кнопку "Скачать" вверху страницы после перехода по ссылке).
Число участников по регионам в каждой группе. Здесь также считаются только ненулевые участники. Также там посчитана доля участников в 7-8 классах, которые умеют программировать (набрали больше нуля на задачах по программированию).
Статистика по используемым языкам программирования. Учитывается только 9-11 класс, после проверки на списывание. Считается, что участник использовал язык программирования, если набрал больше 0 баллов, сдавая решения на этом языке. А по Москве я веду статистику используемых языков программирования на разных этапах начиная с 2011 года.
