Архив форума

После соревнований в Перми, где за чистоту стиля дали приз команде, решившей хоть и с первой попытки, но всего одну задачу (хотя были команды, решившие пять задач с первой попытки), мне захотелось вывести формулы чистоты стиля. Такую, чтобы учитывала и количество задач, и качество их решения. После некоторых размышлений первая формула получилась такой: число задач+число сданных с первой попытки. Тут при равном числе задач учитывается, сданные с первой, а при равном числе сданных с первой, учитываются остальные. Это идеальная формула для вычисления, но она не учитывает количество плохих попыток (сдать со второй явно лучше чем с десятой). Фактически, сданные с первой получают двойной коэффициент, эквивалентно тому, что сданные не с первой делятся на два. Логично уменьшать баллы за задачу пропорционально числу сделанных попыток.
Поэтому самая лучшая, на мой взгляд, формула чистоты - это сумма 1/(число попыток) для всех сданных задач. Считать немного хуже чем первую, но зато учитывается всё, полная справедливость.
По этой формуле на чемпионате Урала по чистоте победила команда ПГУ-1, второе - УГАТУ-1.

Народ, может у кого-то есть свои формулы, почему никто не предлагает? Что надо считать и как? Чистоту можно оценивать просто по количеству сданных с первой попытки. Или (самая первая и простая формула, выведенная после первого чемпионата в Перми):
(число сданых с первой попытки)/(число всего попыток + 1)
Здесь +1 в знаменателе, чтобы учитывалось количество сданных задач. Одна проблема - почему +1 а не +A, где A - константа чистоты.

Хм. А что вообще предлагается? Ввести еще некоторый показатель. Зачем? Есть железная точка зрения, кто победил - тот и играл "чисто". Достаточно чисто, чтобы победить.

Объективно ли понятие чистоты? И нужна ли нам эта характеристика? И чем замечательна команда, решившая 7 задач с первой попытки, если она проиграла команде, решившей 8, но с пятых, шестых, восьмых попыток. Правила соревнования достаточно объективно оценивают чистоту, как штрафное время +20 за подход. С правилами вроде никто и не спорит. Может быть мы просто по известной русской традиции хотим поддержать обиженных реальным исходом соревнования, но милых сердцу? ;)

И вообще ситуация немного странная. Играем вроде в одну игру, а призы дают за результаты в другой ;)

А если не осмысливать необходимость вычленения такой характеристики, как чистота, то мне формула Стаса нравится вполне.

Полностью не согласен со своим тезкой. Если у команды нет чистого стиля, то ей ничего не светит на крупных соревнованиях. Далеко за примерами ходить не надо - взять хотя бы наши 1/2 финалы. Выигрывает тот, кто играет чище, у кого уходит меньше времени на разбор того, что же в проге приглючилось. Очевидно, что меньше времени уходит у того, кто сдает с 1ой попытки. А на межнаре выигрывала хоть одна "нечистая" команда?! Нет! Обогнать на несколько задач это конечно же лучше, но на 1/2 финале такое уже не прокатит и придется бороться не только за задачи, но и за чистоту.

P.S. Очень рад был услышать, что на Урале команда УГАТУ-1 2ая по чистоте стиля :))

Не. Тезки друг друга не поняли :lol: Посылка: команда выиграла, следстие: команда играла чисто. Вот что я имел в виду.

PS Я перечитал только что написанное. Чушь конечно. Но формальная логика неумолима ;)

Не-е! вот смотри! Хотим определить какая из команд лучше играет в ICPC.
Способ первый: устроить чемпионат и посмотреть кто выиграет.
Только как показал прошедший ЧУ, корректность этого способа под вопросом :)) Результаты в 1 и 2 туре сильно отличались! Значит нужен какой-то альтернативный способ.
Вот, например, смотрим результаты:

УрГУ-2
1 тур: чистота=4,976 задач=8
2 тур: чистота=5,353 задач=8

ПГУ
1 тур: чистота=5,5 задач=6
2 тур: чистота=5,833 задач=8

УГАТУ
1 тур: чистота=3,005 задач=6
2 тур: чистота=7 задач=8


Тут видно, что, вообще говоря, ПГУ играет сталибьно и стабильно лучше, чем УрГУ-2.
Уж не поэтому ли они были в финале, а УрГУ-2 нет? ;)

Такой результат уже говорит, что эта формула имеет все основания на жизнь :)

И вообще, эта формула говорит о том, сколько задач за тур способна решить команда ЧИСТО! Очень показательно, имхо :)Я как ее увидел, решил устроить своеобразный мозговой штурм и предложил сам себе целый ряд формул и.... и все отверг, как необъективные и неучитывающие или плохо учитывающие тот или иной фактор :))
Так что мне формула Стаса тоже очень нравится! И альтернатив я предложить не могу... Разве что в знаменателе степень поварьировать, но это уже не серьёзно. Да и формула должна быть максимально проста и наглядна!
Так что я ЗА применение этой формулы! :)

Предлагается Паше подсчитать коэффициент "чистоты стиля" в двух турах и постоить графики:
1. Чистота стиля в первом - чистота стиля во втором
2. Итоговая чистота стиля - итоговое место
Также просьба вычислить корреляцию.

и запостить их в тему "Немного статистики...." Очень интересно ;)

PS Хотя это представляет, пожалуй, лишь теоретический интерес. Если мы получим хаотическое распределение на обоих картинках, то это будет свидетельством, что показатель никому не нужен, если все выстроятся по y=x, то зачем нам дублирующий показатель?

Знаешь, мы, наверное, за это и любим ACM, что результат соревнования слабо предсказуем. У любой команды есть сильные/слабые стороны, комплекты бывают разные, огромную роль играет банальное везение. Было ли когда-нибудь, чтобы какая-то команда стабильно выигрывала ВСЕ соревнования на протяжении двух лет? Даже Дурову/Лопатину это не удалось. Нельзя просто взять две команды, комплект и в вероятностью 99% сказать, кто на нем выиграет. Только сыграть ;)

Да и вообще характеристика "лучше" зачастую бессмысленна. Кто из нас, Паша, лучше программирует, а? :P

Говоря "лучше" я имел в виду такой чисто абстрактный показатель, как вероятность победы на усредненном комплекте, который естественно ни вычислить, ни даже определить номально не получится :)
Что-то типа, если устроить марафон на 1000 комплектов тем 40 командам с ЧУ, то "команда А лучше команды Б" означает, что место команды А в таком марафоне выше места команды Б.
И проблема очень простая: как по результатам одного-двух конестов сравнить по этому параметру 2 команды.
То есть как найти некую характеристику, в каком-то смысле близкую к результатам подобного марафона :)
Есть гипотеза, что параметр "чистота на ЧУ" в каком-то смысле лучше параметра "место на ЧУ" :)

Не хочу по этому параметру сравнивать! :lol: Это уже ДРУГАЯ игра получится. Менее зрелищная/яркая/динамичная.

Вводить параметр дополнительный - пожалуйста. Тогда получится именно ситуация: играем за одно, призы за другое. Стиль игры команды во многом определяются правилами. Когда моя команда во второй день ЧУ проигрывала 8:5, мне уже плевать было на чистоту. А до этого 5 задач сдавались именно чисто. Причем засчет тестов, однократной вычитки до сабмита. Разве что гигантские тесты на TL не генерил. После цель была - рог сломать, но 8 сдать ;) Последние 3 задачи мы так и сдавали "методом силового пробивания". Это тоже техника. Её тоже надо уметь применять.

То есть вы сначала должны договориться на какой именно приз вы претендуете, и играть соответственно :))
Только и всего! Если важна поездка в Питер - играете как играете.
Если вдруг приза за чистоту захотелось, играете максимально чисто.

Вот и все! Просто становится больше возможностей. А значит игра становится интересней! :))Именно более динамичная зрелещная и яркая! Именно за счет нескольких "номинаций" :)

Мда... Серьезный вопрос. Я, пожалуй, поддержу точку зрения Дениса Назарова, что команде, играющей нечисто, уже в Питере мало что светит. Дена Расковалова надо немного поправить: "Команда выиграла, следовательно, играла чисто" - вообще-то неверно. Можно и при грязной игре выиграть на контесте некоторого уровня. Во всяком случае, соглашусь с такой посылкой: "Команда стала чемпионом мира, следовательно играла чисто". Все остальное можно оспорить. Команда Перми в первом туре и УГАТУ - во втором играли первоклассно! Стиль и уровень команд сразу чувствуется. Взяли задачу, решили, сдали, следующую - решили, сдали и так далее. Это только наши команды берут все сразу, потом добивают все сразу. Проблема не в том, что это неправильно, а что у более сильных команд должно все с первого раза сдаваться. Ну ничего, может, хоть добивать научимся.

Плюс этой формулы - в том, что команда, решившая 5 задач чисто, имея -10 еще на 3-х задачах и сдав их, свой показатель чистоты только увеличит. Кроме того, количество штрафных попыток по одной из задач не сильно влияет на коэффициент (8 задач чисто, или 7 - чисто, а одну - с двадцать пятой попытки - изменение в пределах 1). Минус в том, что нельзя все же всегда говорить, что команда, играющая чище, может достигнуть лучших результатов. Пример: одна команда решила 8 задач - все - со второй попытки, вторая - 5 - все с первой. Вторая имеет больший показатель, возможно, даже не прикидывая в уме, как остальные 3 задачи решать. Другое дело, что решившие 8 задач, поедут в Питер или куда-то еще, решат там 6-7, но грязно, и из-за штрафного времени могут не попасть в те команды, которые едут дальше. Например, в Питере, МГУ3 с 8 задачами заняла 3 место и имела показатель чистоты 4.83. ПГУ с 7 задачами заняла 6 место и имела показатель 6.5. ИжГТУ с 7 задачами заняла 10 место с показателем 5.78. Показатель чистоты СпбИТМО = 8.68.
Так что с этим показателем считаться все же надо.

А вот что я писал до этого :)Тебя смущает, что 8 со второй равно 4 с первой? Определись с тем, какой расклад тебя не смущает и соответствующим образом подбери показатель. Не 1, а 0,5, например :)

А тебя не смущает? :)Это, пожалуй, дает более полную картину. Теперь цена решенной задачи становится больше, и решить ее с 10 попытки - не тоже самое, что вообще ее не решить.

В том то и дело, что это вопрос из разряда, "куча - это сколько?"

Я не знаю! Качественно формула хороша. Количественно - не знаю :)
И честно не знаю, что лучше 8 со четвертой или 7 со третей :)

Вот показатели чистоты пятерки лидеров, посчитанные по этой формуле:
1.ПГУ:
1 день - 5.707. 2 день - 6.577. Итого: 12.284
2.УрГУ-2:
1 день - 6.077. 2 день - 6.028. Итого: 12.105
3.УГАТУ:
1 день - 3.890. 2 день - 7.414. Итого: 11.304
4.ИжГТУ:
1 день - 2.914. 2 день - 6.707. Итого: 9.621
5.УрГУ-3:
1 день - 3.618. 2 день - 5.524. Итого: 9.142

Меньше показатель степени в знаменателе делать нельзя, а то получим не показатель чистоты, а место в зачете(кол-во решенных задач). Безусловно, на первом месте по чистоте - ПГУ. Кстати, все видели, как они первоклассно отыграли Барнаульский Интернет-контест? :o