Приглашаем вас поучаствовать в Кубке трёх четвертьфиналов — 2014 — командном онлайн-соревновании, которое будет проводиться параллельно с четвертьфиналами ACM в Москве, Минске и Санкт-Петербурге в конце октября — начале ноября. Турнир будет организован совместными усилиями команды Яндекс.Контест и жюри перечисленных четвертьфиналов ACM ICPC. Даты и времена проведения: Московский ЧФ (регистрация) — 26 октября, 11:30 по Москве, Западный ЧФ — 06 ноября, 12:00 по Москве, ЧФ в Санкт-Петербурге — 08 ноября в 12:30 по Москве.
Команды, участвующие в официальной версии одного из четвертьфиналов, могут поучаствовать в онлайн-версиях остальных четвертьфиналов. Команды, не участвующие ни в одном из официальных четвертьфиналов, могут принять участие онлайн во всех трех раундах. Результаты каждой команды на всех соревнованиях, официальных и неофициальных, будут учтены, итоговый зачет турнира будет производиться по системе Гран При 30 (версия 2014 года).
Регистрация на онлайн-версию каждого четвертьфинала идёт непрерывно вплоть до старта соревнования. Создать команду в системе Яндекс.Контест вы можете по ссылке Мои команды. Все приглашенные в команду участники должны подтвердить своё участие в соревновании. После успешного создания команды необходимо зарегистрироваться на соревнование, указав вашу команду. Также возможно и индивидуальное участие.
Внимание! Логины, сгенерированные для соревнований Открытого кубка, предназначены только для них и для Кубка трёх четвертьфиналов работать не будут. Чтобы зарегистрироваться в системе Яндекс.Контест, достаточно завести почту на Яндексе.
Правила отдельных раундов совпадают с правилами официальных четвертьфиналов.
Потренироваться сдавать задачи в системе Яндекс.Контест можно, приняв участие в Тестовом соревновании.
UPD официальные результаты МосЧФ
UPD2 Онлайн-трансляция Западного Четвертьфинала уже завтра, в 12:00 MSK!
UPD3 Северный четвертьфинал начнется завтра в 12:30 MSK.
Ух-ты, это же уже вот прямо совсем завтра. Вопрос сообществу, а кто-нибудь имеет опыт/желание собрать в рандоме команду на это дело? Ну или вдруг, есть кто двое и нужен третий? Я вот чисто из интереса хотел бы командно что-нибудь написать. В идеале очно (Питер), можно, наверное и заочно. Замечания про силу несыгранных команд не приветствуются :-)
Один из членов моей команды подтвердил участие в команде после того, как мы уже зарегали команду на соревнование. Теперь он отображается во вкладке участники отдельной командой. Как бы это поправить?
Интересно, как Яндекс относится к переводу времени на "зимнее".
Сейчас время на сервере — 7:36. При этом во всей Москве 6:36.
На какое время ориентироваться нам, простым участникам? :)
серверное время осталось в зоне GMT+4, но время до старта соревнования должно быть актуальным.
Можно ли где-нибудь достать pdf с условиями задач?
Их можно скачать по ссылке "скачать условия" около кнопки "объявления жюри"
Дайте, пожалуйста, прямые ссылки на текущие офиц. результаты ЧФ и результаты трансляции на YC. На сайтах http://acm.msu.ru/ и http://contest.yandex.ru/ я их быстро обнаружить не смог.
Я нашел здесь http://ejudge.cs.msu.ru/stand-qf-2014.html
Спасибо, и пост обновили. Результатов трансляции все еще нет. Печально это.
результаты трансляции там же, где трансляция: http://contest.yandex.ru/QF2014/contest/793/standings/ Но пока что не объединенные с результатами четвертьфинала. Ожидаем.
could you put these three contest into the gym,thanks
I'll do it as soon as I'll get tests.
Почему, когда начинаешь виртуальный контест, то тебя не видно в таблице? Смысл виртуального участия теряется :(
А чего в официальных результатах МосЧФ делает команда "SPbSU Trawa"?
Они вне конкурса участвовали. Как сунц и пр.
Ну это не совсем официальные результаты.
Команды:
AESC-I-1
SPbSU Trawa
MAI (╯°□°)╯︵ ┻━┻
Yaroslavl SU 1 *
Rybinsk SATU Craben *
Вне конкурса писали, они не учитывались при расчете мест и выдаче наград/дипломов.
И тем не менее дипломы дали 16 официальным участникам, а не 20 @_@
Или так и задумано?..
Ну видимо 7 задач отсечка была.
Многие спрашивают, что за название у нас такое.
(╯°□°)╯ -- человечек ︵ -- переворачивает ┻━┻ -- стол
Очевидно же.
Положи. Стол. На место.
А почему вы вне конкурса? Пропускаешь сезон? Помню, ты даже спрашивал здесь недавно по поводу участия с вечернего/заочного обучения:)
Присоединяюсь к вопросу и добавляю еще один — за кого мне теперь на NEERC болеть? :(
А что, нельзя?=)
А ведь и не поспоришь:)
Не, я чисто уточнить, где нынче МКАД заканчивается :)
Вообще говоря, Москва — это то, что за МКАДом.
Всё относительно
Расскажите, кто-нибудь, H и I, пожалуйста.
H:
Переберём вершину, в которую побежит кролик из "корня" (это та вершина, у которой степень больше 2).
Теперь бинпоиск по ответу.
Ответ не может быть меньше, чем расстояние от корня до зафиксированной вершины (ну и не больше n, разумеется).
Удалим все вершины, из которых можно добежать до зафиксированной. Тогда граф распался на цепочки, для цепочки с зафиксированным ответом очень легко посчитать необходимое кол-во норок.
Можно чуть-чуть посложнее без перебора вершины.
Давайте найдем наш "корень" и удалим его из графа. У нас граф распадется на циклы и цепочки. Обойдем каждую оставшуюся структуру и сохраним количество вершин в ней и ее тип (цепочка или цикл).
Далее запустим бин. поиск по ответу (d).
При фиксированном d для каждой структурки мы хотим посчитать такую пару: (k, remain), где k = количество вершин, которые мы обязаны в ней покрасить, а remain = количество неокрашенные вершин.
Легко доказать, что:
1) Если в цепочке > d вершин, мы обязаны покрасить какую-либо вершину в цепочке.
2) Если в цикле > 2 * d вершин, мы обязаны покрасить какую-либо вершину в цикле.
Ну и давайте в соответствии с этими двумя принципами обрабатывать каждую структуру.
1) До тех пор, пока в цепочке > d вершин, красим одну и вычитаем из количества вершин 2 * d + 1 (количество достижимых из покрашенной). Возвращать будем (количество покрашенных, оставшееся количество вершин). Внимательный читатель может заметить, что вторая величина может получиться отрицательной. Ее смысл прост = мы покрасили вершину и она покрывает не только эту цепочку, но возможно еще и какие-то вершины выше. Она нам дальше пригодится.
2) До тех пор, пока в цикле > 2 * d вершин, красим одну и вычитаем из количества вершин 2 * d + 1. После такой покраски (может быть нулевой) нас интересует только максимальная длина цепочки, которая осталась на пути из корня. А это c, где c = (количество оставшихся вершин + 1) / 2. Возвращаем (количество покрашенных, c).
В результате таких покрасок, у нас может получиться, что больше ничего красить не нужно. Такое получается, если у нас есть цепочка, в которой мы покрасили вершинку и она покрывает все неокрашенные в других. Проверить это очень просто: возьмем вторые значения из пар, и сумма минимального + максимального из них должна быть строго меньше 0 (мы должны покрыть еще и корень). Иначе, докрасив корень, мы покрываем все оставшиеся неокрашенные вершины.
Ну а дальше суммируем количество окрашенных вершин, если оно < = k, тогда смогли, иначе нет.
Итого: O(n * lg(n)).
На разборе говорилось, что можно за O(n). А кто-нибудь умеет?
А где может ломаться такое решение?
Сначала так же преобразовали наш граф в набор пар (isCycle, length), разобрали случай без "корня" (на него же ответ
). Бинпоиск по d. Так же считаем ответ для цепочек и получившийся "перехлёст". Теперь есть 2 случая, покрыли ли мы корень или нет.
Если корень не покрыт. Если циклов нет, то ставим нору в корень и готово. Если был один цикл — пусть есть расстановка нор на этом цикле, тогда его можно покрутить так, чтобы нора оказалась в корне. Аналогично для нескольких циклов, можно найти тот, который целиком покрывается норами с этого цикла, крутим его до корня. Таким образом, нам всегда выгодно ставить нору в корень в таком случае — ставим, переходим к случаю покрытого корня с "перехлёстом", равным d.
Если корень покрыт. Так же выкидываем покрашенные вершины, граф распадается на цепочки, считаем для каждой отдельно ответ и всё складываем.
Это решение ловит ВА7, но найти ошибку я в нём никак не могу.
Я вот тут выложил тесты, которыми я ловил свои баги, попробуйте проверить, может найдется.
Спасибо за тесты, моё решение на них работает правильно.
Собственно, вот оно http://pastebin.com/FBDAyHN7.
У меня было WA7, когда я не учитывал, что норы из одной цепочки\цикла могут быть использованы в другой цепочке\цикле, то есть я считал ответы для них независимо.
I:
До упора будем спрашивать 2.
однозначно задает пару (x0, P)
Если действительно 2 — ну хорошо :)
Понятно, что
x0·2k = ak·P + xk для некоторых целых ak
Научимся их находить.
a0 = 0
ak + 1·P + xk + 1 = x0·2k + 1 = 2(x0·2k) = 2(ak·P + xk) = (2ak)·P + 2xk
Если 2xk > P, то xk + 1 < xk, и наоборот.
Таким образом, чтобы из ak получить ak + 1, нужно умножить ak на 2, а последний бит выставить исходя из ответа, полученного на запрос.
Отсюда akP < x02k < (ak + 1)P
Или
Дробь
Ну а дробь такая найдется только одна, потому что разность двух разных не меньше, чем
Как найти эту дробь: переберём P, для него бинпоиском найдем x, проверим.
В последние 10 минут переделывал это решение с полного перебора X0, на его бинпоиск. Хотя, возможно, моё решение немного отличается. Я после каждой двойки смотрел все оставшиеся P, смотрел какие у них могут быть X0, проверял подходят ли они до сих пор, хотя можно было и правда, сначала сделать 41 запрос, а потом уже отбросить лишнее. Сдать вовремя не успел, и была куча багов (хотя как куча... был баг, что я забыл, что P может быть равно N — WA20 (хотя не обязательно WA, иногда RE или PE)). Остановился на WA31 и решил, что может это решение недостаточно быстро работает в плане количества запросов.
Доступны ли где-то тесты?
Подскажите как решить G?
Будем решать задачу отдельно для каждой фамилии. Построим ориентированный граф из имён, в котором есть ребро u->v тогда и только тогда, когда во входных данных есть "u son of v".
Посчитаем для каждой вершины D[v] количество вершин в наибольшем пути начинающемся из неё. Если бы в графе не было циклов, то это можно было бы сделать простым дфсом. Заметим, что в каждой компоненте получившегося графа будет не более одного цикла, при этом он всегда будет находиться в конце любого пути. Найдём его, и присвоим для каждой вершины v, входящей в него D[v] = число вершин в цикле. После этого, для нахождения D[v] для остальных вершин в компоненте, будет работать обычный дфс.
Ещё нужно учесть тот факт, что если в компоненте нет цикла, то ответом будет maxD[v] - 1, так как последней вершины в получившемся пути нет в инпуте, поэтому мы не можем её использовать.
Расскажите решение B, пожалуйста
Делим подрывников на две независимых взрывных волны -- вертикальную и горизонтальную, у каждой из них своя вероятность "срабатывания".
Объединяем вертикальные взрывные волны, лежащие на одной вертикали, в одну. Аналигично объединяем горизонтальные волны. Если вероятности взрыва волн обозначить как a1, a2, ..., an, то вероятность "срабатывания" суммарной волны, т.е. если сработает хоть одна из них, вычисляется как A = 1 - (1 - a1)·(1 - a2)·...·(1 - an).
Последний шаг — принцип включения и исключения. Для каждой вертикальной и горизонтальной волны прибавляем к ответу вероятность срабатывания этой волны, умноженную на площадь пересечения этой волны с отрядами врага. Потом надо из ответа исключить посчитанное дважды — точки пересения горизонтальных и вертикальных волн внутри отрядов, умноженные на вероятность срабатывания обеих волн. Сделать это быстрее чем за O(N2) можно заметающей прямой — идём слева направо, у нас могут быть три события: добавить отряд, вертикальная взрывная волна, убрать отряд. Всего для подсчета ответа я использовал две дополнительных переменных: длина пересечения текущей заметающей прямой с отрядами (это для включения в ответ вертикальных волн) и суммарная вероятность срабатывания горизонтальных волн, которые проходят через отряды, пересекаемые текущей заметающей прямой (это для исключения из ответа). Для обновления второй переменной использовал неявное дерево отрезков по горизонтальным линиям для суммирования мат ожиданий. Так же надо не забыть включить в ответ горизонтальные линии сами по себе, это легко делается тем же деревом до начала заметающей прямой.
Я сначала посчитал уничтоженное вертикальными бомбами, а затем перед тем как считать уничтоженное горизонтальными, из ширины каждого отряда вычел уничтоженное вертикальными. Это легко сделать, например, деревом фенвика или вообще частичными суммами предподсчитав мат. ожидание уничтоженной вертикальными бомбами суммарной ширины с x1 до x2.
Вроде у нас было проще.
Что-то типа для каждого столбца/строки знаем P = произведение (1-p) и Q = произаедение (1 — q) Тогда в фиксированной клетке вероятность человека выжить — это PQ события независимы, т.к в клетке с человеком нет бомб).
Теперь у нас есть запросы посчитать на прямоугольнике
Это можно сделать преф суммами, надо только не забывать про то, что если в столбце нет бомб, то это 1, а не 0.
Хороший контест. Авторы креативно подошли к описанию задач. Про ЦРУ, поросёнка? Пётра, который хочет уехать на тракторе за лучшей жизнью, профессор Мофенко, 2048 и проч и проч :)
Great contest, thanks to the organizers! The contest in the Gym: 2014-2015 ACM-ICPC, NEERC, Moscow Subregional Contest.
thanks for providing,and another request,is that available for you to put the Central Subregional 2014 contest into gyms,millions of thanks
а как отменить регистрацию? я случайно нажал "Зарегистрироваться" вместо "Зарегестрировать команду" меня так сразу ни с того ни с сего и зарегистрировали, а хочется все-таки поучаствовать действующей командой
поправила, попробуйте зарегистрироваться еще раз
Судя по всему, два года назад такая кнопка была.
Спасибо :)
а удали еще, пожалуйста, alex.zabashta, он тоже с нами :)
Нет доступных для регистрации команд. Все доступные уже зарегистрированы или Вы не состоите ни в одной команде. Вы можете вступить в команду по приглашению, либо создать свою.
Подскажите, пожалуйста, что делать?
UPD Ну и ладно...Очень надо..
UPD2 И вообще, я на пары давно сходить хотел.
Есть ли где нибудь разбор задач сегодняшнего контеста? Точнее интересуют задачи G и K.
Нужно авторизоваться, чтобы посмотреть задачи.
У вас монитор надо влево-вправо прокручивать, чтоб увидеть все результаты.
А во сколько всё-таки завтра зеркало северного чф? В посте написано, что в 11:00, а здесь, что сам четвертьфинал стартует в 12:00.
Верное замечание. Старт перенесен на 12:30 МСК
А появление суммарной таблички планируется?
Пока что есть только в таком виде. По "похожести имён" склейка ЧФ-Яндекс.Контест сделана.
Поправки на тему "не склеили два результата" принимаются (комментариями к этому посту). Указывать логин, под которым участвовали в Яндекс.Контесте, четвертьфинал и соответствующую команду.
Спасибо.
А правда, что часть команд в топе Минского ЧФ появилась позже? Мне казалось, некоторых я там не видел сразу после контеста.
По поводу склейки: Skird(grafoman96) — это, вероятно, Moscow IPT Jinotega
Fixed
SPb ITMO University 3 (vlad107, izban, Belonogov) (Западный чф) и SPb ITMO University 3 (vlad107, Belonogov, izban) (Московский чф) — одна и та же команда
Fixed
1) На "Third Subregional: Northern Subregional 2014" кнопка регистрации зарегистрировала меня лично, а не команду. Как это исправить?
2) Как изменить флажок страны рядом с моим ником на верный? Настроек в Я.Контесте не нашел. В Я.Паспорте страна указана Беларусь.
Такое ощущение, что там что-то не так с регистрацией на завтра, а может и в общем. Нажал "регистрация" — меня автоматом зарегистрировало, как соло-участника, а хотел командой. Раньше выбор был, только не помню до этой кнопки или где. Я так понимаю по предыдущим сообщениям тут, что я уже не первый на эту тему попался.
Под кнопкой зарегистрироваться еще раньше была кнопка зарегистрировать команду.(в частности, у меня сейчас есть для Московского ЧФ)
BTW: По-моему не очень удобно, что для регистрации 2 кнопки, при этом кнопка зарегистроваться(более заметная) никак не говорит о том, что регистрация личная(а потом еще отменить нельзя)
Same thing, случайно зарегистрировался лично. Для Северного ЧФ кнопки "Зарегистрировать команду" не было.
Кнопку вернули на место. Подскажите, пожалуйста, свой логин, чтобы я убрал для Вас регистрацию. После этого можно будет зарегистрировать команду.
Марат Юлдашев, спасибо.
Done
Убери, пожалуйста, также регистрацию участников nalivayko.nick и Aliaksei, чтобы тоже смогли зарегистрироваться командой.
Done
Спасибо.
У qwaker.00 еще отмените, пожалуйста
Разрегистрируйте, пожалуйста, Александра Останина, а вместо этого зарегистрируйте Moscow IPT Ababahalamaha
Tomorrow there also is Georgian subregional. Can we have it online somewhere?
All subregionals tomorrow will have the same problems
Really, not all: Far Eastern and West Siberian will have their own problemsets.
Если я сейчас создал команду, но в ней пока я один. Я могу зарегистрироваться, а потом пригласить в команду людей, они будут отображены в мониторе?
нет, при регистрации вы указываете состав "играющей" команды
Is the final result of Northern QF available now? I'm very eager to see whether tourist's team has solved the last problem
Yes.
Суммарную табличку в яндекс.контесте разморозят? Результаты ЧФ уже есть.
ИТМО 1 стал в Западном четвертьфинале отображаться с 11 задачами, как в Северном. Вроде, и другие Питерские команды тоже затронуло. скрин
Хм, а нам норм. Может так и оставим? =)
Работаем над этим, суммарная табличка не затронута, постараемся оперативно поправить.
А это правда, что в сегодня в трансляции на Яндекс.Контесте был какой-то тихий реджадж? Моя команда говорит, что без каких-либо объявлений вердикт сменился с WA1 на OK.