Следующий год будет моим пятым и последним сезоном в ACM-олимпиадах. За эти годы накопилось много разных воспоминаний и знаний об олимпиадах, благо мой университет участвует в них весьма активно. Рассказывать только со стороны участника будет не совсем правильным, поскольку поучаствовать в олимпиадах могут многие, мне же довелось и быть в составе жюри (правда, школьных олимпиад). Расскажу немного интересных вещей изнутри, приоткрою чуть-чуть наше закулисье. Рассказ будет тесно связан с Открытой Всесибирской олимпиадой, поскольку с ней у меня общение самое тесное (да и проводится она нашим университетом).
Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.
В первой статье я хочу рассказать о составлении задач к этим олимпиадам. Дело увлекательное, творческое, но порой весьма муторное.
Года 2-3 я пишу задачи для школьных олимпиад разного уровня. До студенческих я ещё не добрался, поскольку самому ещё вполне играется и поучаствовать хочется самому (хотя, как помню, одну мою задачу взяли-таки на личную олимпиаду НГУ; в личках я участвую редко).
Недели за 3 до проведения какой-либо школьной олимпиады наши тренеры собирают «старичков» — первые 4 команды НГУ — в закрытом помещении и озадачивают. Ставится задача наковырять 10-12 задач, из которых набираются на тур где-нибудь 8.
Сначала накидываются сырые идеи. Во-первых, не должно быть уклона в какую-либо область олимпиадного программирования, это на тренировках хорошо — или целый день на геометрии тренироваться, или прорабатывать динамику. В готовых олимпиадах должно быть всего более-менее поровну. Одна-две задачки на графы, почти обязательно — одна геометрия, что-нибудь по комбинаторике. Иногда простенький тервер (школьники ведь, пожалеть надо). Пара задач на динамическое программирование, одна на обработку строк, а самое главное — одна «утешалка». Во-вторых, нужно выдержать общий уровень олимпиады. Если цель — отбор на олимпиаду следующего уровня, то не следует увлекаться сложными задачами; если же проходит финал турнира, то можно проявить и небольшую дольку садизма, выпустив 1-2 откровенных гроба с целью отделить просто хороших кодеров от реальных топов.
Так вот, у мозгового центра есть всегда в загашнике пара идей у каждого. Высказывают, записывают, распределяют. В итоге и получается те самые 10-12 задач, некоторые из которых отсеиваются по ходу пьесы (из-за сложности/неудачности/повторизма).
Каждая задача достаётся паре людей, желательно — из разных команд. Дальше, каждому из них достаётся по 2-3 задания из списка:
Условие обычно пишет сам автор идеи задачи. Обычно, но не всегда. Если у автора нелады с письменным творчеством/язык не подвешен, то при подготовке в ходу техскелет условия, а к собственно олимпиаде его олитературивают. Самое главное — чтобы и тренеры, и напарник по задаче сумели осознать, что требуется при решении и как это делать. Бывают, конечно, и казусы. Условие может быть специально накрученным, запутанным и неудобоваримым, а решение — простым и быстрым. Поэтому у нашей команды в ходу метод чтения задачи снизу вверх. Сначала смотрится формат входных/выходных данных, затем ограничения по времени выполнения и свободной памяти. Если после этого волосы не встают дыбом, то можно браться за решение. Но о турах чуть позже, сейчас у нас только подготовка.
Условия бывают разные. Бывают строго математические (как, например, задачи Шилова на Всесибах — почти всегда есть задача от него на парсер какого-нибудь языка, заданного формально). Бывают строго юмористические (так, например, нашу команду, состоявшую из ярых футбольных болельщиков, минут на 5 вывела из строя задача про футболиста Владислава Буланова и хозяина команды Гарольда Ивановича Нерра). Главное — не переборщить ни с тем, ни с другим. Квинтэссенцией условий, по-моему, является идея Миши Калугина поручить написание задачи на сложение двух чисел профессиональному психоаналитику, с неотлагаемым развитием у прочитавшего боязни замкнутых пространств, открытых пространств, языка Java и числа 13.
Ладно, по условиям хватит. Теперь насчёт решений. Решение в обязательном порядке пишет и автор задачи, и его помощник. Желательно — на разных языках (в случае школьных олимпиад: c++/pascal, для студенческих: c++/java). Тесты обычно пишет не автор задачи. Зачем это делается? Дело в том, что при составлении задачи целиком одним человеком могут быть не затронуты какие-либо тонкости, упущены крайние случаи, да и вообще — выбран неоптимальный способ решения. Когда же решение написано двумя более-менее знающими человеками независимо, оно с гораздо большей вероятностью оказывается правильным.
В процессе написания решений зачастую меняется условия задачи. Ограничения — так те тысячу раз меняются, с целью либо прохождения, либо непрохождения определённых решений. Если разрешена Java — то могут лимиты по времени/памяти увеличить. Иногда внезапно находится дыра в условии либо контрпример, валящий одно из решений. В итоге, в процессе взаимодействий возникают 2 решения, они же — пресловутые «решения жюри», непогрешимые и непокобелимые =).
Тут всё более-менее понятно. Чекер пишется в том случае, если задача имеет более, чем одно решение и требуется вывести лишь одно произвольное возможное. В таком случае пишется программка, которая по входным и выходным данным проверяет оптимальность. Иначе же, если правильное решение только одно, проверка полностью отдаётся на откуп тестирующей системе. С авторов — только наборы входных и выходных тестов.
Теперь о тестах. Тут делится на две категории. Если олимпиада проводится по правилам ACM, то душа отрывается. В таком случае зачёт проходит лишь та задача, которая проходит абсолютно все тесты и написана с предполагаемой авторами оптимальной асимптотикой от размера входных данных. С поправочной константой в районе 2-3, ведь на написание решения жюри у автора 2-3 спокойные недели, а олимпионикам предлагается в диком кипише написать 10 решений за 5 часов. Пишутся тесты на граничные значения (проверить, что будет при минимальных значениях входных данных — зачастую многие упускают из виду случаи с нулевыми входными данными). Пишутся макстесты — на них часто сыплются неоптимальные решения либо решения, где писавшие неаккуратно обращались с массивами (о да, всегда десяток лишних элементов добавляю). В случае геометрии — пишутся тесты, на которых режутся ребята, состоящие во вражде с точностью и эпсилонами. Пишутся случайные тесты, если надо много — то генератор тестов. А если лень — пишется шоу.
Немного оффтопика:
В бытность второкурсниками мы с моим постоянным напарником и хорошим другом Мишей Городиловым составляли тесты на простенькую задачу. Вход — одно число до 10^18, выход — два числа. Писать генератор случайных чисел не хотелось. В итоге: в тестах жюри были и наши номера телефонов, и штрихкоды с банки кофе и бутылки кока-колы, и даже, под конец, результат двух ударов головой по клавиатуре. Для нас это тогда было быстрее, чем написать генератор
Так вот, а с школьными олимпиадами дело обстоит несколько иначе. Как уже говорилось в комментариях к недавнему топику, там другая система оценивания. Баллы начисляются за число пройденных тестов. Все прошёл — 100, только входной либо ни одного — 0. А между ними — всё наше буйство фантазии. Сначала продумывается ограничения на полнопереборное решение. Туда отправляются 3-4 теста на баллов 15-20. Чтобы не было обидно. Дальше продумываются возможные неидеальные варианты и асимптотики. Алгоритм работает за O(N^3) — вот ему смертельная пилюля. За O(N^2) — вот и ему. За O(NlogN) — хорошо. Вот ему макстест и если константа асимптотики хорошая, то будет 100 баллов. С геометриями, опять же, отсечку проходят на сложных тестах, где нужна повышенная точность. Ну и в этом случае пару набору входных/выходных данных составляет разбалловка.
Вроде всё. Условия написаны, решения есть, осталось загрузить всё в тестирующую систему и сделать взмах клетчатым флагом. Но об этом — в следующих статьях.
Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.
В первой статье я хочу рассказать о составлении задач к этим олимпиадам. Дело увлекательное, творческое, но порой весьма муторное.
Года 2-3 я пишу задачи для школьных олимпиад разного уровня. До студенческих я ещё не добрался, поскольку самому ещё вполне играется и поучаствовать хочется самому (хотя, как помню, одну мою задачу взяли-таки на личную олимпиаду НГУ; в личках я участвую редко).
С чего всё начинается
Недели за 3 до проведения какой-либо школьной олимпиады наши тренеры собирают «старичков» — первые 4 команды НГУ — в закрытом помещении и озадачивают. Ставится задача наковырять 10-12 задач, из которых набираются на тур где-нибудь 8.
Сначала накидываются сырые идеи. Во-первых, не должно быть уклона в какую-либо область олимпиадного программирования, это на тренировках хорошо — или целый день на геометрии тренироваться, или прорабатывать динамику. В готовых олимпиадах должно быть всего более-менее поровну. Одна-две задачки на графы, почти обязательно — одна геометрия, что-нибудь по комбинаторике. Иногда простенький тервер (школьники ведь, пожалеть надо). Пара задач на динамическое программирование, одна на обработку строк, а самое главное — одна «утешалка». Во-вторых, нужно выдержать общий уровень олимпиады. Если цель — отбор на олимпиаду следующего уровня, то не следует увлекаться сложными задачами; если же проходит финал турнира, то можно проявить и небольшую дольку садизма, выпустив 1-2 откровенных гроба с целью отделить просто хороших кодеров от реальных топов.
Так вот, у мозгового центра есть всегда в загашнике пара идей у каждого. Высказывают, записывают, распределяют. В итоге и получается те самые 10-12 задач, некоторые из которых отсеиваются по ходу пьесы (из-за сложности/неудачности/повторизма).
Что дальше делают с идеями?
Каждая задача достаётся паре людей, желательно — из разных команд. Дальше, каждому из них достаётся по 2-3 задания из списка:
- условие задачи;
- решение задачи;
- тесты для задачи;
- чекер (опционально от вида задачи)
Условия
Условие обычно пишет сам автор идеи задачи. Обычно, но не всегда. Если у автора нелады с письменным творчеством/язык не подвешен, то при подготовке в ходу техскелет условия, а к собственно олимпиаде его олитературивают. Самое главное — чтобы и тренеры, и напарник по задаче сумели осознать, что требуется при решении и как это делать. Бывают, конечно, и казусы. Условие может быть специально накрученным, запутанным и неудобоваримым, а решение — простым и быстрым. Поэтому у нашей команды в ходу метод чтения задачи снизу вверх. Сначала смотрится формат входных/выходных данных, затем ограничения по времени выполнения и свободной памяти. Если после этого волосы не встают дыбом, то можно браться за решение. Но о турах чуть позже, сейчас у нас только подготовка.
Условия бывают разные. Бывают строго математические (как, например, задачи Шилова на Всесибах — почти всегда есть задача от него на парсер какого-нибудь языка, заданного формально). Бывают строго юмористические (так, например, нашу команду, состоявшую из ярых футбольных болельщиков, минут на 5 вывела из строя задача про футболиста Владислава Буланова и хозяина команды Гарольда Ивановича Нерра). Главное — не переборщить ни с тем, ни с другим. Квинтэссенцией условий, по-моему, является идея Миши Калугина поручить написание задачи на сложение двух чисел профессиональному психоаналитику, с неотлагаемым развитием у прочитавшего боязни замкнутых пространств, открытых пространств, языка Java и числа 13.
Решения
Ладно, по условиям хватит. Теперь насчёт решений. Решение в обязательном порядке пишет и автор задачи, и его помощник. Желательно — на разных языках (в случае школьных олимпиад: c++/pascal, для студенческих: c++/java). Тесты обычно пишет не автор задачи. Зачем это делается? Дело в том, что при составлении задачи целиком одним человеком могут быть не затронуты какие-либо тонкости, упущены крайние случаи, да и вообще — выбран неоптимальный способ решения. Когда же решение написано двумя более-менее знающими человеками независимо, оно с гораздо большей вероятностью оказывается правильным.
В процессе написания решений зачастую меняется условия задачи. Ограничения — так те тысячу раз меняются, с целью либо прохождения, либо непрохождения определённых решений. Если разрешена Java — то могут лимиты по времени/памяти увеличить. Иногда внезапно находится дыра в условии либо контрпример, валящий одно из решений. В итоге, в процессе взаимодействий возникают 2 решения, они же — пресловутые «решения жюри», непогрешимые и непокобелимые =).
Тесты и чекеры
Тут всё более-менее понятно. Чекер пишется в том случае, если задача имеет более, чем одно решение и требуется вывести лишь одно произвольное возможное. В таком случае пишется программка, которая по входным и выходным данным проверяет оптимальность. Иначе же, если правильное решение только одно, проверка полностью отдаётся на откуп тестирующей системе. С авторов — только наборы входных и выходных тестов.
Теперь о тестах. Тут делится на две категории. Если олимпиада проводится по правилам ACM, то душа отрывается. В таком случае зачёт проходит лишь та задача, которая проходит абсолютно все тесты и написана с предполагаемой авторами оптимальной асимптотикой от размера входных данных. С поправочной константой в районе 2-3, ведь на написание решения жюри у автора 2-3 спокойные недели, а олимпионикам предлагается в диком кипише написать 10 решений за 5 часов. Пишутся тесты на граничные значения (проверить, что будет при минимальных значениях входных данных — зачастую многие упускают из виду случаи с нулевыми входными данными). Пишутся макстесты — на них часто сыплются неоптимальные решения либо решения, где писавшие неаккуратно обращались с массивами (о да, всегда десяток лишних элементов добавляю). В случае геометрии — пишутся тесты, на которых режутся ребята, состоящие во вражде с точностью и эпсилонами. Пишутся случайные тесты, если надо много — то генератор тестов. А если лень — пишется шоу.
Немного оффтопика:
В бытность второкурсниками мы с моим постоянным напарником и хорошим другом Мишей Городиловым составляли тесты на простенькую задачу. Вход — одно число до 10^18, выход — два числа. Писать генератор случайных чисел не хотелось. В итоге: в тестах жюри были и наши номера телефонов, и штрихкоды с банки кофе и бутылки кока-колы, и даже, под конец, результат двух ударов головой по клавиатуре. Для нас это тогда было быстрее, чем написать генератор
Так вот, а с школьными олимпиадами дело обстоит несколько иначе. Как уже говорилось в комментариях к недавнему топику, там другая система оценивания. Баллы начисляются за число пройденных тестов. Все прошёл — 100, только входной либо ни одного — 0. А между ними — всё наше буйство фантазии. Сначала продумывается ограничения на полнопереборное решение. Туда отправляются 3-4 теста на баллов 15-20. Чтобы не было обидно. Дальше продумываются возможные неидеальные варианты и асимптотики. Алгоритм работает за O(N^3) — вот ему смертельная пилюля. За O(N^2) — вот и ему. За O(NlogN) — хорошо. Вот ему макстест и если константа асимптотики хорошая, то будет 100 баллов. С геометриями, опять же, отсечку проходят на сложных тестах, где нужна повышенная точность. Ну и в этом случае пару набору входных/выходных данных составляет разбалловка.
Вроде всё. Условия написаны, решения есть, осталось загрузить всё в тестирующую систему и сделать взмах клетчатым флагом. Но об этом — в следующих статьях.
