Здравствуйте еще раз!
После одного своего недавнего комментария я неожиданно задумался над вопросом — насколько в СП работает принцип "своего поля". И первый делом я решил проанализировать результаты Саратовского ГУ на ЧФ в Саратове.
Выборка строилась за последние четыре года так: выбираем первые 8 команд-участников Саратовского ЧФ из участвовавших на NEERC. Выписываем их относительные места парой (ЧФ, NEERC). Оставляем команды Саратовского ГУ. Получаются следующие данные:
2008 1 1 2 2 3 6 4 7 2009 1 2 2 1 3 4 6 7 2010 1 2 3 3 5 5 7 6 2011 1 1 2 2 5 6
Или то же самое на диаграмме (одинаковые точки совмещены):
Здесь выше линии значит, что команда на ЧФ выступила лучше, чем на NEERC, ниже — наоборот. Из 15 пар в данных 7 выше линии, 6 на линии и 2 ниже линии. Одна пара выше/ниже локальная, вторая точка ниже (7 6 в 2010 году) является, в каком-то смысле, ошибкой агрегации (не учтены команды Volgograd SU и NN STU, которые заняли на ЧФ место ниже 8 и выше соответствующей команды Саратова).
Я не специалист в области мат. статистики, но в данном случае очень похоже, что команды Саратова в Саратове решают лучше. Хочется узнать, есть ли соответствующие эффекты в других ЧФ и насколько они сильные?
тонко подошёл к вопросу =)
Интересно увидеть такую же статистику для всех вузов, которые:
результат лучше.
А. Стабильно выходят в финал;
Б. Стабильно имеют 3-4 команды в полуфинале.
Казалось бы, команды таких универов более мотивированы на 1/4, чем на 1/2
Константин, мое мнение по этому вопросу таковое:
0) Во-первых, данные по крайней мере за 2011 год не корректны. В четвертьфинале 5 место заняла команда Saratov SU #9(Хайрулин, Ветошкин, Иванов), а в полуфинале выступала другая команда нашего университета (Saratov SU #4 — Гусаров, Коновалов, Коваль), которая показала на четвертьфинале значительно более низкие результаты, в районе 15 места(не могу найти нормальный ранклист).
1) На Саратовском ЧФ авторы задач — преимущественно саратовские, и совершенно нормально, что задачи той тематики, которые дают авторы, саратовским командам знакомы лучше. Что, кстати, совершенно не означает, что нам каким-либо образом помогают. Просто задачи своих авторов саратовцы решают чуть лучше — но, надо отметить, преимущество у команд СГУ не слишком велико по сравнению с проблемсетами от других авторов, что заметно и на NEERC, и на opencup, и на других ресурсах.
2) Надо заметить, что командам от СГУ намного сложнее выйти в полуфинал, чем другим командам региона — квоты на ВУЗ заставляют команды готовиться к четвертьфиналу и хорошо на нем выступать. В то время, как команда Samara SAU #1 могла спокойно уйти после 4 часов контеста, команды Saratov SU #2, Saratov SU #4 вынуждены были писать до конца, потому что сданные две задачи от нас, Saratov SU #3, или от Saratov SU #5 могли их выбросить из тройки лидеров (мы этого не сделали, потому что я валерный и запихал паленую идею по I, а задачу H из-за того что дебужили I не понимая где палево мы не успели написать). То что ни мы, ни команда номер 5 из нашего универа не сдали эти задачи — сути не меняет: команды из Саратова вынуждены писать свой четвертьфинал очень хорошо. На полуфинале все-таки каждая команда должна хорошо написать, чтобы пройти на финал.
Собственно, именно в этом я вижу причины хорошего выступления команд от СГУ на четвертьфинале.
0) Данные о составах за тот год я просмотрел, замечание верно.
1) Преимущество не выглядит настолько как "невелико", если учитывать, что такое даже 0.4 места по ожиданию в первой восьмерке при составе в среднем 3-4 команд уровня финала мира. [Еще часть отвечу ilyakor ниже.]
2) Конкуренция — это, конечно, хорошо. С другой стороны, например, команда Samara SAU #1 на моей памяти не уходила на последнем часу с контеста, и вообще играла все соревнования с полной выкладкой. И я не думаю, что много команд бросало ЧФ посередине.
По поводу конкуренции. Команда Teddy Bears решала задачи в любом случае гораздо спокойнее, чем команды из Саратова. Кроме того, в финале обычно команды из других вузов более мотивированны — например, третья команда из Саратова обычно прекрасно понимает, что у нее мало шансов пробиться на финал, и теряет мотивацию на полуфинале. Ладно, не хочу разворачивать эту дискуссию, я убежден в своей правоте, Вы — в своей. В любом случае, если Вам так не нравится Саратовский ЧФ, Вы можете:
1) Не ездить на него. Вас никто не заставляет. Действительно, зачем ездить на такой нечестный ЧФ, где команды из одного города/региона поставлены в более хорошие условия?
2) Насколько я знаю, в жюри Саратовского ЧФ принимают участие в работе не только люди из Саратова. Конечно, не мне судить, но если жюри сочтет Вас достаточно квалифицированным, опытным, и, самое главное, адекватным человеком — я думаю, что в этом случае Вы вполне можете принять участие в работе жюри, пытаясь улучшить качество четвертьфинала.
Слушай, вот неужели ты еще не понял, что Костя просто поржал, написав этот пост? :)
Кстати, со стороны состав жюри и правда выглядит немного странным, потому как почти все люди оттуда — саратовцы, но вроде бы не было заметно, чтобы это как-то помогло саратовским командам. По крайней мере, в этот раз :) Мы сами виноваты, что не придумали B и K.
1) Я бы с удовольствием организовал ЧФ в Самаре. И ездить никуда не надо. И стандартной квоты хватило бы на Самару с головой.
2) В жюри Саратовского ЧФ принимает участие человек не из Саратова. Жаль, что вряд ли этот человек мог влиять на выбор той или иной задачи. Вот не знаю, но я, как знакомый с SAU#1 и SAU#2, вполне могу сделать соревнование, на котором SAU#1 будет не просто против SAU#2, при кардинальной разнице в уровне и опыте. В этом смысле весьма показательна задача Triathlon с давнего NEERC. И это не обязательно делать осмысленно. Просто жюри Саратовского ЧФ, во многом, считает, что подготовка везде ведется ровно так же, как в Саратове. Недавняя %problem_name% (контест еще идет) в очередной раз это подтвердила.
Кроме того, тестирующая система на ЧФ собственная, неизвестная всем командам вне Саратова. И тренировки закрытые, так что задачи авторов ЧФ можно видеть только на ЧФ, в Петрозаводске и/или на opencup (в последних двух другой уровень сложности!) вне Саратова. Много факторов.
Могу сказать, что с системой которая на ЧФ мы тоже мало знакомы, на саратовских закрытых тренировках она другая.
Кстати, давно хотел спросить (и у кого-то даже спрашивал, но всё не по адресу): почему бы не сделать закрытые саратовские тренировки открытыми? Плюсы очевидны — увеличение вселенского добра. А разве есть какие-то минусы? Было бы очень интересно услышать ответы людей, разбирающихся в этой ситуации.
А можно ли ознакомиться с примерным списком тех, кто открывает свои тренировки? И не задавал ли ты подобный вопрос представителям других вузов? Каковы были ответы?
Чуть позже я напишу свое мнение на эту тему.
Мы открываем все свои тренировки. Все 0 штук.
Хм, ну тренировки МГУ/Физтеха/других московских вузов открытые, там в прошлом году даже MIT и CMU участвовали. Тренировки Итмо — тоже открытые. Так что закрытые тренировки — скорее исключение, чем правило.
Возможно, я не разобрался с contest.yandex.ru, поэтому задам глупый вопрос. Вот здесь приведен полный список тренировок, или есть какие-то еще?
Полный список тренировок, проходивших в этом учебном году. На contest.yandex.ru тренировки проводятся начиная с этого календарного года, контесты прошлого семестра почему-то сейчас в списке не отображаются, наверное, по техническим причинам. Ссылки на все старые тренировки (в т.ч. и на edjuge) есть в гугл-группе acm-msu (сейчас она вроде deprecated). Команды других вузов туда пускали/пускают без проблем.
Так вот, про наши тренировки.
Сейчас в нашем архиве тренировок содержится большое количество материалов, которые по договоренности с авторами, либо в соответствии с условиями их распространения не могут быть использованы для проведения открытых онлайн-тренировок.
Тестирующая система в архиве уже морально устаревшая и работает не всегда стабильно. Она годится для проведения локальных тренировок, но для открытых тренировок ее функциональности и надежности не хватит.
Тренерскому коллективу СГУ весьма удобно при организации тренировочного процесса, что на в архив решают только те, кого мы тренируем.
Хочу отметить, что тренерами, участниками и сотрудниками нашего университета много делалось и делается для сообщества. Мы постоянно готовим контесты на Петрозаводские сборы, этапы Открытого кубка, проводим четвертьфинал, поддерживаем созданный нами online-judge acm.sgu.ru и проект Codeforces. Отмечу, что суммарно на acm.sgu.ru и в Codeforces.Тренировках уже имеется порядочное число контестов, для которых доступно виртуальное участие (в отличие, например, от тренировок ИТМО). Вполне возможно, что и мы сами переведем свои тренировки на платформу Codeforces. Которая, на мой субъективный взгляд, удобней contest.yandex.ru.
Я совсем не уверен, что у тебя получилось бы провести ЧФ у себя. Организовать это чрезвычайно сложно.
Самая главная сложность в организации ЧФ — получить ЧФ. Все остальное не очень отличается от организации обычного контеста.
Зная наш вуз, сомневаюсь, что у нас получится что-либо организовать :) С технической стороны проблем нет, еджадж-то давно стоит и работает, а вот организовывать заселение участников, возиться с документами, искать спонсоров... В вузе все это никому не нужно. Это не локальный контест, где люди пришли, посидели 5 часов и ушли.
А. Мне совершенно лень по пунктам тебе расписывать, что как и почему в логике универа, например, почему вы с поездками в универе мало кому нужны.
Б. Я не понимаю сложность размещения даже 20 команд. Саратовский ЧФ без команд из Самары и Саратова составляет ~40 команд.
В. Даже необходимость размещения под вопросом. Я совершенно не понимаю, почему при 4-сайтном NEERC не проводить многосайтный ЧФ с общим жюри. Например, географически Самара — Казань — Нижний Новгород.
Г. В любом случае, я не понимаю, почему, если жюри Саратовского ЧФ бравирует своей распределенной работой в разных точках мира, оно ограничивается собственными кадрами, и в нем, например, нет представителей Самарского ГАУ, Нижегородского ГУ, Казанского ФУ, Волгоградского ГТУ.
А. вот потому что в универе мы мало кому нужны — поэтому ты и фиг организуешь ЧФ у себя
Б1. договориться с гостиницами/общагами, обеспечить всех документами и договорами, не?
Б2. кто согласится у себя разместить 200 человек на время контеста/открытия/закрытия? это тоже очень большая сложность
В. вот этого я и сам не знаю, наверно играет роль доверия к местам параллельного проведения, все-таки ЧФ — важное соревнование, и нельзя абы кому разрешить у себя дома писать
Г. суммарно у жюри в Саратове: 2 чемпиона мира, 4 золота и 8 серебра на финалах. Зачем нам представители??
P.S. ну все-таки для особо важных людей есть исключения, например, Елена Рогачева.
A. поездки в универе никому не нужны. ЧФ — хорошая отчетность универа, нет?
Б1. 30 штампов на командировках, договорах и прочих документах в канцелярии? Много гостиниц/общаг, не желающих принять в октябре гарантированно много людей?
Б2. Ты про актовый зал? Три раза?
В. Обмен представителями уже не в моде? И потом, доверие — вещь обоюдная. Почему все должны доверять Саратову, а они могут кому-то не доверять?
Г. Почему же тогда жюри NEERC это не только СПб ИТМО и СПб ГУ? И потом, жюри — не участники соревнований. Не очевидно, что быть хорошим автором задач и хорошим участником — одно и тоже (например, Елена Валерьевна не самый сильный участник).
P.S. Второй пример будет?
По поводу состава жюри лучше всего, наверное, ответит Михаил, но мне кажется, что я тоже могу объяснить ситуацию. По крайней мере, как я ее понимаю.
Жюри действительно не испытывает потребности в упомянутых тобой представителях, поскольку у нас достаточно опытных и грамотных людей для того, чтобы подготовить один контест в год.
С другой стороны, никто не будет закрывать двери, если кто-то из представителей упомянутых тобой вузов выразит желание работать в составе жюри. Этого в массовом порядке не наблюдается. Елена Рогачева несколько лет присылала свои задачи и стала очень ценным членом жюри. Больше, насколько я знаю, никто не пытался.
А как насчет компьютерных классов? Нужно отменять/переносить занятия из этих классов. Скорее всего, классов какого-то одного факультета не хватит — как это каждый год происходит в Саратове, придется договариваться с другими факультетами. Опять-таки, необходимо чтобы стояло нужное ПО — а это все-таки не домашние компьютеры, где можешь ставить все что душе угодно — нужно специальное соглашение/разрешение.
Вот в этом плане у нас все довольно хорошо. У нас есть специальный корпус — медиацентр, где стоит много-много компов. Если учесть масштаб соревнования, выделить его на субботу и воскресенье не составит проблем, тем более что аудиторий там много и не все их придется бронировать. А единственное ПО, которое необходимо на этих компах — VMWare Client. Через него участники подсоединяются к заранее подготовленным виртуальным машинам, где уже стоят все возможные IDE. Серверы, на которых крутятся виртуальные машины, очень быстрые, так что все отлично работает. Вроде бы проблем мы с этой технологией еще не испытывали :)
Мне известен хотя бы один случай отказа.
Жюри нашего ЧФ старается сделать набор задач разнообразным как по сложности, так и по тематике. Каждый может лично убедиться в том, удается это нам или нет, посмотрев задачи последних четвертьфиналов.
Что же касается подготовки, то она, безусловно, везде немножко отличается. При полном отсутствии единых подходов каждый готовится (или готовит других) как умеет. Мы никогда не дадим задачу на какие-то совсем специальные знания. А уж если вы дошли до выхода в финал, не зная, что такое ним, то причина этого — пробелы в вашей подготовке. И мы в этом не виноваты.
Ну а в чем же такая большая специфика нашей тестирующей системы? Она радикально отличается вердиктами или функциональностью?
Все системы немножко отличаются. Простой пример
Никаких проблем с MLE на Timus. А что у вас? А как я могу это проверить?
А что вы считаете специальными знаниями? Про ним я немножко ошибся на год, но ним, извините, в университете у нас не проходят. Связь томографического преобразования и преобразования Фурье — специальное или не специальное знание? Приближенный поиск цены антагонистической игры? Классы Поста (привет, отборочный всесиба)? Устойчивые алгоритмы решения СЛАУ? Где граница?
Возможно, на пробном туре?
Возможно, на пробном туре поздно узнать, что с десяток моих реализаций надо переделывать?
Upd. Когда-то в Казани я столкнулся с тем, что не всегда это не дает MLE, и для меня это было откровением. Хорошо, что у них был пробный тур с задачами и я просто случайно это написал.
А разве я говорил, что все тестирующие системы одинаковые? Не надо включать капитана тогда, когда это не требуется. Приведенный пример иллюстрирует самое принципиальное различие? Кстати, я понятия не имею, какой вердикт будет на тестирующей системе ЧФ. Мне кажется, что пример искусственный и адекватная команда ничего подобного на контесте не напишет, а следовательно, не пострадает от каких-то там мелких различий.
Кроме того, тестирующая система ЧФ отличается от той, на которой тренируются наши студенты. И даже написана другими людьми. И проверяющие компы другие. На этой системе саратовские команды пишут ровно один контест в год.
Пример: пишем минимумы на отрезках.
Эта индусятина настолько очевидна и быстро пишется, что единственная проблема — количество памяти, которую она сожрет. Тимус скажет, что существенно меньше 80МБ. Разумеется, можно задавать int *x[20]; и выделять память по слоям, но это скучно, лишний код и возможная ошибка.
Кстати, будь добр, напомни мне задачу на технически сложную реализацию (похожую на NEERC 2010, H или NEERC 2007, E)
Это мне вопрос? А когда шла речь о технически сложных задачах?
Речь шла о разнообразных по тематике задачах. Эту тематику я не помню на ЧФ, хотя она, как видно, минимум дважды представлена на NEERC. Что характерно, обе эти задачи у команд Саратова вызывали определенные сложности.
Эти задачи не подходят под твое определение?
Раз, два, три.
И потом, технически сложной может быть задача почти любой тематики.
Прекрасно помню эти задачи с полуфиналов, с ними были проблемы у многих команд. Насчет твоих характерных выводов не согласен.
UPD: поправил ссылки.
Ссылки не работают. Названия / прямые в архив можно?
Upd. спасибо, прекрасно помню эти задачи! Я, вероятно, не очень точно выразил тип задачи. Обе этих задачи NEERC характеризуются кэпской идеей "закодить условие" и не содержат каких-либо дополнительных идей, кроме того, что кодить условие — это много букв.
Задачи Kakuro и Cyclic Troubles явно отличаются это этого. В задаче Kakuro надо написать польский перебор, т.е. оптимизировать константу до посинения. В задаче Cyclic Troubles надо придумать эффективную идею match-инга строк, и, опять же, либо решение с бинарным возведением пишется не очень долго, либо надо придумывать эффективную по константе линию. Задача Bencoding — это то, что я имел ввиду, с одной разницей — на вид она очень простая. Рекурсивный парсер списков/мапов/интов с передачей в глубь макс.длины (-1 кроме мапы с нечетными item, у которой -3) не выглядит хоть немного сложным.
Задачи с полуфиналов тоже не были неподъемными. Так что с тематикой у нас все в порядке.
Я конечно тоже не специалист по матстату, но что-то мне подсказывает, что 6 точек "выше линии" против 6 точек "не выше линии" — довольно слабое основание для каких-либо выводов :)
А вообще — я не удивился бы, если бы это было так: на саратовских ЧФ саратовские задачи, и саратовские команды их решают лучше. Если эта гипотеза верна — то эффект должен быть ещё сильнее для Урала и заметно слабее для Москвы (там довольно существенная ротация авторов). Кому не лень — могут это проверить.
Последний Уральский ЧФ (2011 года) не подтверждает. Более ранние сложны для анализа (нет фамилий).
За эти несколько часов я не узнал больше о матстате, но мне кажется странным считать игрока, сыгравшего +7=6-2 без форы, равным по силе его сопернику.
Как по мне, шахматы менее дисперсионны, чем АСМ, так что пример не весьма удачный. Ну и в данном случае выборка слишком маленькая.
Выборку больше построить невозможно из очевидных соображений. Дисперсия должна бы более или менее симметрично делать, но это не наблюдается. Замечание о необходимости построить относительное выступление всех команд и посмотреть, насколько меняется относительный порядок остальных команд, принято. Правда, вероятно, для остальных команд будет с точностью до наоборот — из 17 остальных команд верхней восьмерки ЧФ будут писать хуже, чем NEERC, минимум 7 команд.
Из очевидных соображений выборку больше построить вполне возможно — если достать данные по всем остальным четвертьфиналам. Все равно будет не очень много, но заметно больше, чем в данном случае.
А диспа дала бы симметричную картинку с широким/узким разбросом в случае большой выборки. У нас же что-то похожее на "повезло/не повезло".
У меня на прошлой недели была сессия в покер, во время которой в 5 из 7 случаев в PFAI моя оверпара проиграла более низкой паре. Кто не знаком с холдемом — в каждом случае мои шансы на победу были примерно 80%. Да, по результату сессии у меня был недобор в 350бб, но ведь я не стану делать на основании этого предположение, что дамы круче тузов.
Это пример приблизительно такого же уровня. Точно так же можно выводить на основании выборки такого порядка закономерности относительно того, кто круче — рожденные зимой или летом. Да, я не против, интересно и забавно такое читать, только не серьезно это.
Посчитал дальше по четвертьфиналам.
Если ты придумаешь хорошую модель выступления команд, можно проверить влияние следующего фактора модели: на самом деле, при равной силе команд такой эффект может наблюдаться как ложный. Действительно, если из 3-4 команд равных по силе дальше проходит две, то кажущийся результат после отбора этих команд будет ниже.
Upd. И в последнем случае такой же эффект должен наблюдаться на ЧФ в СПб. Надо будет его посчитать.
На чф 2011 года жюри поправили тесты в задаче H за 3 минуты до конца контеста. Поэтому результаты получилось неадекватными, и их учитывать в статистике не надо.
Почему включены только последние 4 года? Что помешало сделать статистику за последние, например, 10 лет? По крайней мере, можно было бы включить предыдущий 2007 год, в котором саратовцы не заняли первое место ни на четвертьфинале, ни на полуфинале. Неужели данные прошлых лет портят подмеченную закономерность? Проблем с тем, чтобы найти результаты старых контестов, тоже вроде быть не должно — тебе известен его email...
Если ничего не путаю, то
Статистика 2003-2007 года 7 лучше ЧФ, 5 одинаково, 2 лучше NEERC.
Итого 14 лучше ЧФ, 11 одинаково, 4 лучше NEERC.
Более ранних данных у меня нет.
На Snarknews есть статистика по сравнению результатов команд NEERC на полуфиналах и финалах: http://finals.snarknews.info/index.cgi?data=stat/neercstat&class=final2012&year=2012
(нужно промотать вниз до раздела "Сравнение выступлений команд вузов-финалистов в полуфиналах и финалах")
В частности, Саратов на финалах выступает в среднем лучше, чем на полуфиналах.
Возможно, это связано с тем, что авторы четвертьфиналов в Саратове всегда старались делать контесты более похожими на финал, чем на полуфинал.
Главную фичу финала — "multiple test data" в неизвестном количестве и многобукав условия и инпута — на ЧФ я не помню. А в остальном не очень ясно, в чем разница.
На финалах обычно нет задач на знание особо сложных алгоритмов и в среднем побольше задач на перебор/реализацию. Ну или по крайней мере так было несколько лет назад :)
Табличка какая-то поломанная. Кроме того, финал кардинально отличается по средам от полуфинала, в отличие от разницы между полуфиналом и четвертьфиналом. Например, на финале нет вижака, а плагин Eclipse так крут, что мы зря не писали в блокноте. Кроме того, на финале не говорят номер теста с ошибкой и не очень очевидный TL. Все это определенно меняет результаты команд.
Upd. Учитывая последний результат (-2.5), получаем в среднем +6.5 за 9 участий. Не то, чтобы явно лучше, учитывая "+7" в 2004/2005 году.
Да, эклипс ужасен, особенно дебаггер. Но мы перед финалом несколько месяцев целенаправлено тренировались писать в эклипсе (и вообще с сайта финала всегда можно скачать полный образ линукса, который будет использоваться). Так что проблема решаема.
Имхо фактор нервов гораздо более значимый :) Например в том же Саратове, насколько я могу судить, на четвертьфинале обычно более-менее понятно, какие три команды поедут на полуфинал. А вот за попадание в финал приходится понервничать. Зато уж на финале никто не ожидает золотых медалей каждый год, поэтому может быть чуть попроще.
Вы счастливые, у вас была возможность тренироваться :)
У нас получилось, что финал в феврале, а диплом у меня в феврале. Петрозаводск в декабре, а следующий отпуск на работе у меня не раньше января. В итоге первую командную тренировку после NEERC мы провели на пробном туре финала, и не заметили, насколько автодополнение } тормозит мне набор.
Понервничать за попадание в финал — да, и поэтому мы на NEERC за 100 минут до конца вместо того, чтобы писать по-честному одну задачу и готовить следующую, сели все втроем за компьютер, написали одну задачу так, чтобы она не могла не зайти, получили Accepted и стали думать дальше. Потому что на финал нам 99.99% хватало одной задачи. Как оказалось потом, можно было даже ее не решать.
Кстати, а много тут людей, кому автодополнение фигурной скобки тормозит набор?
Мне почему то кажется, что такой человек один на всей планете...Окей, вас уже трое. Немало.Мне тормозит набор. На финале мы первым же делом отключили его.
Если человек привык, что ее нужно ставить самому, то да, он тратит время на то, чтобы ее поставить, заметить, стереть обратно. Часто встречаю ругающихся на это.
Мне. Терпеть его не могу.
Нормальная среда должна и ставить и заменять если программист её сам ставит... а то хочется экран снести нафиг =)
Можно линк, пожалуйста? Я нашёл только информацию о компиляторах и средах.(Вероятно, я слепой или английский не позволяет лезть в дебри сайта).
http://pc2.ecs.baylor.edu/ImageBuildInstructions.2012.html
Кажется вот это. Найдено за 3 секунды по запросу "acm icpc download linux image".
Прошу прощения, ступил Искал "acm icpс linux". Спасибо