Кто я такой? занялся 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 уже позволяет провести такой контест и всё упрётся только в визуализацию результатов.
В общем, если идея хорошая — ставьте лайк, участвуйте в обсуждении — может это заинтересует других организаторов. Без массового применения, интереса она представлять не будет, поэтому и пишу здесь. Если же идея старая — поделитесь ссылкой на реализацию, особенно интересует возможность проводить свои контесты, тренировки и т.д. Понятное дело, что в мире существуют сотни контестов с неточными решениями, но я говорю именно о реформах в классическом спорт-проге, где есть давно устоявшиеся традиции.
Кажется, что лучше все-таки требовать от организаторов предоставлять генератор, который генерит хотя бы одному тесту из каждой "группы" — пусть это и будет что-то достаточно случайное.
А можно ли будет самим организаторам добавлять тесты по ходу соревнований? Например, придумали / увидели какое-то совсем неверное решение — взяли и дописали в свой генератор парочку тестов, совсем "не очень" решения упали.
Вполне можно потребовать от генератора претестов удоволетворять тем же критериям, что и генератор участников. Но вот в распределении баллов на мой взгляд он участвовать не должен.
Думаю, в общем случае, это сломает объективность. Т.к. одни решения в жюри посмотрят, другие не успеют или не поймут. После контеста можно ради любопытства нагенерить любых тестов и понять кто же был "действительно лучшим", но это уже не должно влиять на результаты соревнования.
Например я, как жюри, придумал интересные тесты. Почему мой генератор не может участвовать в распределении баллов?
Про объективность — ну и участники аналогично могли бы законтрить подход Х, но не законтрить подход Y.
Не очень понимаю, почему вы не оставляете возможность жюри делать тесты, влияющие на распределение баллов.
В сущности, я просто озвучил идею и постарался сделать её для начала максимально простой и масштабируемой. Развивать и улучшать можно до бесконечности. Например, у меня была в голове идея, чтобы жюри писало своё решение и свой генератор, который держит базовую кубышку 100% баллов пока кто-то его не победит на этих тестах или не добавит новых, на которых окажется лучше решения жюри. Т.е. жюри де-факто участвует в контесте со всеми, просто вычёркивается из итогового протокола.
По-моему, расширение списка тем никак не поможет, по той причине, что т.н. "стандартных знаний" будет несколько больше, только и всего.
Мне кажется, оптимизация по убиранию логарифма довольно часто пригождается. А вообще говоря, ведь спортивное программирование это в первую очередь соревнование по придумыванию алгоритмов, а не по их написанию. Не вижу ничего плохого в том, чтобы не заставлять участников оптимизировать константу в решении. Особенно это проявляется в школьных олимпиадах: у школьников может не быть достаточно набора знаний, чтобы оптимизировать решение, скажем, путем того, чтобы чаще попадать в кэш, или применить процессорные оптимизации.
А как предлагается решить эту проблему? Отсутствие локальных соревнований это проблема организации, а не формата олимпиады. Что же касается того, что менее опытные участники не могут попробовать себя в роли авторов задач. Это ведь совершенно нормально: трудно (не невозможно, но трудно) составить задачу, если ты недостаточно опытен в задачах. Это как составить шахматный этюд, плохо умея играть в шахматы.
На белорусских олимпиадах, к примеру, есть задачи с открытыми тестами: дается 10 тестов, и нужно при помощи различных эвристик и приближенных алгоритмов сгенерировать как можно более удачный ответ.
Могу предложить контесты, которые будут состоять только из ad-hoc задач и конструктивов. Там точно не будет стандартных алгоритмов.
И как этого добиться? Главное влияние жюри на результат — составление набора задач, и темы и сложность этого наборы и определяют ключевое влияние на результат.
Автор, а вы правда не видели NP-полных задач на контестах? Они там уже давно есть. По поводу эвристик: на одно локальное белорусское соревнование я давал задачу, где надо было решать коммивояжера т.н. деревянным алгоритмом (не в лоб, конечно, но через серию действий задача сводилась к этому). Как известно, этот алгоритм выдает ответ не более, чем в 2 раза больший, чем оптимальный. Как же я обошел это? А очень просто: гарантировал, что все тесты это невзвешенный граф, в котором есть гамильтонов путь. Стала ли задача хуже? Конечно, нет, но зато она вписалась в обычную систему оценки.
Итак, предлагается проводить не очень длинный контест, с супер-нестандартными задачами, и при всем том, что участники будут тратить мало времени, заставить их еще и... генерировать тесты?! Ну, я вижу тут ряд проблем, конечно. Одна из первых: сильным участникам нет никакого смысла генерировать тесты, а слабые вряд ли смогут сделать это качественно. Также другая проблема: порой генерация сильных тестов не проще, чем решение задачи, и, если сделать так, то в задаче как были слабые тесты, так и останутся.
Необходимо заставить, но генератор опционален...
В общем, судя по тексту, вы предлагаете примерно следующее: превратить спортпрогу в этакое подобие huawei challenge, где задачи (эвристические и качественные!) могут приносить любые, даже неопытные участники, тесты готовиться не будут, а участники сами за время соревнования должны будут пытаться делать тесты, при всем при том, после каждого нового теста все решения будут перетестированы (что вызовет неимоверную нагрузку на сервера, если делать это постоянно). Как формат вполне интересно, но едва ли это может быть серьезным соревнованием. Если уж так хочется, можно проводить олимпиады, более приближенные к реальным задачам: что-то посчитать многопоточно, к примеру, разработать сервер и так далее. Но это будет, во-первых, точно не для школьников, а во-вторых, вряд ли будет требовать знания алгоритмов.
В общем, мне кажется, что ваша идея сработала бы, конечно. Можно было бы провести несколько олимпиад в таком формате, и, скажу честно, это было бы невероятно интересно. Но делать все соревнования такими совершенно не хочется.
P.S. Если хотите ответить, отвечайте, пожалуйста, на английскую версию комментария -- мне кажется правильным, чтобы обсуждение видели все участники сообщества, а не только русскоязычная часть.
You're pushing a lot of the burden of preparation onto contestants... and onto CF. There's a reason why contests with non-exact solutions tend to run for much longer — it's a potentially unlimited amount of work for potentially no payoff.
You forgot to add: if you have the time. Besides the concern was never accusing the jury of preferring some heuristic, but lack of a clear specification that makes such concerns irrelevant. What if some specific heuristic passes because nobody made tests for it? What if there are all kinds of tests, but very few of a particular kind? The jury will have to decide to give them weights (equal weights also count) and that introduces the bias you want to avoid. If there are 2 tests which give 1% to one solution and 1 test which gives 1% to a different solution, it fair to get more points just because there are more tests? Will the jury manually filter that? More bias!
We've already had problems without exact general solutions, but with an exact (condition-based not score-based) checker + guarantees like data being generated randomly. They have hacks disabled. I think that's a much better approach.
However, you're free to make a site hosting such contests yourself to try your idea in practice. There's an alarming dropoff in the number of CF-style programming contest sites recently, definitely a gap you could fill.
The idea is to put competitors in equal conditions, give them simple rules and... watch what will happen. It is the same idea as ICPC in terms of simplicity. When many people start to solve difficult problems and make tests for it in a very short time of competition, we don't know what will happen, but for sure system will balance itself. When CP started no one could imagine that competitors will solve some problems in 5-10 minutes. I remember the days when giving suffix array task meaned 0 attempts in table and now it's a standart school task. For sure one day such epic improvement of skill will take place in a difficult problems and test-making. 5 minutes from the start of contest and you'll see that top-teams already posted random solutions and tests better than some professionals will make in a week.
This is an english translation of my russian comment I made a few minutes ago, sorry for the duplicate, didn't see this blog has an english translation.
In my opinion, expanding the list of topics would not help at all, for the reason that the so-called "standard knowledge" would be somewhat more, that's all.
It seems to me that optimization to remove the logarithm comes in handy quite often. And generally speaking, sports programming is primarily a competition to come up with algorithms, not to write them. I see nothing wrong with not forcing participants to optimize a constant in a solution. This is especially true in school olympiads: they may not have enough knowledge to optimize the solution, say, by hitting the cache more often, or by applying processor optimizations.
And how do you propose to solve this problem? Lack of local competitions is a problem of organization, not a problem of Olympiad format. As for the fact that the less experienced participants cannot try themselves as the authors of the problems. This is absolutely normal: it is difficult (not impossible, but difficult) to come up with a problem if you are not experienced enough in problems. It is like composing a chess study, if you are bad at chess.
At the Belarusian olympiads, for example, there are problems with open-ended tests: 10 tests are given, and one must generate the best possible answer with the help of various heuristics and approximate algorithms.
I can propose contests that consist only of ad-hoc problems and constructives. There will definitely be no standard algorithms.
And how to achieve this? The main influence of the jury on the result is coming up with a set of problems, and the themes and hardness of the problems in this set determine the key influence on the result.
Author, have you really not seen NP-complete problems at contests? They've been there for a long time. Regarding heuristics: for one local Belarusian contest I gave a problem, where it was necessary to solve a traveling salesman with the so-called wooden algorithm (not directly, of course, but through a series of steps the problem was reduced to that). As you know, this algorithm produces an answer not more than twice as big as the optimal one. So how did I get around this? Very simply: I guaranteed that all tests are unweighted graph, which has a Hamiltonian path. Did the problem become worse? Of course not, but it did fit into the normal grading system.
So, it is proposed to have a not very long contest, with super-unusual tasks, and for all that participants will spend little time, make them also... generate tests?! Well, I see a number of problems here, of course. One of the first: it makes no sense for strong participants to generate tests, and weak participants are unlikely to be able to do it qualitatively. Also another problem: sometimes generating strong tests is not easier than solving a problem, and if you do that, then the problem as there were weak tests, and so will remain.
It is necessary to force, but the generator is optional...
So, judging from the text, you propose the following: to turn sportproga into a sort of huawei challenge, where tasks (heuristic and qualitative!) can be brought by any, even inexperienced participants, tests will not be prepared, and participants themselves during the competition should try to make tests, with all that, after each new test all solutions will be retested (which will cause an incredible load on servers, if done constantly). As a format it is quite interesting, but it can hardly be a serious competition. If you really want, you can hold an Olympiad, closer to the real tasks: to calculate something multi-threaded, for example, to develop the server and so on. But first of all, it would definitely not be for schoolchildren, and second, it is unlikely to require knowledge of algorithms.
In general, I think that your idea would work, of course. You could hold several Olympiads in this format, and frankly, it would be incredibly interesting. But I don't want to make all competitions like that at all.
Too much issues about "don't change anything". I'm not an classic competition programming hater, so you should not explain the benefits of current format. I spent 15+ years as contestant/coach/author and I love it :) But I see the big problems with it, especially in mass-market. Many students now don't want to compete after finishing school, cause they sure that they've got all benefits from CP and better to try something else. My students prefer not to start compete at all, cause they have no chance to global success without school-background and almost no local competitions around. Don't you see that Russian teams win allmost all World Finals? Is that because they best of the best, or because nowadys many great students in other countries prefer another path for their self-improvement? Without a big changes CP will collapse into a closed comunity of fans who year by year solving the same problems and people from outside will completely loose interest to it, cause around CP will be more agile and lively communities.