Всем привет.
Идея динамической стоимости задач не нова. На сколько я помню, что-то такое обсуждалось еще в 2000-ные, однако на этом все и закончилось. С тех пор тема еще несколько раз всплывала — один из последних экспериментов здесь.
Зачем вообще нужны разные стоимости задач? Как верно подметил RAD, они в самом деле необходимы для контестов, где решение может упасть на системном тестировании или около того. Например, Вася решил простую A, а Петя решил простую A и очень сложную B. У Пети A упала, а B он решил попозже (и может не с первой попытке). В таком случае, если задачи были равны по стоимости, то Петя займет место ниже Васи, что как-то несправедливо.
На Codeforces задачи оцениваются в кратное 500 количество баллов: 500, 1000, 1500 и т.д. Обычно мы стараемся подбирать 5-задачные наборы, разнообразные по сложности. В таком случае, каждый квалифицированный на контест найдет себе задачи по силам и такие, над которыми надо подумать. Традиционный комплект задач включает в себя задачи 500-1000-1500-2000-2500.
На практике все не так просто. Иногда оказывается, что авторы и тестеры не угадывают сложность задачи с точки зрения массового участника. Как быть?
Эксперимент состоит в следующем. Назначать стоимость задачи динамически в зависимости от числа решивших эту задачу. Во время основного времени контеста здесь будут учитываться решения типа "Претесты пройдены", а по его окончанию — типа "Полное решение". Конечно, в расчет будут идти только официальные участники раунда.
Идея такая:
- если задачу решили от половины участников до всех участников раунда, то она стоит 500 баллов,
- если задачу решили от четверти до половины участников участников раунда, то она стоит 1000 баллов,
- если задачу решили от одной восьмой до четверти, то она стоит 1500 баллов,
- и так далее.
Конечно, речь идет о максимальной стоимости задачи. Падение в минуту вычисляется по традиционной формуле X/250 (учитывается X на момент построения текущего положения участника). Более формально в таблице:
| Доля решивших | Максимальный балл за задачу |
|---|---|
| (1/2, 1] | 500 |
| (1/4, 1/2] | 1000 |
| (1/8, 1/4] | 1500 |
| (1/16, 1/8] | 2000 |
| (1/32, 1/16] | 2500 |
| [0, 1/32] | 3000 (макс. балл за задачу) |
При подсчете числа участников учитываются те, кто сделал хотя бы одну попытку в этом раунде. Начальная стоимость (до какой-либо попытки по ней) любой задачи — 3000.
Вот и все! Как видите идея очень проста и не перегружена формулами и подробностями. Чтобы как-то с ней познакомиться сегодня по ссылкам "Результаты участников" для контестов по правилам Codeforces будут открываться результаты, посчитанные по таким правилам. Это временное изменение, вскоре мы вернем все назад.
Сегодняшний Codeforces Round 113 (Div. 2) будет использовать такие экспериментальные правила. Мы гарантируем, что задача A будет в нем именно та, которую мы считаем наиболее простой. Порядок остальных задач — случайный. Удачи!
Динамическая стоимость задач с шагом 250 баллов (поддержка реализована в марте 2015 г.)
Поддержана более плавная реализация динамической стоимости задач с шагом 250 баллов. Также как и раньше, при увеличении количества сдавших задачу в два раза, максимальная стоимость задачи уменьшается на 500 баллов. Теперь также при увеличении количества сдавших в 
раз, стоимость падает на 250 баллов. Таблица наже примерно иллюстрирует зависимость максимальной стоимости задачи от доли сдавших ее.
| Доля решивших | Максимальный балл за задачу |
|---|---|
| (0.707, 1] | 250 |
| (0.500, 0.707] | 500 |
| (0.353, 0.500] | 750 |
| (0.250, 0.353] | 1000 |
| (0.176, 0.250] | 1250 |
| (0.125, 0.176] | 1500 |
| (0.088, 0.125] | 1750 |
| (0.062, 0.088] | 2000 |
| (0.044, 0.062] | 2250 |
| (0.031, 0.044] | 2500 |
| (0.022, 0.031] | 2750 |
| [0, 0.022] | 3000 |
Как в этом раунде будут рассчитываться очки внеконкурсных участников?
Стоимости задач общие. Было бы странно иметь разные, так как показываются совместно. Раз общие, то логично рассчитывать по официальным участникам. Это довольно показательно, хотя может иметь спецэффекты для внеконкурсников. Здесь следует помнить — что раунд проводится в первую очередь для Div.2 участников.
Стоимость не убывает со временем? Можно все на последней минуте сдать и выиграть?
Нет, убывает как обычно. Так определяются макс. баллы за задачи.
невнимательно прочитал, извиняюсь
Результаты всех старых контестов стали показываться по новым правилам, и галочки для отключения не видно. Это значит, что пути назад нет? =)
Это временно, сейчас апдейтну пост.
изначально стоимости всех задач 3000?
Да.
CR100 теперь клёво смотрится
чем же?
Не очень понял. То есть и очки, которые набрали участники, тоже пересчитываются динамически?
May be more dynamism can be added. Suppose 100 people participate and A is solved by 50 people, then it gets 1000 point, and if it is solved by 51 people then it gets 500 point. So, a sharp boundary may be avoided. Just a thought.
Agree.May be some formula can be thought of to calculate the value of a problem just as codechef long contest does linkYour text to link here....
Я так понимаю что это некое подобие на вот эти правила, и мне кажется что тут немного логичнее рассчитывается. Объясню, дело в том что под конец раунда (тестирования или самого контеста), табличку может очень сильно изменить один успешный сабмит от далеко не топового участника, это разве логично, что какой то Вася решает задачу B на последних секундах, и ТОП 20 меняется кардинально?
UPD: А за то что делаете эксперименты спасибо.
почему меняется координально? ведь у всех балл по этой задаче падает
Это в случае если у всех примерно один бал был, а ведь обычно не совсем так. p.s. И баллы по последнему div 2 раунду не правильно проставлены.
Будут ли эти нововведения использоваться в раунде 2 VK CUP?
Нет.
Наконец-то люди начнут читать сперва условия ВСЕХ задач =)
По сути — полезное нововведение, помимо более справедливой оценки решений участники начнут учиться искать в задаче подводные камни, определяя ее сложность аналитически.
Насчет одного сабмита, меняющего всю таблицу, согласен.
Возможно, стоит ввести формулу по типу: 3000*(процент сдавших участников). Ну идея ясна, а формулу уже можно подкорректировать.
Так или иначе, спасибо за то, что сообщество продолжает двигаться вперед и развиваться. Удачного раунда всем!
не обольщайтесь, возможно, только 1 раунд будет проведен по такой системе
а это нововведение подразумевается навсегда?
так да или нет? а то минусование не дает ответа на вопрос
Сказали же — эксперимент, так что ничего еще не ясно. Для этого его и проводят, чтобы понять, имеет ли смысл менять правила навсегда
спасибо
How will the decreasing scores work? How many points per minute will be deducted if we don't know the original scores? Or are scores just calculated at the end of the contest?
An interesting formula to consider would be
, for nP the number of people who solve at least 1, nS the number of people who solve that problem. This gives a minimum and maximum bound of 400 and 3200 (those aren't fixed), while still making this dynamic.
My vote goes to min(3000,400*(1+lg2(nR/nS))) where nR is the number of rated contestants and nS is the number who correctly solve the problem. We may round to the nearest 50 or 100 to make the numbers look "nice", but rounding to 500s creates too much discontinuity.
As usual X / 250 per minute, where X is the problem max. score.
In this way, maybe your rank during the contest will change sharply several times =)
Дискретненько как-то. Из 1000 участников у 510 прошли претесты по задаче, и она оценивается на 500. Упало 9 решений на систестах -- те же 500, 10 решений и больше -- уже 1000. Резкое большое изменение количества баллов у части участников, появившееся только по случайному стечению обстоятельств.
Мне кажется система с более плавной оценкой, не делающая упор на то, чтобы количество балов делилось на 500, была бы лучше.
Да, скачки возможны. Их надо понимать как уточнение сложности задачи. С более плавной оценкой окажется, что баллы постоянно меняются, здесь они меняются реже. Вероятно, многие задачи будут устаканиваться по оценке довольно рано.
Interesting idea, I'm really excited.
Прикольно :) Т.е. если первая задача содержала tricky case и упала почти у всех, то её стоимость может зашкаливать за 1500, когда вторая на технику будет стоить около 1000. Просто факт. :)
Очень дельное нововведение!!! Спасибо!
непонятно, зачем отменили сортировку задач по сложности, больше стало смахивать на асм контест
Потому что многие начинали вонять "Почему D легче C?". А вот автору кажется, что С легче. И как вот тут судить?
That's an interesting idea. I also think that computing the scores without discontinuities would be better. Another thing you could provide to help us decide on a strategy is the fraction of people that solved each problem in each of the past rounds.
По-моему классно придумано, посмотрим что будет!
Ситуация:
Учавствуют 1000 человек. 500 человек решили задачу А, получили по 3000 баллов. Решил 501-ый — получил 2500 баллов. Затем каких-то двоих из первых 500 взломали, теперь стоимость задачи снова 3000 баллов, и кто-нибудь, сдавший задачу позже 501-ого может получить за нее больше баллов.
В этой ситуации количество баллов 501-ому решившему после взломов будет пересчитано?
ты не так понял, перечитай описание
Положение участников строится на основании текущего понимания ее сложности. Для всех максимальный балл за задачу одинаков, от времени зависит штраф (X/250 в минуту). Во время контеста сложность задачи может уточняться.
Идею вижу разумной но вставет проблема: то, выше участник A участника B зависит(и сильно зависит) от остальных участников.
Предполжим, есть 2 задачи, одна немного сложнее другой. Тогда бОльшая часть может заметить, что 2 не успеет решить, а у любую — успеет, решает ту, что сложнее и проигрывает. Особенным трешем это становится, когда участников немного.
Да и вообще, всегда приятно знать, что ты получишь, если сделаешь, что у тебя просят.
Ну и по-моему не такая уж большая проблема, что жюри ошибается со сложностью задач. Это можно рассчитывать как набор вакансий с известной зарплатой. Каждый выбирает то, что кажется ему лучшим по соотношению профит/сложность
Извините нагнал!
Выходит от того что кто то делает первые попытки в начале, стоимости вообще колбасить должно.
Очень понравилось. Хотелось бы продолжения эксперимента и развития такой системы. Но считаю, что дискретное разделение — зло, и его нужно менять на как можно более плавное.
Тогда можно будет с левых акков незаметно и немного опускать стоимость задач. При дискретном это сложнее.
А при плавном профит будет весьма сомнительным и не большим.
Если задачу сдало мало человек, то мб и большим. Но спалить это, наверное, несложно будет.
Зачем сливать стоимость задачи, которую решило мало человек, в т.ч. и вы сами?
UPD: нашёл ответ на такой же вопрос в ветке ниже
И если посмотреть на этот раунд, то видно что при плавном падении бал за задача B и D отличались, что было бы логично и подняло бы тех кто сделал D но не сделал B.
Но человек, делающий так, будет уменьшать стоимость задачи, которую он сдал. Оно ему точно надо?
Если он решил уникальную задачу раньше, а популярную — позже, то надо. В общем забейте на это, думаю никто не проникся, и профита немного вроде. :)
с системой CPR возникали вопросы вида: "что решать?"
были дискуссии на эту тему, даже Лёша Толстиков лично подходил ко мне и просил пояснений; но там хотя бы понятно, как можно рассуждать, чтобы добиться наилучшего профита
например там, если есть две задачи на 300 и 700 баллов, а успеваешь сдать только одну (но любую), то лучше сдавать на 700 баллов — видимо задача на 700 баллов сложнее и многие с ней не смогут справиться
я не участвовал в 113-м раунде, но я ничего не понимаю в описанных выше правилах:
вот есть задача с 2000 баллами, а есть с 1000, я могу любую из них решить, но только одну
мало того, что их стоимости могут меняться пока я пишу код, и, причём, очень резко и неожиданно, так ещё и есть систесты
бац! и после систестов 1000-ая начинает стоить 3000, а я сдуру решил 2000-ую, а её стоимость в процессе решения упала до 1500, если не до 1000 (а может даже именно из-за меня она будет стоить на 500 баллов дешевле)
во-первых, чувствуется серьёзная разница между 2000, которую решило 1/15 участников и 2000, которую решило 1/9 участников, особенно эта информация важна во время контеста, когда можно успеть любую из этих двух, но лишь одну
во-вторых, остаётся открытым вопрос: что же всё-таки решать?
в-третьих, допустим, из 1000 человек 495 решило A, 511 решило B и 252 решило C; стоимости A и C равны, а вот B будет в два раза дешевле, что выглядит достаточно абсурдно
мне нравится желание администрации сделать систему автоматического оценивания задач, но, хоть заминусуйте меня полностью, сейчас я вижу лишь пальцем-в-небо правила
И правда минусуют тебя полностью, а замечания-то по делу. Вот если стоимость сделать непрерывной, все будет круто.
да пусть минусуют, пофиг же
я не уверен, что будет круто с непрерывной стоимостью, смотри: есть две задачи примерно одинаковой стоимости, ты успеваешь из них только одну
какую именно? после финальных тестов в одной из них оказывается мегааццкий мегачастный случай, и почти все падают, а другая почти у всех проходит — в результате примерно одинаковая стоимость задач будет очень и очень различаться
главное, что мне не нравится в предложенном варианте — отсутствие какой-либо адекватной информации из монитора
Тебе-то пофиг, а читать не очень удобно светлый текст:))
мышкой наведи, подсветит ;)
вообще прикольный народ; хоть бы один из минусующих написал, где я неправ, или что не понравилось =)
по мотивам рекламы:
На мониторе при любой разбалловке есть ровно одна информация: сколько человек смогли пройти претесты по этой задаче.
При динамической стоимости, по-моему, из 2-х задач необходимо выбрать ту, по которой, с твоей точки зрения, будет меньше всего полных решений.
Этой информации в мониторе нет ни при каких баллах за задачу, потому что, например, авторы не включили в претесты какой-нибудь хитрый случай и у многих упадет решение, а без этого случая задача — халява.
Мне кажется, что если продолжить так рассуждать, то можно дойти до того, что монитор вообще не нужен. Можно просто решать задачи и самому догадываться какой процент участников смогут решить эти задачи, и как ваш результат (и набор решенных вами задач) будет соотноситься с другими. Но это совсем другое соревнование.
Я всегда считал, что монитор помогает ориентироваться в контесте: "почему все сделают, а я что-то вообще ничего не могу придумать, может стоит капнуть в другую сторону?", "ага, 2500 сдало уже более 10 человек, может там все же какие-то специфические знания, и на эту задачу стоит взглянуть".
А вопрос, который я когда-то задавал Саше, и сейчас для меня актуален, как определить, что если я могу решить любую из двух оставшихся задач, какая мне даст больший профит?
Мне кажется с усложнением и запутыванием правил больше всего подойдет тактика решать всё подряд (из тех что знаешь), иначе слишком много времени будет уходить на выбор стратегии (и это тоже нужно будет учитывать в своей стратегии ಠ_ಠ)
иди ШУТИТЬ отседова
I think the overall result of round #117 was positive. Except that problem B and D got the same score (3500) whilst one has 15 solutions and the other 86 solutions (More or less, another issue is the lack of stats specific to the contest rather than overall). I think there is a world of difference between those amounts. A better algorithm will assign around 500 points more to the harder of them, I think.
Indeed, you already count out-of-competition contestants. However, I totally agree that there should be a formula to make the discrepancy between problems' points "smoother".
Не знаю, как остальным, а мне было бы проще, если бы баллы за задачу не зависели от того, когда участник ее сдал, а только от того, сколько человек эту задачу решило.
Это будет уже не CF :)
Да и монитор станет бессмысленным, ибо можно толпой сдать всё в последний момент и хорошенько перемешать таблицу.
Если бы CF не менялся, вот тогда бы это был не CF. Можно всё, только зачем? Кому хочется в последний момент узнать, что половина твоих решений нуждается в дебаге?
И получим дележки мест в духе
1-5
6-30
31-300 (fuuuuuu..)
..
Ну в таком случае, конечно, надо было бы ранжировать участников с одинаковым количеством баллов по времени последнего АС, или как в ACM, или ещё как-то. Понятно, что так или иначе надо время учитывать, а как именно — это уже вопрос вкуса.
Ну что ж, покупаю бубен и начинаю играть в угадайку. Мне больше нравилась статическая система: там я знал, что я решаю.
How about assigning 500 points to the most solved problem, 1000 to the next one, 1500 to the next one ... 2500 to the least solved problem? In case of a tie you can assign the same score to tied problems.
If one problem was solved by x contestants and another one was solved by x + 1 contestants it will be totally unfair to give this problems different score.
But now such x exists anyway. It would be much better to make some continuous score function from number of persons solved.
Do you think the problems solved by 1000 and 1001 participant should have costs 500 and 1000?
I wanted to solve the problem described by this article (the problem makers cannot always sort problems by difficulty) and the problem described by vexorian (a problem solved by 86 people, another by 15 people and both with the same score) with the simplest algorithm. It is not the best one (a continous function would be best), but it is better than the method described in this article.
Problem A wasn't the easiest one!!! :-(
For the sake of continuity, I suggest the score for a question to be shared by all those who solved the problem. This way, the initial problem score could be ceil( 500 * numberOfUsers) / UserShare.
The share could be relative to the time taken by user to solve in comparisson to the sum of time taken by all users who solved during the contest time. The faster you do it, the more you get from the maximum score.
Although I have to admit, thinking of the details make it seem more complicated than necessary.
I don't think it's good formula. 1. Problem soved by 2 users is not really two times easer, then problem solved by 2 users. 2. It hould be scaled more close to existing.
I think something like
. It's not very good now, because if half of users solved problem it will cost about 1800. But i think that it's question of scaling value under erf.
"Typically Codeforces problems has divible by 500 values"
Мне одному кажется, что 250 баллов за задачу — уже как-то не серьезно?
За несерьёзную задачу несерьёзные баллы.
А после нескольких бревен она может стоить 75
Да, кстати. Очень прикольная фишка выходит. Мы делаем 4 неудачных попытки, и получаем 75(30%*250) баллов. То есть за последнюю неудачную попытку отбирается 25 баллов. И так с каждой задачей, со стоимостью 250 * (2x+1) баллов. Это ИМХО ну очень некрасиво выглядит...
А то, что за следующие отбирается 0, не выглядит проблемой?
Я знал, что кто-то таки об этом спросит. Но почему бы не изменить немного систему, и поменять штраф на 25? Ну и за взломы -25/+50 соответственно. По-моему так выглядело бы намного приятней.
P.S. но, все таки, могу поспорить, что 90% участникам до этого дела нет вообще.
нужно сразу правильно сдавать! а не морочить себе голову такой ерундой
Ну я бы так не сказал что ерунда. Теперь когда переделали динамическую систему взломы стали вообще опешные. Раньше и так бесило когда ты сидел мучился над задачей в конце концов сделал, думаешь тип ну все затащил рум, заходишь и видишь как какой-то парень с 20 взломами и одной задачей на первом месте. Да видеть баги в кодах других участников конечно круто, но, как по мне, нужно держать какой то баланс между взломами и решениями
Can anyone explain why all this is written 3 years ago but I see it in "Recent actions" and see it first-time now?
The post was updated
Не совсем хорошо то, что диапазон 3000 имеет больший размер (0.022), нежели 2750 (0.009), или 2500 (0.013), или 2250 (0.018). Логичнее было бы если бы диапазон уменьшался с увеличением стоимости.