Поскольку никто не идеален, никакое жюри не может точно оценить сложность задачи. Часто случается, что предполагаемая стоимость задачи не соответствует реальной. Бывает даже, что более дорогая задача оказывается статистически более простой (например, SRM 504.5). Поэтому имеет смысл подумать о возможности определить стоимость задач апостериори, по результатам контеста.

Подумаем, какую статистику о задаче можно использовать при подсчёте стоимости задачи.

Количество сдавших задачу? Безусловно, количество сдач отражает интеллектуальную и техническую сложность задачи.

Статистика времени сдачи? Пожалуй, нет. Если есть какой-то заранее заявленный порядок задач по сложности, то, как показывает опыт, большинство участников начнут решать с самой простой задачи, и тогда использование статистики времени сдачи опирается на мнение авторов контеста о сложности задач. Если нет, то очень часто бывает, что вначале контеста много участников сдаёт задачу, которая первой была сдана кем-то. Тогда как для очень сильных участников бывает несколько одинаково простых для них задач, которые весьма разные по сложности для большинства других участников. И получится, что быстрее всего будут сдавать не самую простую задачу, а ту, которая первой будет кем-то сдана.

Количество попыток? Пожалуй, да. Статистика количества попыток говорит о том, насколько сложно написать задачу без ошибок. Конечно, важна при этом полнота набора тестов, на котором задача тестируется сразу.

Теперь подумаем, как должна зависеть стоимость задачи от того, сколько человек её сдали. Очевидно, что задача, сданная одним человеком, гораздо сложнее задачи, которую сдали десять человек. Разность в сложности между такими задачами далеко не такая, как между задачами, сданными десятью и двадцатью людьми. Скорее она примерно такая же, как между задачами, сданными десятью людьми и ста. Соответственно, кажется естественным функция вида 1/k, где k – количество сдач.

При этом есть две проблемы, связанные с такой формулой. Во-первых, если одну из задач на контесте решит только один человек, а все остальные – хотя бы 10, то человек, решивший уникальную задачу, скорее всего выиграет: 0.1 – очень мало по сравнению с 1. Нормально ли это? Наверное. Ведь единственного человека, решившего самую сложную задачу, пожалуй, можно назвать сильнейшим.

Правда, есть один нюанс. Дело в том, что такая функция стоимости задачи может побудить некоторых из сильнейших участников упорно решать сложную задачу, рассчитывая быть единственным, кто её решит и выиграть. И он может её решить и выиграть, а может потратить на неё весь контест, и не решить, показав очень плохой для себя результат. Так как целью контеста является определение сильнейших, такой исход был бы нежелательным.

Кроме того, возможна следующая ситуация. В конце контеста две примерно одинаково сложные задачи никто не решил, и несколько сильных участников пытаются решить кто-то одну из этих задач, а кто-то другую. И в результате одну задачу решит один человек, а другую – три или четыре. И получится, что человек, решивший уникальную задачу, выиграет с большим отрывом, несмотря на то, что несколько других участников решили примерно такую по сложности задачу.

Таким образом, фактор случайности намекает на то, что не должен быть такой разрыв по стоимости между задачами, решёнными одним человеком и решёнными 2-5 людьми.

С другой стороны, задача, которую решили 100 человек, действительно вдвое сложнее, чем задача, которую решили 200. На таких задачах фактор случайности нивелируется за счёт большого количества испытаний.

Есть несколько способов борьбы с этой проблемой. Например, можно поделить 1 не на k, а на медленно растущую функцию от k, например, корень (четвёртой степени) от k, или даже ln k. Или можно взять функцию 1/(k+10). Более того, можно даже сделать задачи популярности от 1 до 5 одинаковой стоимости. Например, стоимость задачи может быть определена, как min(1/ln(5), 1/ln(k)), или 10-(2, log_2(k)).

Теперь подумаем, как должна стоимость задачи зависеть от числа попыток, которые понадобились участнику для того, чтобы сдать задачу. Очевидно, стоимость задачи не должна бесконечно падать с увеличением количества попыток, потому что решённая задача – это всё же решённая задача, сколько бы попыток не было на неё потрачено. Иначе может получиться, что через некоторое количество попыток пропадёт смысл сдавать задачу – это неправильно со всех точек зрения. Какая часть задачи не может быть съедена штрафными попытками – подлежит обсуждению. Мне лично нравится коэффициент 2/3.

Надо заметить, что между + и +1 есть существенная разница, а вот +7 и +8 – это почти одно и тоже. Поэтому чем дальше, тем меньше баллов надо отнимать за штрафную попытку. В связи с этим, можно, например, вычитать за первую штрафную попытку 1/6 стоимости задачи, а за каждую следующую – вдвое меньше, чем за предыдущую.

Таким образом, как пример вышенаписаного, можно предложить следующую формулу стоимости задачи. За сданную задачу даётся, во-первых, неотъемлимая стоимость задачи в размере х = min(1/ln(5), 1/ln(k)), где k – количество сдавших эту задачу участников. Кроме того, даётся бонус за чистоту в размере x/2^t – где t – количество попыток, с которых была сдана задача.