Меня зовут Абай Баймуканов, я – разработчик-алгоритмист. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.
Быть олимпиадником по спортивному программированию довольно весело и интересно. Но быть жюри и составителем задач для самих олимпиад – достаточно ответственное и не менее интересное дело. Спортивное программирование - это те же математические задачки на логику, которые всего то нужно решить. Но программирование, в отличие от любого другого предмета, уникально тем, что решение нужно еще и реализовать в виде компьютерной программы.
Здесь есть свой нюанс: программа может работать настолько долго, сколько не существует даже вселенная, а может сработать за долю секунды. Причем в обоих случаях результат будет один и тот же. Любой олимпиадник стремится к тому, чтобы его программа была как можно эффективнее. Для этого существуют алгоритмы и структуры данных - методы, позволяющие сделать определенные программы более эффективными с точки зрения необходимого времени или памяти компьютера.
Спектр сложности у задач по спортивному программированию достаточно широкий: от задач для новичков до задач мирового уровня для вундеркиндов. Большинство соревнований проводится практически в одном и том же формате, то есть дается несколько задач, 5 часов на их решение и нужно решить как можно больше за это время.
На школьных олимпиадах обычно за каждую задачу можно получить от 0 до 100 баллов и общим результатом будет суммарный балл за все задачи, у студентов же в результат идет просто количество решенных задач, а если есть участники, решившие одно и то же количество задач, то они располагаются по убыванию штрафа. Чем дольше решаешь задачу или чем больше попыток тратишь на нее, тем больше штрафа за нее получишь.
Обычно любая олимпиада проводится вживую, то есть она проходит на специально организованной площадке, оснащенной компьютерами. Когда в 2020 году началась пандемия коронавируса, многие олимпиады перевели в онлайн-формат, то есть участвовать в них можно из дома, сидя за своим компьютером. Для того, чтобы результаты были честными, нужно соблюдать прокторинг: участники должны записывать себя на камеру на протяжении всей олимпиады, записывать экран своего компьютера вместе со звуком. Потом эти записи проверяет жюри олимпиады и в случае выявления каких-то нарушений участника могут дисквалифицировать.
Кроме организации площадки для участия критически важной частью при организации такой олимпиады является составление набора задач (контеста). В частности, если олимпиада высокого уровня, то и задачи должны быть сложными и в то же время оригинальными. Для составления такого набора задач нужна специальная команда из нескольких ребят, которые в основном являются теми же олимпиадники, чаще всего студентами. Придумывать такие задачи - достаточно сложный процесс и зачастую авторы накапливают их «по ходу жизни», пока сами участвуют на олимпиадах или учебных сборах.
Помимо этого набор задач должен быть сбалансирован. Нельзя чтобы абсолютно весь контест был слишком сложным или легким, потому что это пагубно повлияет на итоговые результаты олимпиады.
После того, как подобран набор задач, остается техническая часть, эти задачи надо сделать. Дело в том, что решения к задачам пишутся не на бумаге, как например, в математике. Олимпиада проводится в системе за компьютером, и когда участник хочет сделать очередную попытку по какой-либо задаче, он отправляет код программы в систему, которая выполнит проверку и сразу же выдаст результат. Поэтому при подготовке любой задачи нужно, во-первых, написать ее условие, во-вторых, подготовить к ней набор из нескольких тестов (чаще всего их около 50). Если программа проходит все тесты, то она считается правильной.
Каждый из тестов является конкретным примером, который соответствует условию задачи. Это значит, что программа должна работать в общем виде. Например, в геометрии условие задачи обычно такое: дан треугольник со сторонами 3, 4 и 5 см, найдите его площадь. То есть даются какие-то конкретные числа. А в программировании условие будет звучать так: дан треугольник со сторонами A, B и C см, найдите его площадь. То есть нужно придумать решение, работающее для любых значений A, B и C.
А чтобы не противоречить здравому смыслу в условии будет гарантироваться, что A, B и C будут положительными числами, потому что не бывает треугольников со стороной 0 или меньше см. В тестах будут уже какие-то конкретные значения для A, B и C. В идеале хотелось бы сделать набор со всевозможными тестами, тогда можно быть уверенным на все 100% что программа верна, если прошла все эти тесты.
Однако почти всегда всевозможных тестов может быть слишком много, в текущем примере в том числе. Столько тестов невозможно будет сохранить даже на всех существующих компьютерах по всему миру. А даже если и возможно, то проверка может занять несколько лет, что очевидно не подходит. Проверка должна занимать от силы пару минут, поэтому даже в тестировании все должно быть эффективно. Из-за этого набор тестов ограничивается по размеру, и, как следствие, встает вопрос о качестве тестов.
Вполне возможно сделать набор таким, что неправильная программа пройдет все тесты, но тем не менее она все еще неправильная. Поэтому на составителе задач лежит огромная ответственность. Чтобы проверить тесты на прочность, задачу решают те же ребята составители, иногда для этого привлекают других ребят, если сложность задач достаточно высокая.
Если все одобрят, задачу добавляют в систему. Составлять задачи непросто, поэтому важным фактором выступает профессиональность автора: чем он сильнее как олимпиадник, тем больше вероятность того, что он не допустит ошибок при составлении задачи в системе. Когда контест готов, можно проводить олимпиаду.
Во время нее авторы задач превращаются в дежурных и следят за тем, чтобы контест шел безо всяких проблем. Участникам разрешается задавать вопросы в системе, авторы будут на них отвечать. Помимо вопросов участники могут сообщать о любых технических проблемах, либо о проблемах с задачами (ошибка в условии, какая-то ошибка в тестах и прочее). Важно ответить на эти вопросы оперативно, т.к. это влияет на итоговые результаты отрицательным образом. Также авторы с большим интересом следят за текущими результатами. Обычно на школьных олимпиадах участникам не доступна таблица результатов во время олимпиады.
Комментарии (20)
anonymous
00.00.0000 00:00
qw1
20.03.2022 12:53+7Всегда волновал вопрос — какой во всем этом смысл?
В том, чтобы самому научиться писать алгоритмы. То есть, если есть амбиции пойти в FAANG или начать стартап. Для рутинных бизнес-задач можно взять готовую библиотеку, а если её нет, сказать руководству: задача мне не по силам, ищите «сеньора».это даже не притянуть к «зато будет лучше работать», потому что мудреные, но страсть какие эффективные, решения оценят с меньшей вероятностью, чем простые и понятные
В реальности может быть так, что возможно только эффективное решение, а простое и понятное (например, полный перебор вариантов) не потянет по ресурсам. Либо без математической подготовки вообще не известно, как это решать (например, если отбросить всю предметную шелуху, задача вырождается в составление расписания, в поиск максимального потока на графе или в задачу коммивояджера. Олимпиады прокачивают способность видеть математическую суть за словесными формулировками из «реального мира»)
dimskiy
20.03.2022 13:48+3Чтобы начать стартап, вам в последнюю очередь пригодятся алгоритмы ;)
Еще любопытно, что простые и понятные решения вы отнесли к крайностям вроде полного перебора. В любом случае, кроме абстрактных «прокачиваний математической составляющей» так и не услышал ничего конкретного. Само по себе прокачивание математики не даст вам примерно ничего в отрыве от предметной области.
aamonster
20.03.2022 14:20Умение работать с абстракциями (привет математике) помогает нормально моделировать предметную область.
qw1
20.03.2022 14:49+2Верно, про стартап это скорее относится не к основателю, а к тому, кто потянет реализацию.
Тут ещё важно не сколько «прокачивание математики», сколько практика реализации алгоритмов. Когда тыщу раз написал обход в глубину и ширину, рекурсивный и нет, это становится не какой-то магией, а просто рутиной. Когда нужно написать такое в проде, уже видишь заранее все возможные варианты и осознанно выбираешь: тут можно тупо рекурсией, потому что нагрузка небольшая, и кода меньше писать, а тут надо бы очередь организовать.
Также спортивное программирование приучает не делать глупые ошибки, типа неучтения крайних случаев (на это всегда есть коварные тесты) или забытой (-1) в индексах, которые в проде может быть запросто прощены и вылезти редкими неуловимыми багами. Причём обучение имеет сильное эмоциональное подкрепление (ааа, из-за такой ерунды не взял первое место), а потому хорошо запоминается.
Для самого программиста это в принципе ничего не даёт, в работе баги и неоптимальные алгоритмы прощаются и на з/п я думаю не сильно это отразится. Но для работодателя спортивный программист намного привлекательнее, чем человек без такого опыта, поэтому при большом выборе (яндексы/фейсбуки) берут только спортсменов.
Biga
20.03.2022 15:59+3Кому как, мне вот иногда по работе приходится решать задачки, близкие к олимпиадному уровню (хотя сравнивать могу только с городскими олимпиадами). Как только надо оптимизировать какой-то слишком затратный алгоритм, так сразу здравствуй динамическое программирование, хитрые структуры данных, математические ухищрения, кэширование и всё прочее. Некоторым вещам я научился именно на олимпиадах, не говоря уже о том, сколько полезного я вынес с тамошних компов на дискетках. =)
lalkatopkekla
20.03.2022 18:15Есть предмет на курсе "Информатика и программная инженерия", который называется "Алгоритмы и структуры данных". Всё, больше ничего. Культ олимпиад это только в СНГ. Во всём мире на него пофигу. Хочешь идешь на олимпиады, не хочешь не идешь. Олимпиады это показатель того, что ты можешь быстро находить неочевидные последовательности в данных. А не крудашлёпить по указке на Котлине под Андроид с открытой документацией? Ведь так, Vadim Sinitskiy? Крудашлепишь под Андроид на Котлине фронтендик?
alexdevyatov
20.03.2022 18:30+3Какой смысл в любом спорте? В получении удовольствия и удовлетворении желания соревноваться. Вот и здесь то же самое.
В качестве побочных эффектов: приобщение школьников к программированию, геймификация процесса изучения фундаментальных алгоритмов, приучение к обработке крайних случаев, развитие математического и логического аппарата.
Многие мои знакомые стали программистами благодаря олимпиадам, я и сам люблю порешать задачки на codeforces после работы.
mbait
21.03.2022 02:17+2Практического смысла столько же, сколько в шахматах, стрельбе из лука или биатлоне - это просто спорт, соревнования. Побочный эффект - набивается рука на написание решение алгоритмических задач, которые в прикладном программировании тоже иногда встречаются. Можете рассматривать алгоритмические задачи как музыкальные этюды - никто не играет их на концертах, но зато они помогают улучшить технику.
ganqqwerty
20.03.2022 09:06-1А бывают олимпиады по программированию, где существенную роль в итоговой оценке играет код-ревью живыми людьми? Некрасиво назвал переменные, сделал кучу дублирующегося кода, твой алгоритм неизящен, а код непонятен -- и с тебя снимается не меньше очков, чем если бы код работал медленно или некорректно?
FiddyNun
20.03.2022 11:54Topcoder регулярно проводят (или проводили раньше) контесты по самым разным задам, связанным с разработкой, от построения архитектуры системы до багфиксов в существующем коде. Победитель, соответственно, получает некоторое денежное вознаграждение. По сути, эдакий соревновательный фриланс.
dimskiy
Всегда волновал вопрос - какой во всем этом смысл? Если взять в пример все эти школьные олимпиады и их вариации, то все в результате сводится к «красному» аттестату/диплому. Ценности от которого в реальной жизни не больше чем от зеленого/синего :)
В случае с программированием это даже не притянуть к «зато будет лучше работать», потому что мудреные, но страсть какие эффективные, решения оценят с меньшей вероятностью, чем простые и понятные
Semigradsky
Различные льготы при поступлении. Даже 100 баллов за предмет очень приятно, а иногда это и автоматическое поступление без вступительных экзаменов.
aamonster
Разгон мозга: умение и привычка входить в поток. На рутинных задачах этого добиться гораздо труднее.
unsignedchar
Как и в олимпиаде по математике, например. Умение быстро найти решение определенного.вида задач.
dimskiy
Это как умение быстро переворачивать слова в голове. Что это вам даст на практике-то? ))) если вы не работаете в NASA над полетом на Марс, то вряд ли вы каждый день будете решать мат. задачи, да еще и на скорость
unsignedchar
Пожалуй, биологию в школе тоже зря учат. И физику с математикой. (Это доведение до абсурда ;))
Если человек умеет в абстракцию - это можно использовать не только в NASA.
Sergeant101
Скорее всего это просто сито: суперскилы пригодятся одному из ста тысяч, продвинутые десяти, обычные - сотне школьников, для остальных - просто забава.
Но эти несколько скилованных человек что выйдут из сотни тысяч в современном мире нужны как Илон Маск космонавтике.
Это хоть к математике отнеси, хоть к физике, хоть к программированию.
tzlom
Как и в любой олимпиаде - пооднять своё ЧСВ