вегетарианец

Насколько мне помнится (поправьте, если вру), “сидит автор и руками жмет accepted” было раньше. Начиная с 2010 года используется полностью автоматическая система, разработанная в KTH (Королевский технологический институт, Швеция). Поэтому вердикты приходят достаточно быстро.

Саратов — эпик слив…

Известно, кто-нибудь сдал что-нибудь после заморозки?

На топкодере он есть.

Так вот Сергей как раз интересуется, какова роль конкретно этого человека. Ни в коем случае не намекая, что он бесполезен. Мне тоже любопытен ответ на его вопрос.

Удачи, Saratov SU #2! Завтра будем за вас болеть. Рвите всех.

В соответствии с нормативными документами (например, [этим]("http://cqc.spbstu.ru/zn_baza/zak_pol/zak_pol/postanov638(25-08-08).pdf")), иностранные граждане могут учиться в российских вузах на бюджетной основе в пределах некоторой квоты. Насколько это реализуемо в конкретном случае — лучше уточнить, позвонив международный отдел интересующего вуза. Вообще лично знаю некоторых студентов в СГУ, не имеющих российского гражданства.

Вообще если главный приоритет — acm-команда, ничего более удачного, чем Саратовский государственный университет не найдешь. Особенно учитывая твой пока не очень высокий уровень. У нас даже многие вообще не занимавшиеся в школе выбиваются в люди. С политологиями-экологиями тоже все ок. Единственный недостаток — это не Украина)

Вот говорить об этом как раз следует. Как показывает практика, на codeforces можно удачно найти команду. Тем не менее, хочется надеяться, что хорошее образование для человека — тоже важный фактор.

Однако дали всего 90. Так что иногда и первое место бывает заинтересовано в нерейтинговости раунда)

В div2 была эта задача)

Если добавлять Азов — то нам, пожалуйста, с АС по E)

А если серьезно, неправильное авторское решение по задаче, которую активно решали участники — это повод сделать раунд безусловно незачетным. И неважно, как изменился монитор, если добавить/убрать АС.

Это существенно на поведение не менее 14 команд в последние 2-3 часа контеста. Если бы этой задачи не было вообще или если бы по ней были правильные тесты, кто-то бы не отлаживал правильный код, а решал другие задачи. И монитор мог бы быть совсем другим. Это не говоря про такие команды, как мы, кто не стал браться за эту задачу.

После такого надо делать незачетный этап. Мы, например, видели, что у всех по этой задаче минус, и не решали ее. Другие много времени потратили.

Мы писали быстрое преобразование Фурье. Пусть наше число a₀a₁…a_n - 1. Тогда ответ равен сумме всех попарных произведений цифр a_ia_j, умноженных на некоторые степени десятки. А именно, a_ia_i + k умножается на 10^{n - 1 - k}. Нужно быстро уметь считать сумму . Это можно сделать, перемножив два многочлена с коэффициентами (a₀, a₁, …, a_n - 1, a₀, a₁, …, a_n - 1) и (a_n - 1, …, a₁, a₀) и внимательно изучив коэффициенты получившегося произведения.

http://code.google.com/codejam/contests.html

Не участвовал раньше в кубке — это хорошо с той стороны, что я могу просто включить тебя в команду Saratov SU Retired и никакая другая команда при этом не пострадает) Поэтому если есть желание и возможность участвовать в “строенном” этапе — пиши.

А вам с Пашей и с Игорем тогда не скучно будет?) Компьютер-то всего один.

Тем более, лидеры сдали не все. И до самого конца контеста шли турниры по хоккею и WW3. Поэтому появление задачи М скорее было запланировано. Для нашей команды оно было очень своевременным. Мы как раз спорили, что нам решать, а тут — новая задача :)

Меня наиболее устроит вариант: раунд нерейтинговый, из раундов 2B и 2C выходят по 75 участников)

Потому что если у нас есть неразделенная группа из n лампочек, то ее решить за log n округленный вверх.

Я 300 свалила тестом switches = {YYNNNY, YYYNNN}, lamps = {YNNNYY, YYYNNN}. Должен быть ответ -1, т.к. получается, что одному выключателю соответствуют две лампочки и наоборот.

Я как раз про то, что в любой ситуации желающие найдутся. У разных людей разные приоритеты. Вот увидишь, 50 человек наберется :)

А я уверена, что есть люди, кто это представляет. Например, мне как-то позвонили и сказали: “сегодня идешь, берешь билет на самолет, завтра утром летишь в Москву к президенту”. Я отказалась по принципиальным соображениям. Но ведь были люди, которые туда прилетели, в том числе был кто-то вместо меня (кого позвали уже вечером в тот день, когда я отказалась).

Переносить финал сейчас будет максимально некрасиво, потому что

1) кто-то уже берет билеты,

2) кто-то не участвовал в отборе, потому что был уверен, что не сможет поехать.

Спасибо за понимание.

Все равно убери его.

И убери выделение синим третьей строчки. Иначе см. мой самый первый комментарий по этой теме.

С rng_58 чит. Там название начинается не со “Спортивного программирования”.

Нужно добавить еще колонку “удалено администрацией/по просьбе администрации”.

Ну, в первое место грех не тыкнуть) Поздравляю!

Вроде стало понятно, как посчитать количество решений системы по произвольному модулю вида p^k. Будем делать Гаусса с выбором главного элемента по всей матрице. В качестве главного элемента выбираем такой, который делится на наименьшую степень p. Получаем, что каждая правая-нижняя квадратная подматрица делится на ту же степень p, что и главный элемент. Если в столбце свободных коэффициентов что-то не делится — ответ 0. Иначе после завершения прямого хода Гаусса при необходимости дополняем матрицу до квадратной нулевыми строками и перемножаем элементы на главной диагонали (заменяя нули на p^k). Это и будет количество решений системы.

Да, поняла, что это тоже палево.

(Палево) По-видимому, правильно искать количество решений системы по модулю 2 и количество решений тоже по модулю 2 системы, у которой коэффициенты матрицы такие же, а от свободных коэффициентов берутся старшие биты. И перемножать.

Пример: x1 + x2 = 2, x1 + x2 = 0. По модулю 4 система не имеет решений, по модулю 2 у нее два решения. Что-то не так(

Да, так гораздо проще. И поздравляю с рандомными 50$ :)

Вот из-за этой проблемы я и не успела. Но вроде бы, Гаусса делать можно.

На очередном шаге выбираем, какую строчку поставить первой. Если есть строчка с коэффициентом 1 или 3 — отдаем предпочтение ей. Если есть строчки только с двойкой — их можно вычитать друг из друга, ни на что не деля. Прямой ход сделать получилось.

Что касается обратного хода, то там уравнения с первый коэффициентом два накладывают ограничения, что вся остальная часть уравнения должна быть четной. Это приводит к некоторой СЛАУ по модулю два, для которой можно найти количество решений. Еще нужно учитывать, что при делении на два получаются два корня.

Придумала решение по 950, не успела. Посмотрите, похоже ли на правду.

Идея основана на китайской теореме об остатках. Будем решать задачу отдельно по модулям 2 и 5, потом перемножим ответы. Разобьем числа в позициях от 0 до N-1 на две группы: которые попадают в хотя бы один запрос с ненулевым произведением и которые ни в один такой запрос не попадают. Некоторые из чисел второй группы должны быть нулями, чтобы удовлетворить все нулевые запросы. Остальные числа из второй группы могут быть чем угодно, это ни на что не влияет.

Количество вариантов для второй группы считаем динамикой d[i][j] — количество способов расставить числа до i-го, чтобы последний ноль стоял в позиции j. Если у нас не удовлетворяется какой-то нулевой запрос, заканчивающийся в текущем i — перехода не делаем.

Что касается первой группы, то в случае модуля 2 все тривиально — мы должны поставить во все такие позиции 1. В случае модуля 5 записываем систему равенств, которую получаем из ненулевых запросов. Берем дискретный логарифм -> приходим к СЛАУ, количество решений которой определяем Гауссом.

Ответы для первой и второй групп перемножаем.

Идем последовательно по символам строки a и ищем их позиции в строке b. Если позиция текущего символа меньше позиции предыдущего — увеличиваем ее на длину строки b. Потом идем двумя указателями, чтобы разница в позициях не превосходила длину строки b.

Если бы копирование решения задачи 643 с олимпа или копирование минкоста с e-maxx считалось бы читерством — тогда запросто) Однако, по-видимому, не считается.

А что будет с Опенкапом? Он тоже будет в понедельник?

Тут смотря какую цель ставить перед SLR. Если это просто рассматривать как развлечение в выходные — тогда все ОК, кто не хочет — развлекайтесь по-своему. А вот если он проводится как этап отбора в официальном турнире с призами и онсайтом — это совсем другое дело. Красть у людей время становится не так стыдно (вспомним VK Cup 2012 Уайлд-кард раунд 2) и при этом возникает дополнительная ответственность за качество раунда.

Два или четыре часа — непринципиально, когда есть одна задача на поиск в ширину. Кто знает поиск в ширину и умеет применять — напишет за 2, кто не знает — не напишет за 4. В SLR человек может протупить первые 2 часа, но потом немного освоиться с языком и все быстро порешать. Это мое субъективное мнение, хотя не исключено его совпадение с чьим-нибудь еще.

Господа минусующие, теряюсь в догадках, что вам не понравилось: что я посочувствовала студентам СГАУ, или вы рады возвращению промежуточной аттестации, или зря я ее вообще сюда приплела?..

У меня так же получилось с VK Round 1. К счастью, там был wildcard…

Бедненькие!

У нас все не так плохо, хотя сегодня вот узнала, что промежуточную аттестацию вернули. Ее в прошлом семестре отменили за ненадобностью, теперь вот снова решили ввести(

Что-то многовато насчитал) Я по тренировкам на универе и ssutrain04 наблюдаю 25 человек 2+ и примерно 18 человек нового набора.

Я хочу внести предложение — делать SLR подлиннее, хотя бы 4 часа вместо 2-х. Не у всех конечно, но лично у меня а wildcard’е очень остро ощущалась нехватка времени. Потому что за 2 часа нужно успеть вникнуть в непривычную парадигму языка, в его синтаксис, возможно, поизучать стандартные библиотеки, а еще решить несколько задач, помучившись с ошибками компиляции. Для тех, кто по природе тугодум — очень серьезное испытание. Как только начинаешь понимать что-то в языке — контест заканчивается.

Тем более, я полностью согласна с Alex_KPR, отписавшимся выше. Посмотрите для примера на решения неофициального победителя последнего SLR nab. У него самое длинное решение — 4 (!) строчки кода. Безусловно, он молодец, но разве можно называть это программированием?! Если бы времени было побольше — можно было бы добавить в проблемсет задач, в которых можно чего-то посерьезнее написать, строчек на 20-30 хотя бы. Мне кажется, сильным участникам было бы интересно побороться с такими задачами, а у более слабых будет шанс за это время сдать хоть что-нибудь)

Разумеется, вижу основной недостаток своего предложения — не у всех найдется 4-5 часов времени на участие в SLR. С другой стороны, автор при тех же затратах сил на изучение языка и приспособление его к проведению раунда доставит в 2 раза больше удовольствия тем, кто примет участие.

Не порти мне рекламу.

Могу с уверенностью сказать, что из СГУ по причинам занятий acm-мом еще никого не отчисляли. Выбирайте правильный вуз!

За первый час ее сдали еще две команды, а на втором часу стали сдавать все подряд.

Да, и по поводу задачи D с ICL: имхо, она не из самых простых, потому что 1) у нее большое условие с картинкой, 2) там можно накосячить с какими-нибудь случаями, ее далеко не все сдавали с плюса. На GP ICL ее стали сдавать примерно на 40-й минуте, что вполне отражает уровень этой задачи и подтверждает мои соображения о представительности монитора.

Тут важно, насколько представителен монитор. На таких соревнованиях, как полуфинал, петрозаводские сборы, открытый кубок, монитор достаточно представителен, чтобы командам из нижней его половины в точности идти за монитором. Я считаю, что это безусловно правильная тактика для новичков. Особенно если новички не обладают исключительными способностями к решению суровой математики или пропихиванию палева. Ну и разумеется, нужно уметь оставлять задачу, которую все сдают, а вы в течение 3 часов сдать не можете.

Другое дело, менее представительные соревнования. Где есть сильные команды и сложные задачи, но их немного. Особенно сказывается, когда все участники имеют определенный уклон в их подготовке (например, все из одного вуза). Тогда какая-то задача может оказаться незамеченной или поздно замеченной, и вообще порядок решения задач может оказаться неразумным. Такое регулярно происходит на наших четвертьфиналах. Народ как правило предпочитает реализацию идейным задачам. Если найдется кто-то, кто захочет чуть побольше подумать, чтобы потом меньше писать — у него будет преимущество. На таких соревнованиях надо читать все задачи. Особенно тем, кто на что-то претендует.

Actually, ‘+’ doesn’t mean only one submission. Submissions with WA on test 1 are not counted.

Немножко неприятно, что “неизвестные” языки раньше уже фигурировали непосредственно на Codeforces. Получается сюрприз только для тех, кто регулярно не участвует в SLR, не следит за прогопедией и вообще за деятельностью Nickolas.

Вопрос про Intercal: там играло роль, в каком регистре выводится название языка?

INTERCAL

Стало лень думать… Хочется разбора!

But I made too many iterations and got TL :)

Мы для каждого числа считали p[i] — расстояние до предыдущего такого же и затем d[i] — количество предыдущих p[j], совпадающих с нашим p[i]. Кроме того, дерево отрезков с максимумом из i — p[i]. Затем в онлайне отвечали на запросы. Может быть, можно как-то проще, если в оффлайне.

Разбалловка по задачам?..

Хочется еще отметить, что в условии задачи Е не были перечислены шахматные фигуры и правила, по которым они ходят. На наш вопрос “Какие шахматные фигуры могут быть” нам ответили “все”, что весьма невнятно. Например, вообще непонятно про пешек, мы долго ломали над ними голову. После разбора второго теста (который немаленький) все, правда, стало понятно. Однако в итоге обнаружился неприятный баг со слонами.

Мнение мое личное и многих участников из нашего сектора (в том числе видавшего виды бывшего координатора задач на Codeforces RAD): в подобных задачах нужно подробно пояснять, какие есть фигуры и как они ходят. Не все acm-щики играют в шахматы. Участники не должны использовать все свое воображение, чтобы додуматься, чего хотели авторы задачи. А такие условия вызывают массу вопросов и недовольства.

Таганрог = Опенкап для всех остальных.

На тему номера один. Во-время-контестный разговор. Опенкап. Я в скайпе, Дима пишет из ЦОППа.

– Возникла идея выводить всегда, кроме сэмпла, -1

– Су3 сейчас это пишут. Подождем, посмотрим на результат. Сами всегда написать успеем

Есть еще ‘rem’

Ну, меня, например, все устраивает. Так что “хорошо, попробую пройти” :)

За несколько суток можно исправить баги и даже поменять правила в процессе раунда :) Так что здесь эксперименты более вероятны. Я тоже думаю, что будет марафон.

В количестве)

У нас в СГУ такие (спорные) методы использовались и, скорее всего, до сих пор используются при отборе на курсы по Java и C++, которые отобранным людям оплачиваются. Довольно адекватных людей набирали.

про формат контеста ничего не гарантируется

Гарантировалось, что будет длиться 2 часа. Из этого почти наверняка следовало, что будет ULR. Добавлять новый вид правил контеста в систему и сразу проводить по ним такое важное соревнование очень рискованно. Тем более, контест совсем короткий и если что-то не так заработает — то все. URL — единственная уже опробованная возможность.

Ой как обидно… Очень надеялась на Париж.

Более подробный список женской аудитории был в прошлом году. И конечно же спасибо поздравителям)

RAD’у, наверное, нет большого смысла писать. Он сам участвовал в соревновании.

Прекрасно, где тогда граница между своим кодом и чужим?

Вот мы с Димой Матовым шаблон пишем одинаково. Я и думаю: кем из нас был написан тот шаблон, который я использовала сегодня :)

Тут вопрос в том, считается ли использование твоих материалов жульничеством (когда человек выдает это за свой собственноручно написанный код).

Нет.

Смысла предпринимать дополнительные усилия разработчикам платформы действительно никакого. Можно просто временно разбанить аккаунт с предупреждением, что анонимусу разрешено только участвовать в VK Cup и ничего больше. Если он начнет бедокурить, то дисквалифицировать его с турнира и заблокировать аккаунт снова. Такой вариант хорош тем, что набедокурить он может с любого аккаунта, а так у него будет шанс нормально поучаствовать и возможно турнир пройдет спокойно.

Утверждение о ручной собачке не имеет под собой никакого реального основания. Даже удивительно, с чего ты взял.

Спасибо, кэп. Негативное мнение Павла о раундах понятно благодаря чему возникает. Непонятно, чем ему лично не угодил анонимус?

На последнем раунде не проявлял, хотя я так ждала.

Оказывается, Е тоже боян.

С I не так то, что она совсем неинтересна участникам, которые ранее встречали точно такую же задачу (с другой легендой, конечно). Она дает таким значительное преимущество.

Мой рейтинг упал только на 3, поэтому нет, не в рейтинге. Дело в том, какую планку ставит себе Codeforces для нормального (= рейтингового) раунда.

На мой взгляд, есть вполне объективные причины, по которым раунд должен был бы быть нерейтинговым. А именно, неправильное условие в задаче С, которое было исправлено на 48 минуте контеста и о котором часть участников узнала даже не сразу после объявления, потому что вместо объявления пришел текст “undefined”. Учитывая, что для div1 это задача C, которую все-таки многие пытались решать, проблема (вероятно) задела значительное количество участников.

В любом случае жду пояснений относительно рейтинговости раунда со стороны авторов или администрации.

А я не почувствовала боянистости ни в одной из задач.

Раунд рейтинговый или нет?

Да, и из-за этого бага я сначала не поняла, к чему вообще это и довольно долго продолжала разбирать дебажный вывод по второму тесту.

У него нет другого ника на cf, под которым он участвует в соревнованиях.

по слухам, есть люди, которые пишут задачи и вовсе бесплатно; не знаю, не пробовала Мне это предложение тоже очень не понравилось.

А мне в последнем предложении не понравилось слово “тоже”. Я не вижу ничего обидного для себя, например, в словах Nickolas. Просто решила осветить тему подготовки контестов с другой стороны, с которой я ее вижу. Совершенно необязательно приобщать мой комментарий к своим спорным мнениям относительно ее карьеры.

по слухам, есть люди, которые пишут задачи и вовсе бесплатно; не знаю, не пробовала

Лично я много задач готовила бесплатно: городские олимпиады школьников, региональный этап ВКОШП, контесты в Петрозаводск, Четвертьфинал. (В последний год это все оплачивалось, но вообще источники финансирования нестабильные). По-видимому, это все отличается от того, о чем пишет Nickolas, еще в и том, что подобные соревнования готовятся авторским коллективом. В студенческие годы это было интересно, потому что возможность проявить себя в новом качестве. Полезно оказаться по другую сторону баррикады. Например, самостоятельное составление тестов к задачам учит видеть логику в тестах жюри и всесторонне тестировать свои решения на контесте. Для ветеранов же подготовка контеста — это повод собраться вместе, в том числе в неформальной обстановке.

Так что материальная составляющая здесь, имхо, далеко не самое важное. Хотя, конечно, лучше, чтобы она была и побольше :)

Поздравляю RAD с победой в СРМе!

А у меня один человек делал так. Если строка имеет вид x.y, то он добавлял тот конец, который больше.

Да, причем это лучше делать в самом конце, а не в переходах динамики.

Да. Нужно только учитывать кратные ребра.