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