Я давно собирался написать некоторые свои мысли о системе взломов, которую мы имеем на данный момент, и раунд 60 стал своеобразным толчком к этому.
Что мы имеем на данный момент: взломы можно делать на протяжении всего раунда, каждый успешный взлом приносит 100 очков, каждый неудачный взлом отнимает 50 очков, участники из обоих дивизионов перемешаны и каждый может взламывать каждого в своей комнате.
Мне всегда казалось, что на олимпиадах по программированию вроде Codeforces или Topcoder в первую очередь нужно уметь решать задачи, а уже потом взламывать чужие решения. Кто-то скажет что все заранее знают правила и у всех свои стратегии. Я согласен с этим, но тем не менее не считаю правильным иметь возможность за счет вариации стратегии будучи с 2-мя задчами обойти человека который решил 4, причем не очень медленно.
Для статистики я взял последние 10 раундов для обоих дивизионов и для каждого выписал максимальный процент баллов, набранных за счет взломов от общего количества баллов набранных участником, взятый среди первой пятерки по результатам контеста.
Раунд Максимальный процент Средний процент
Codeforces Beta Round #39 12.1% 4.8%
Codeforces Beta Round #41 10.3% 7.0%
Codeforces Beta Round #47 15.4% 5.2%
Codeforces Beta Round #48 30.8% 15.9%
Codeforces Beta Round #50 10.8% 5.4%
Codeforces Beta Round #51 11.6% 2.8%
Codeforces Beta Round #53 20.8% 10.8%
Codeforces Beta Round #56 12.2% 2.4%
Codeforces Beta Round #58 27.3% 6.5%
Codeforces Beta Round #60 70.5% 53.0%
Итак, в каждом из последних 10 контестов для обоих дивизионов был хотя бы один участник из первой пятерки, набравший более 10% своих баллов на взломах. В 4 из 10 контестов был хотя бы один участник из топ-5, набравший более 20% своих баллов на взломах. В одном контесте был участник, набравший более 70% своих баллов на взломах, причем в среднем на этом контесте первая пятрка набрала более 50% баллов на взломах.
Хоть ситуации подобные последнему раунду - редкость (хотя, в раунде 58 было бы то же самое, не будь там проблемы с условием задачи А), но все же они встречаются. Далее я постараюсь провести анализ ситуации со взломами на последнем раунде.
Итак, победитель раунда реализовал 39 успешных взломов, причем в его комнате другими участниками была сделана всего одна успешная попытка взлома. Теперь возьмем комнату 3. Во взломах в этой комнате принимали участие 4 человека, из них двое сделали более одного успешного взлома, поэтому далее будем учитывать только их. В сумме они реализовали 28 успешных взломов по задаче А, причем в этой комнате было всего 3 решения по этой задаче, которые не прошли финальное тестирование. Учитывая что в комнате победителя было 5 решений задачи А, которые не прошли финальное тестирование, то можно проигнорировать эти 3 решения из комнаты 3. Получаем, что даже если сильнейший участник попадет в комнату 3 и реализует эти 28 взломов с 1 попытки, он максимум сможет получить 2800 очков на взломах против 3800 реально полученных очков из комнаты 7.
Из-за распределения по комнатам очки за взломы могут варьироваться даже на +-1000 и даже сильнейшие участники попав в неудачную комнату не имеют шансов выиграть контест. Рассматривая эту ситуацию с комнатами 3 и 7 я не учитываю то что взламывать могут несколько человек в одной комнате, что тоже сильно снижает суммарные очки по взломам. Например, в комнате 6 два участника примерно в одно и то же время (на 11 и 13 минутах) начали взламывать задачи А, позже к ним присоединился еще один. Каждый из первых двух начавших взламывать реализовал по 12 взломов. Сильнейший участник попав в эту комнату не имеет шансов реализовать все взломы в этой комнате, даже если он очень быстро сдаст и заблокирует А и сразу начнет взламывать чужие решения. Даже если предположить что у него отберут 12 взломов, реализовав все остальные взломы с 1 раза он сможет набрать 2000 очков на взломах, что на 1800 меньше чем у победителя раунда. Опять же, шансов победить в этом раунде у него нет.
Я считаю что текущая система должна быть подвергнута изменениям. Есть 2 способа стабилизировать взломы, причем лучше всего их объединить.
1. Разделить участников из 1 и 2 дивизиона в разные комнаты. В среднем первые 5 участников по турнирной таблице последнего раунда набрали +300 очков на взломах фиолетовых, оранжевых и красных, остальные очки были набраны на серых, зеленых и синих. Разделив дивизионы, красные уже не смогут так беспощадно взламывать серых, тем самым уменьшится суммарное количество очков по взломам.
2. Изменить количество очков за взломы. Я уже не помню кем и где высказывалась мысль о том, что можно насчитывать баллы за взлом в зависимости от разности рейтинга взломщика и взламываемого. Например, если красный взламывает серого, прибавлять 20 баллов, если же серый взламывает красного, прибавлять 100 баллов. Количество баллов за взломы у победителя не будет заоблачным, в то же время вряд ли серые смогут навзламывать много красных и выбиться в топ турнирной таблицы за счет этого, не решив при этому большую часть задач.
Это сугубо мое мнение и оно может отличаться от мнения общественности. Критика и комментарии приветствуются.
В качестве альтернативы пункту 2 можно предложить привязывать очки за взлом не к рейтингу, а к общему проценту взломов по задаче. Это, собственно, весьма логично - чем легче взломать задачу, тем меньше баллов за взлом по ней.
В первом приближении формула может выглядеть как (кол-во взломов)*(баллов за взлом) / (кол-во посылок) = const. Хотя, наверняка для сложных задач в таком виде она не подходит.
Некоторый минус такой схемы тоже понятен - очки за взломы постоянно пересчитываются и результаты будут ползать вверх-вних независимо от действий участника.
UPD: Не, вообще кривая формула получилась... Но сама идея, вроде, здравая)
В раунде 60 я ломал в основном довольно универсальным тестом (0 0 0 1 1 0). Чтобы вновь послать решение, нужно пройти этот тест, и чаще получается придумать и реализовать при этом полное решение, чем случайно обойти его неправильным. Таким образом, тратится меньше времени на придумывание каждого конкретного взлома, зато по второму разу особо не поломаешь (мне удалось только 2 из 27 раз; ещё несколько неправильных решений было, но я их не нашёл).
Если же на каждое решение давать самый слабый тест, который его завалит, велика вероятность, что и перепосланное решение будет неверным. Больше времени тратится на каждый взлом, зато и общее количество взломов получается больше. Например, у победителя (Kenny_HORROR) 14 из 39 взломов — повторные, а количество разных взломанных людей 25, как и у меня. Думаю, в том числе и из-за более индивидуального подхода к каждому решению.
Раза четыре меня опережал yak_ex, потому что я скурпулёзно проверял, действительно ли упадёт, и не успевал буквально пяти секунд...
А ещё у нас в комнае было целых два участника, которых взламывали по три (!) раза! ruban и xiaoyoulei. Причём на ruban'е свою сотню получил каждый из трёх активно ломавших. Ещё четыре участника были взломаны дважды.
И повторюсь ещё раз, что Хороший тестировщик важен не меньше, чем хороший программист. ^_^
Для меня взломы вообще любимая часть игры, чем больше, тем лучше :) Причем в таком виде, в каком они здесь, на CF (в виде win-win game то есть), их больше нигде нет.
Вот идея давать разные баллы за взломы участников разного цвета - нравится.
Аналогично поддерживаю идею разных баллов в зависимости от цвета участника и против деления дивизионов.
P.S. Не против, что на "ты"?
не против. Мы, кажется, уже года полтора назад были на ты :)
1) готовить более сильные претесты (тем не менее, всю задачу они покрывать не должны)
2) давать разное количество очков за взлом разных цветов, например, 25-30-40-55-75-100 (а что будет, если пересчитать результаты последнего раунда с такой системой подсчета очков?)
3) возможно, стоит также уменьшать очки за повторный взлом одного и того же участника
Я тоже поддерживаю изменине разбаловки за взломы участников разного цвета. Ну, а также возможные решения на вопросы выше:
2) Половину от того что будет полученно в случае удачного взлома.
3) Я думаю не сложно сделать табличку со стоимостями / при открытии решения участника для взлома добавить ожидаемое число баллов за успешный взлом.
Тоже считаю, что стоимость взломов следует сделать разной в зависимости от цвета взломанного. Тут даже можно провести аналогию с шахматами (раз уж основной рейтинг Эло оттуда), где в коэффициентах Бергера, Бухгольца более ценны победы над сильнейшими участниками (там, правда, при равенстве очков).
Но то был оффтоп, по теме теперь:
Этот перекос скорее вызван желанием авторов устроить fun - если бы претесты были более жесткие, так много взломов бы не было. Вроде нормальный вариант - и претесты делать лучше покрывающими задачу, но не до конца - иначе взломы только по TLE будут, и баллы давать разные.
Идеальная стратегия взломов вроде как понятна - нужен "индивидуальный подход" к каждой жертве, т.е. ломать тестами, покрывающими лишь 1 баг из нескольких. Другое дело, что такой подход требует больше времени, и может оказаться так, что кто-то взломает раньше тебя. Поэтому мне кажется: видишь баг - немедленно ломай первым пришедшим в голову тестом (наверное, все так и делают).
Приятно встретить шахматиста, не очень стало это сейчас популярно. И о проблемах швейцарки я, естественно, знаю.
Мою фамилию когда-то можно было даже найти в "Энциклопедии шахматных дебютов". В качестве примера того, как не надо разыгрывать защиту Бенони черными :).
Кстати, шахматы вполне себе популярны сейчас. Но чем выше твой уровень, тем сильнее осознаешь, что шахматы превращаются в тупое заучивание дебютов.
Тем не менее, меня все еще можно встретить на сайте chessplanet.ru по выходным в 18-00
Ну, а "убил на шахматы" - это, как минимум, некорректно по отношению к шахматам. Не думаю, что эти занятия нам не помогли в программировании.
Убил - да, некорректно немного. Все-таки должно быть у ребенка хобби какое-то.
С другой стороны, я мало чего добился в шахматах, а в жизни они особой радости не приносят.
насчет претестов не совсем согласен. все-таки претесты довольно разумно делаются и чаще всего отсеивают глупые ошибки
просто здесь, в отличие от топкодера, к примеру, формат соревнований побольше рассчитан на взломы и побольше рассчитан на самостоятельное тестирование.
на топкодере же в тесты примеров почти всегда включаются жесткие тесты, и там в задачах поменьше крайних случаев.
но предыдущий раунд в плане взломов все-таки фейловый, имхо
Вот приятно просто, что есть такие люди. Живет значит спортивное программирование!
Сделать убывающую шкалу по стоимости взломов по конкретной задаче.
Но это только для одной задачи. Т.е. если я сделал два неудачных и один удачный челленджа по задаче A, и один удачный челлендж по задаче B, то я получу ( -50 + -45 + 100 ) + 100 = 105 очков.
А 20 взломов по задаче A будут равняться 650 очкам, а не 2000. :-)
Т.е. взламывать много будет всё же немного выгодно, но не так выгодно, как решать задачи.
Возможно лучше будет вот такую разбалловку:
Но так как некоторые люди недовольны такому выгодному хакингу (+72 у этого поста), то предлагаю такой способ.
Потому что почти все взломы делаются на задаче А на глупых ошибках.
Найти пару групых ошибок, вбить несколько тестов, а потом мониторить все решения, и соревноваться с другими кто первый их уронит -- это не круто. И не круто ронять на переполнении инта.
Если бы разделили стоимость взломов по разным задачам -- было бы заметно разумнее. Взлом задачи А ничего не стоит -- ему крайняя цена 10 баллов, чтобы нубики ей пытались отыграть поздно сданую задачу. 100 баллов взлом по задаче А не стоит.
А как взламовать ??