Возникла, как мне кажется, достаточно интересная идея возможного вычисления штрафного времени в формате ACM/ICPC.
Пусть K — число штрафных попыток, N — число решенных командой задач, t[i] — время решения i-ой (по счету для команды) задачи в минутах. Классическая формула выглядит так:
.
Предлагаемый вариант такой:
.
По пунктам улучшения и соответствия классическим правилам:
В классике, команда, которая
опоздала на контестмедленнее решает простые задачи, сразу оказывается в безнадежно проигранном по штрафному времени положении. В итоге, при равных штрафных попытках, на исход (при восьми решенных задачах) влияют первые пять — шесть задач, которые, обычно, намного проще седьмой и восьмой. Новая формула определенно смещает акцент в середину контеста.Следует из первого — в классике ошибку в ранней стадии контеста практически невозможно компенсировать. Задачи, которые дольше писать и, соответственно, на которых можно отыграть больше штрафа, решаются позже и влияют на результат меньше. Множитель i компенсирует это.
В классике, если какие-то команды пишут соревнования раньше остальных (досрочно), то они безнадежно проигрывают штраф, потому что остальные команды "не показывают" им простые задачи в начале соревнования. Здесь зависимость от начала соревнования уменьшена.
Поскольку цена каждой следующей задачи возрастает, лидирующая команда не может "успокоиться" и соревнование становится более напряженным и интересным.
Новая формула немного лучше компенсирует реальное время, оставшееся в конце контеста. Точнее, его цена возрастает примерно вдвое (последняя задача в два раза дороже средней).
Формула для штрафного времени построена из следующего преобразования стандартной формулы:
В каком-то смысле, цена штрафной попытки не меняется при переходе от одной формулы к другой.Во многих случаях, относительные результаты, посчитанные по новой и старой формуле, будут совпадать. Новая формула, во многом, уточняет классическую при близком штрафном времени, а не кардинально изменяет ее.
Оптимальная тактика "решать от простых к сложным" не изменяется.
Мысли, идеи, предложения?
P.S. Разумеется, речь не идет об изменении стандартных правил ACM/ICPC. Даже сложно подумать об этом. Однако, нестандартные варианты правил достаточно часто встречаются, например, на SN*S и onsite opencup. Интуитивно — подобный подсчет штрафного времени лучше адаптирован, например, для ситуации, когда участники начинают соревнования не одновременно, а соревнуются в виртуальном режиме.
Очень хорошие мысли, и в большинстве пунктов поддерживаю автора, но, к сожалению, консервативные организаторы врятле поддержат эту идею. P.S: не согласен по-поводу 1го пункта. По-моему умение выбирать и быстро решать халявки — один из показателей мастерства команды.
Умение выбирать и решать халявки — да, разумеется, потому что стандартным по правилам ACM/ICPC начало соревнования по цене [дальше читать оригинальный пост].
С другой стороны, умение быстро угадывать мысли пишущего условия (например, на неродном для тебя языке) — не главный предмет соревнования по программированию, а в этом одно из условий хорошего старта.
Надо проводить контесты, чтобы посмотреть. Напиши Снарку, он любит новые формулы
Я собирался это сделать, если мне не найдут существенный недостаток на КФ.
На самом деле, ничего проводить не надо. Можно любой имеющийся контест пересчитать.
Не совсем. Люди все-таки писали исходя из обычных правил. Пусть разница невелика, но иногда это довольно существенно
А в чем возможная разница в поведении команды, которая пишет по стандартным и по этим правилам?
Для этого надо пересчитать по ней несколько контестов, посмотреть, кто поменялся местами и сравнить стратегии
Например, команда, отстающая на задачу, но имеющая преимущество по времени нередко вычисляет сколько у нее есть попыток на сдачу задачи без потери лидерства, что влияет на то, сколько времени будет уделено тестированию.
Есть небольшие вопросы и дополнения по пунктам.
1-2) Достаточно часто 7, 8 задачу не сдают, а упихивают ногами -> штраф по первым задачам уже не становится сколько-либо принципиальным. Отсюда следствие и во второй пункт: сдать 7, 8 задачу и отыграть штраф возможно — просто необходимо продумать получше идею, как оптимизировать константу, доказать решение, писать достаточно нахаченно. И, кроме того, кто виноват, что команда плохо решает халявные задачи?
3) На официальных соревнованиях редко такое бывает, что одна команда пишет соревнование раньше других. Такое случается на опенкапах, но они не официальные. Как мне кажется, АСМ — правила команду, которая лучше подготовлена, все равно оставят в лидерах, если контест нормально сбалансирован — да, команда будет медленнее искать задачи, но быстрее придумывать решения и сдавать у нее все равно получится быстрее, кроме того возможно выиграет на одну или несколько задач. Что касается равных по силе команд, не уверен что вообще хоть какая-то формула способна нивелировать такое преимущество как ранклист, в котором видны остальные команды.
4) Лидирующая команда в принципе никогда не сможет успокоиться, т.к. преследующая ее команда всегда может сдать на одну задачу больше.
5-6-7-8) А правильно ли, что цена последней задачи выше первых? Сейчас поясню. Допустим, все команды в ранклисте начинают сдавать очевидную реализацию в задаче J и тратят на это 17 минут, а в задаче H какая-то из команд найдет простую формулу и сдаст ее за 5 минут. И это даст команде, которая нашла эту формулу, большое преимущество по стандартным АСМ — правилам. А по вашим получится, что она получает небольшое преимущество. В итоге получится, что по вашей формуле правильным выбором будет откладывать математические(идейные) задачи до поры до времени, и сидеть писать очевидные реализации пока математик доказывает правильность утверждений. Это будет большим плюсом для команд, которые намного хуже пишут математику чем реализацию. Во всяком случае мне так кажется.
А что есть официальные соревнования, и почему OpenCup таким не является?
Видимо, слово "официальные" — плохое, но не могу придумать лучше:(. Я подразумевал онсайты, отборочные к ним и вообще соревнования, с которых можно собрать профит. Да, Вы сейчас скажете, что на opencup тоже есть онсайт, и с него тоже можно собрать профит в виде кубка, но лично для меня opencup это просто тренировка. И, как мне кажется, очень мало кто воспринимает opencup именно как серьезные соревнования, а не как тренировку. Хотя бы потому, что онсайт помимо людей, участвующих в онсайте, пишут еще и те команды, которые пишут сборы в ПЗ. То есть профит от участия в онсайте минимальный.
Однако, на мой взгляд, ничего из того, что я сказал в топике выше, ваше замечание не меняет.
Собирать профит с контестов — не очень хорошая идея, гораздо больше профита вы соберёте просто работая :) А по части "серьёзности" организации он сильно опережает многие контесты с большими денежными призами. Тем более, он является единственным регулярным командным контестом без возрастных ограничений, и называть его "несерьёзным" или "неофициальным" — несколько странно.
Полностью поддерживаю. Еще бы добавила, что в онсайт опенкапа выйти сложнее, чем финал ACM ICPC. Поэтому в некотором роде он даже престижнее :)
Это сильно от ВУЗа зависит.
Утверждение: как и в правилах ACM, правильно решать задачи в порядке увеличения времени кодирования. В частности, оставлять задачу, которую можно сдать за 5 минут, не выгодно.
Пруф: Заметим, что такой порядок решения в обоих случаях следует из факта, что поэлементно не большее t[i] дает не больший результат.
Не совсем. В частности, после доказательства (которым занимается другой член команды) мат. задачу зачастую получается закодить гораздо быстрее, чем перед тем как доказательство было получено, а так же тратится меньшее время на тестирование. На "чисто кодерских" задачах что ты ее сейчас начнешь писать, что через час — писать придется один и тот же объем. В итоге представим себе такой проблемсет из двух задач: задача А — математическая и ее можно решить за 11 минут в случае, если решать ее "с места в карьер", и 5 минут, если решать ее после кодерской, и задача В — чисто кодерская, решать ее 17 минут если сразу и 15 минут если после математической. В итоге в ACM-style выигрывает порядок АВ(11 + (11 + 15) = 37 штрафных минут против 17 + (17 + 5) = 39 штрафных минут), а в anonymous-style выигрывает порядок BA(17 + (17 + 5)*2 = 61 штрафная минута против 11 + (11 + 15)*2 = 63 штрафных минут)
anonymous-style :) Не привыкли еще к его новому нику?
Модель не очень ясна. Если я правильно понимаю, что 6 минут надо придумывать решение А, то:
1) кодим 6 минут кодерскую задачу.
2) принтер, отдаем комп, на 11 минуте сдаем А.
3) на 22ой минуте сдаем B.
Такой порядок дает 33 минуты по ACM и 55 минут по новым правилам.
Хорошо бы было использовать эти правила для онсайтов опенкапа, когда разные команды стартуют в разное время. А то по правилам acm у команд, вышедших с 9-12 мест, с самого начала руки опускаются.
Однако у правил acm есть два больших преимущества перед всеми остальными. Они очень простые и используются почти везде. Именно по второй причине вряд ли удастся заменить их на что-то другое на обычных этапах кубка, которые часто совмещены с разными локальными соревнованиями или контестами в Петрозаводске. А пересчитывать результаты реальных участников, которые писали по правилам acm, на другие правила для учета в кубке, имхо, нехорошо. Потому что, как было замечено, разные правила приводят к разным стратегиям поведения.
Насколько я понял, смысл этих правил как раз в том, чтобы проще было командам, решающим контест без монитора, а при раздельном старте это как раз те, кто вышли с первых мест.
Зато те, кто начали позже, не получат огромного штрафа по простым задачам. Правила сглаживают различия в начале контеста.
Онсайт с раздельным стартом был вроде бы только летом 2011, и там время шло с нуля для всех команд.
Вполне возможно, я что-то путаю. Про 2011 год я точно не помню, в правилах на сайте про время с нуля ничего нет. Просто хотела высказать общее соображение, что новую модификацию правил можно приспособить для онсайта. Но в последнее время, действительно, онсайт совпадает с петрозаводским контестом, который пишется по правилам acm.
Только на онсайте сейчас не 20 минут штрафа за неудачную попытку, а 20*место. На последнем онсайте у нас было 200 минут штрафа за попытку, в итоге +2 по последней задаче перекрыли сдачу всего остального с плюса.
Давайте посчитаем. Пусть есть две команды, одна стабильная и медленная, другая быстрая и хаотичная. Пусть есть 10 задач. Наши обе команды очень крутые, поэтому первые 9 для них "ни о чём", а 10я — технический гроб.
Стабильная команда пишет в час по две задачи и сдаёт их каждые полчаса с первой попытки. Получаем у неё 11550 штрафа (непривычная цифра, да).
Шустрая команда пишет 9 задач за первый час (тратя на каждую задачу равное время) и получает за это 1157,380952 штрафа. Допустим 10ю задачу команда сдаст в 300 и получит 3000 штрафа.
Вычитаем 11550 — 1150 — 3000 = 7400. Сколько же раз может шустрая команда штрафануть чтобы не проиграть? Аж 67 раз. о_О
А хотел ведь доказать сначала, что толкать не выгодно, но пришел к тому, что штрафные посылки тут уже роли почти не играют, вот, мне нравится.
Повторить число 1157 + 3000 = 4157 у меня не получилось. Генератор
Говорит, что ответ равен 4900, и возможное число штрафных попыток 60. Старая формула говорит, что 1650 vs. 600 и возможны 52 попытки. В таких ситуациях штрафные попытки и правда не играют роли :)