Меня зовут Абай Баймуканов, я – разработчик-алгоритмист. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.
Быть олимпиадником по спортивному программированию довольно весело и интересно. Но быть жюри и составителем задач для самих олимпиад – достаточно ответственное и не менее интересное дело. Спортивное программирование - это те же математические задачки на логику, которые всего то нужно решить. Но программирование, в отличие от любого другого предмета, уникально тем, что решение нужно еще и реализовать в виде компьютерной программы.
Здесь есть свой нюанс: программа может работать настолько долго, сколько не существует даже вселенная, а может сработать за долю секунды. Причем в обоих случаях результат будет один и тот же. Любой олимпиадник стремится к тому, чтобы его программа была как можно эффективнее. Для этого существуют алгоритмы и структуры данных - методы, позволяющие сделать определенные программы более эффективными с точки зрения необходимого времени или памяти компьютера.
Спектр сложности у задач по спортивному программированию достаточно широкий: от задач для новичков до задач мирового уровня для вундеркиндов. Большинство соревнований проводится практически одном и том же формате, то есть дается несколько задач, на их решение 5 часов и за это время нужно решить как можно больше.
На школьных олимпиадах обычно за каждую задачу можно получить от 0 до 100 баллов и общим результатом будет суммарный балл за все задачи, у студентов в результат идет просто количество решенных задач, а если есть участники, решившие одно и то же количество задач, то они группируют по убыванию штрафа. Чем дольше решаешь задачу или чем больше на них нужно попыток решить, тем больше штрафов за нее получишь.
Обычно любая олимпиада проводится вживую, то есть она проходит на специально организованной площадке, оснащенной компьютерами. Когда в 2020 году началась пандемия коронавируса, многие олимпиады перевели в онлайн-формат, то есть участвовать в них можно участвовать из дома, сидя за своим компьютером. Для того, чтобы результаты были честными, нужно соблюдать прокторинг: участники должны записывать себя на камеру на протяжении всей олимпиады, записывать экран своего компьютера вместе со звуком. Потом эти записи проверяет жюри олимпиады и в случае выявления каких-то нарушений участника могут дисквалифицировать.
Кроме организации площадки для участия критически важной частью при организации такой олимпиады является составление набора задач (контеста). В частности, если олимпиада высокого уровня, то и задачи должны быть сложными и в то же время оригинальными. Для составления такого набора задач нужна специальная команда из нескольких ребят, которые в основном являются теми же олимпиадники, чаще всего студентами. Придумывать такие задачи - достаточно сложный процесс и зачастую авторы накапливают их «по ходу жизни», пока сами участвуют на олимпиадах или учебных сборах.
Помимо этого набор задач должен быть сбалансирован. Нельзя чтобы абсолютно весь контест был слишком сложным или легким, потому что это пагубно повлияет на итоговые результаты олимпиады.
После того, как подобран набор задач, остается техническая часть, эти задачи надо сделать. Дело в том, что решения к задачам пишутся не на бумаге, как например, в математике. Олимпиада проводится в системе за компьютером, и когда участник хочет сделать очередную попытку по какой-либо задаче, он отправляет код программы в систему, которая выполнит проверку и сразу же выдаст результат. Поэтому при подготовке любой задачи нужно, во-первых, написать ее условие, во-вторых, подготовить к ней набор из нескольких тестов (чаще всего их около 50). Если программа проходит все тесты, то она считается правильной.
Каждый из тестов является конкретным примером, который соответствует условию задачи. Это значит, что программа должна работать в общем виде. Например, в геометрии условие задачи обычно такое: дан треугольник со сторонами 3, 4 и 5 см, найдите его площадь. То есть даются какие-то конкретные числа. А в программировании условие будет звучать так: дан треугольник со сторонами A, B и C см, найдите его площадь. То есть нужно придумать решение, работающее для любых значений A, B и C.
А чтобы не противоречить здравому смыслу в условии будет гарантироваться, что A, B и C будут положительными числами, потому что не бывает треугольников со стороной 0 или меньше см. В тестах будут уже какие-то конкретные значения для A, B и C. В идеале хотелось бы сделать набор со всевозможными тестами, тогда можно быть уверенным на все 100% что программа верна, если прошла все эти тесты.
Однако почти всегда всевозможных тестов может быть слишком много, в текущем примере в том числе. Столько тестов невозможно будет сохранить даже на всех существующих компьютерах по всему миру. А даже если и возможно, то проверка может занять несколько лет, что очевидно не подходит. Проверка должна занимать от силы пару минут, поэтому даже в тестировании все должно быть эффективно. Из-за этого набор тестов ограничивается по размеру, и, как следствие, встает вопрос о качестве тестов.
Вполне возможно сделать набор таким, что неправильная программа пройдет все тесты, но тем не менее она все еще неправильная. Поэтому на составителе задач лежит огромная ответственность. Чтобы проверить тесты на прочность, задачу решают те же ребята составители, иногда для этого привлекают других ребят, если сложность задач достаточно высокая.
Если все одобрят, задачу добавляют в систему. Составлять задачи непросто, поэтому важным фактором выступает профессиональность автора: чем он сильнее как олимпиадник, тем больше вероятность того, что он не допустит ошибок при составлении задачи в системе. Когда контест готов, можно проводить олимпиаду.
Во время нее авторы задач превращаются в дежурных и следят за тем, чтобы контест шел безо всяких проблем. Участникам разрешается задавать вопросы в системе, авторы будут на них отвечать. Помимо вопросов участники могут сообщать о любых технических проблемах, либо о проблемах с задачами (ошибка в условии, какая-то ошибка в тестах и прочее). Важно ответить на эти вопросы оперативно, т.к. это влияет на итоговые результаты отрицательным образом. Также авторы с большим интересом следят за текущими результатами. Обычно на школьных олимпиадах участникам не доступна таблица результатов во время олимпиады.
Автор:
MrLeMans
