Кто я такой? занялся ACM ICPC в 2006-м уже студентом, 5 раз съездил на полуфинал, потренировал команды провинциального ВУЗа, провел несколько лагерей для школьников от нулевого уровня и выше, многократно участвовал в организации региональных соревнований (Олимпиада ЮФУ aka Чемпионат Юга РФ aka GP of Azov Sea — Opencup). В последние годы занимаюсь карьерой, поэтому активно в спортпроге не участвую, но периодически продолжаю помогать в проведении соревнований в Таганроге.
Зачем высказываюсь? Всё чаще ловлю себя на мысли, что спорт.прог не успевает за быстро меняющимся миром и становится труднее находить аргументы для студентов им заниматься. Со школьниками, наверное, попроще, но это лишь вопрос времени. Понимают ли эту проблему те, кто организуют ICPC, школьные олимпиады и т.д. — я не знаю, так как в деятельность сообщества активно не вовлечен. Вполне вероятно, что всё что я скажу дальше уже многократно обсуждалось здесь или в коридорах ИТМО, а может быть уже и реализовано на какой-нибудь неизвестной мне платформе (изысканий не проводил). А вдруг нет?
Какие проблемы вижу в спортпроге:
Задачи полиномиальной сложности конечны. С каждым годом становится труднее придумывать оригинальные задачи, особенно для соревнований с невысоким уровнем участников. Спортпрог становится всё больше похож на шахматы в том плане, что из-за конечности задач в обозримое время ИИ будет справляться с ним лучше людей, а в соревнованиях людей на первый план выйдут не знания, а способность вычленить смысл из запутанного текста условия и применить стандартные знания (а то и библиотеки) в стрессовой ситуации в ограниченное время. Онлайн же рискует пострадать от засилия читеров. Внешний мир (работодатели, спонсоры и тд) к решаемым задачам с каждым годом будут относиться всё с большим скепсисом, так как в реальной жизни степень неопределенности на порядок выше. Добавлю, что из-за желания жюри принимать решения на разных языках, оптимизации в духе “ускорить в 2 раза” или “убрать логарифм” на сегодняшний день в спортпроге практически бессмысленны, при том, что в жизни они имеют заметный экономический эффект.
Качественно делать задачи очень дорого. Подготовка задачи, даже если это поставлено на поток, занимает огромное количество времени, а следовательно денег. В первую очередь это касается покрытия тестами, ведь для организатора нет ничего хуже, чем принять заведомо неверное или неоптимальное решение. Становится всё труднее проводить локальные оффлайн соревнования, потому что невозможно найти ресурсы для подготовки оригинальных задач, а старые убивают объективность и сильно проигрывают онлайн-контестам. Из-за отсутствия локальных соревнований, снижается разнообразие, не образуются социальные связи между участниками, а участники вплоть до достижения топового уровня толком не могут попробовать себя в роли авторов, не будучи захейченными за недостаточно качественные задачи.
Все попытки расширить класс задач упираются в проблему объективной оценки. Жюри не может оценивать одну эвристику выше другой эвристики, потому что существует набор тестов, на котором результат будет обратным, а участникам тесты и их распределение неизвестны. Единственным успешным кейсом расширения классического набора задач стало появление интерактивных задач, но и этот класс очень ограничен в размере и предъявляет те же требования к полноте решения и тестов.
Чего хочется достичь:
Контесты должны быть интересными. Применять раз за разом стандартные алгоритмы не слишком интересно, поэтому необходимо увеличивать влияние интуиции и творческого аспекта. Спонсорам должно быть интересно от того, что задачи отвечают требованиям сегодняшнего дня, а в идеале они могут легко принести на контест свою реальную задачу и получить силами коллективного разума новые решения и тесты. Зрителям должно быть интересно, потому что контест длится разумное время, а результат не вполне предсказуем до самого конца, в идеале если он ещё и может быть визуализирован.
Контестов должно быть много и их проведение не должно требовать больших затрат на подготовку. В идеале формула должна позволять любому провинциальному ВУЗу или школе за неделю-две качественно подготовить оригинальное соревнование силами преподавателей или студентов не самого высокого уровня.
Контесты должны быть объективными. Должно быть минимизировано влияние жюри на результат. Участники должны быть в равных условиях и соревноваться в первую очередь друг с другом. Фактор случайности при этом должен быть минимально возможным.
Что предлагаю:
Снять все ограничения на решаемые на контестах задачи. NP-полные задачи, задачи с неточным решением, сложные игры и т.д. — использовать в качестве задач можно всё, ведь это огромный массив новых знаний и навыков, которые не менее полезны для участников, чем применяемые сейчас в СП.
Не требовать от жюри подготовки полных наборов тестов, идеально правильных или разных неправильных решений для задач на куче языков. В идеале должно быть достаточно условия, семплов для понимания формата и простейших претестов для отсечения заведомо кривых решений (скорее для проверки соблюдения формата, чем для проверки правильности).
Участники в течение контеста могут залить решение и залить генератор (или интерактор). Решение обязательно, генератор — опционален. При появлении нового решения, оно тестируется на всех тестах, сгенерированных участниками. Результат выполнения сравнивается по некоторому критерию с другими участниками, в результате чего происходит перераспределение баллов. При появлении нового генератора от участника, его старые тесты аннулируются вместе с полученными за них баллами, а все решения тестируются на новых тестах, что приводит к новому перераспределению баллов.
Вот и всё :) На мой взгляд именно такая простая схема проведения может сработать, равно как когда-то сработала схема ACM ICPC где плюсик дают независимо от сложности задачи.
Как считать баллы?
Самая похожая на ACM ICPC схема — это дать всем задачам одинаковую цену в баллах и распределять их в процентах между участниками. Для ровного счёта, предположим, что задачу решило 10 участников (т.е. их решения прошли претесты жюри, чтобы отсечь полную дичь и сэкономить ресурсы системы), и только 5 из них залили свои генераторы, каждый из которых создал по 20 тестов. Тогда у нас в системе лежат 100 тестов, на каждом из которых мы запустим все 10 решений, т.е. каждый тест даёт 1 процент. Допустим на одном из тестов участник нашёл решение лучше всех остальных, тогда он получит 1% за него. А на другом тесте все 10 участников нашли одинаковое решение — они получат 0.1% за него. Если два участника нашли решение лучше остальных 8, то они получат по 0.5%. Ну и т.д. Очевидно, что сумма баллов всегда будет равняться 100%. При этом за счёт присутствия как больших так и маленьких тестах, слабые участники смогут претендовать на баллы до самого конца соревнования. Различные вырожденные случаи вроде "один участник прошел претесты и не залил генератор" тоже не мешают подводить итоги — даём ей все 100% за задачу.
Теперь немного подробностей, почему я считаю, что при такой схеме проведения можно объективно посчитать результат для любой задачи:
Для начала применим эту схему к существующим ACM задачам, у которых есть точное решение. Очевидно, что участники распределятся также, как они распределяются на школьных контестах, за исключением случаев, когда какие-то ошибки не покрывается ничьими тестами. Что ж… это часть тактики, тратить ли время на генератор в попытке отобрать баллы у соперников или решать другие задачи? Зато теперь нельзя будет обвинить жюри в неполном покрытии тестов, а в составе каждой команды появится человек с развитыми скиллами тестирования (именно в командном исполнении данный формат будет наиболее интересным).
Применим схему к какой-нибудь NP-полной задаче или задаче без точного решения. Очевидно, что на выходе в системе будет куча тестов на разные эвристики, а решения в значительной степени будут рандомными. Но обвинить жюри в предпочтении какой-то эвристики будет уже невозможно, ведь ты сам мог написать генератор, который сломает соперников. Будет ли ценность у этой кучи эвристик? Конечно! Ведь в сумме они образуют программу, которая покрывает их все, причём за разумное время выполнения. Чем выше уровень участников контеста, тем качественнее будут как решения, так и тесты.
Применим схему к какой-нибудь игре, например, шашкам. С одной стороны будет решение(интерактор) с ходами за белых, с другой решение соперника с ходами за чёрных. Очевидно, что по результатам запуска каждого с каждым будет получена вполне объективная таблица результатов независимо от того, будет ли соревнование проводиться среди младших школьников или среди топ-участников. И хотя ни в том ни в другом случае результат не будет сравним со специализированными программами, контест это провести не мешает, а для подготовки потребуется только описать правила игры, формат данных и написать чекер для проверки корректности хода
Несколько мелких нюансов, которые дополнят общую картину:
Решение, запущенное многократно на фиксированном наборе тестов (равно как и генератор) должно выдавать одинаковый результат, т.е. участник должен при рандомизации использовать фиксированный seed. В противном случае результаты становятся непредсказуемыми, а значит и необъективными.
Необходимо заставить участников создавать в генераторах не только большие тесты, но и маленькие. Проще всего потребовать от генератора создавать все тесты сразу, а в условии описать критерии для них. Например, потребовать, чтобы часть из них была маленькая.
Чтобы таблица результатов могла отображаться в онлайне, а участники не завалили проверяющую систему бесконечным тестированием, должно быть ограничено количество или время между посылками генераторов, по крайней мере до заморозки монитора. Очевидно, что после заморозки можно тестировать выборочно (например, только последние попытки).
Контесты, проводимые онлайн, должны использовать разбиение на комнаты. В противном случае количество тестов будет слишком большим. Итоговый результат можно подсчитывать уже среди топ-участников из комнат. Для оффлайн мероприятий генерация 10-20 тестов каждым не будет большой проблемой, ведь количество задач на контесте из-за необходимости писать генераторы тоже сократится.
Необходимо подумать, как учитывать время в посылках и стоит ли его учитывать вообще. Очевидно, что при таких правилах участники ни в какой момент времени не могут полностью прекратить работу над задачей, ведь в любой момент могут появиться тесты, на которых их решение потеряет эффективность, либо появится идея, как сломать чужие решения. Скорее всего появится огромное количество тактик, как тратить время контеста, что однозначно увеличит зрелищность.
Показывать или не показывать участникам тесты, назначать ли какие-то бонусы за "первое решение" или "хороший генератор", с какой точностью сравнивать результат, учитывать ли время и память, ограничвать ли многопоточность, требовать ли упихивать сорцы в один файл или разрешить уже исполнять что угодно в изолированном контейнере — всё это малозначимые нюансы, которые общей картины не меняют.
Что требуется чтобы начать?
Нужна доработка Codeforces, а учитывая существующую инфраструктуру взломов, educational-раундов, полигон и т.д. она не выглядит очень масштабно. Вполне возможно, что существующий API уже позволяет провести такой контест и всё упрётся только в визуализацию результатов.
В общем, если идея хорошая — ставьте лайк, участвуйте в обсуждении — может это заинтересует других организаторов. Без массового применения, интереса она представлять не будет, поэтому и пишу здесь. Если же идея старая — поделитесь ссылкой на реализацию, особенно интересует возможность проводить свои контесты, тренировки и т.д. Понятное дело, что в мире существуют сотни контестов с неточными решениями, но я говорю именно о реформах в классическом спорт-проге, где есть давно устоявшиеся традиции.
