Приглашаем вас поучаствовать в Кубке трёх четвертьфиналов — 2015 — командном онлайн-соревновании, которое будет проводиться параллельно с четвертьфиналами ACM в Москве, Минске и Санкт-Петербурге. Турнир будет организован совместными усилиями команды Яндекс.Контест и жюри перечисленных четвертьфиналов ACM ICPC. Даты и времена проведения: Московский ЧФ — 18 октября, 12:00 по Москве, ЧФ в Санкт-Петербурге — 24 октября в 13:00 по Москве, Минский ЧФ — 04 ноября, 18:00 по Москве.
Команды, участвующие в официальной версии одного из четвертьфиналов, могут поучаствовать в онлайн-версиях остальных четвертьфиналов. Команды, не участвующие ни в одном из официальных четвертьфиналов, могут принять участие онлайн во всех трех раундах. Результаты каждой команды на всех соревнованиях, официальных и неофициальных, будут учтены, итоговый зачет турнира будет производиться по системе Гран При 30.
Регистрация на онлайн-версию каждого четвертьфинала идёт непрерывно вплоть до старта соревнования. Создать команду в системе Яндекс.Контест вы можете по ссылке Команды. Все приглашенные в команду участники должны подтвердить своё участие в соревновании. После успешного создания команды необходимо зарегистрироваться на соревнование, указав вашу команду. Также возможно и индивидуальное участие.
Правила отдельных раундов совпадают с правилами официальных четвертьфиналов.
Потренироваться сдавать задачи в системе Яндекс.Контест можно, приняв участие в Тестовом соревновании.
UPD: Регистрация на МосЧФ открыта. Не забудьте принять приглашения в команды, чтобы участвовать.
UPD2: мы рекомендуем не смотреть текущие результаты МосЧФ, если вы хотите решать зеркало ;)
UPD3: открыта регистрация на Северный ЧФ. Чтобы участвовать командой сначала создайте команду и примите в неё приглашения, потом зарегистрируйтесь от имени команды.
UPD4: открыта регистрация на Западный ЧФ!
Если бы инфа об этом была бы пораньше... Понятно, что можно было догадаться.
Или где-то было объявление/расписание?
Прости, пожалуйста =( Я постараюсь в следующем году пораньше объявить, а контесты все равно будут доступны для виртуального участия.
Подскажите, когда и где ЧФ мск станет доступен для виртуального участия ? Спасибо. Если где-то ниже инфа освещалась, прощу прощения, не рискнул читать ветку ибо спойлеры.
Уже выложили в тренировки на coceforces
https://contest.yandex.ru/QF2015/contest/1635/enter/
или нажмите на слова Московский ЧФ в анонсе
Почему в Яндекс.Контесте нет возможности дорешки без участия в виртуальном турнире? Т.е. если я знаю задачи или не хочу участвовать виртуально у меня нет возможности просто дорешать задачи — единственное что я могу это стартовать соревнование виртуально? разве это логично?
I was trying to register as a team but in the process I registered individually. How can I now register as a team ? Is it possible to cancel my participation as it is possible in Codeforces ?
Same problem.
send a feedback message with that request, we'll cancel your individual registration promptly
Yandex competing with Codeforces for "Most Delayed Contest Platform" award.
Как решать G и K?
K: давайте посмотрим на задачу с конца, а именно посмотрим на все стоки. Где должен стоять сток с наибольшим номером? Очевидно, на последней позиции (так как стоки можно переставлять, можно поменять его со стоком, стоящим на последней позиции и улучшить ответ). Будем поддерживать сет стоков, удалять сток с наибольшим номером, пересчитывать число исходящих рёбер у его предков, и, возможно добавлять их в сет. Таким образом получили решение за
.
За
всё же, думаю
G: расстояние между точками (x1, y1) и (x2, y2) — это
. Переберём, где стоит 
, пройдём сканлайном слева направо, поддерживая точку с минимальным 
и обновляя с помощью неё ответ.
Альтернатива по G — решим точно так же, как обычную задачу поиска наиболее удаленных точек (выпуклая оболочка + указатели), только расстояние будем считать так, как описано в условии.
Как доказать?
Если вспомнить что с обычной метрикой мы можем построить выпуклую оболочку как набор внешних точек на линиях аля x cos(a) + y sin(a), т.е. мы этими линиями облепляем нашу фигуру.
Здесь доступных углов всего 8, соответственно и будет на них не более 8 точек (если попадает несколько, то можем взять любую), а из них можно сделать квадратную проверку.
Также легко показать, что обычная выпуклая оболочка будет внутри выпуклой оболочки построенной по такой метрике, но там за квадрат нельзя будет искать макс. расстояние, а метод двух указателей вроде работать не будет.
У нас зашло в дорешку, но непонятно, как такое работает.
Чтобы можно было использовать 2 указателя (или тернарник), функция расстояний от фиксированной точки до остальных должна быть выпуклой по идее.
Рассмотрим пример с точками: O(0, 0), A( - 3, 5), B(0, 6), C(3, 5).
Пусть мы хотим найти самую удаленную точку от точки O.
Тогда если измерять в Евклидовой метрике, всё будет хорошо, функция расстояний будет выпуклой: {5.83, 6, 5.83}.
Если измерять в заданной метрике, то функция расстояний будет вогнутой: {6.24, 6, 6.24}.
Мы не стали писать такое, потому что думали, что не зайдет...
В общем, почему оно работает? :)
Не уверен, что понял, в чем суть вопроса.
Если что — я это доказывать не умею (не пробовал — решил сабмитом проверить, там ведь писать вообще чуть-чуть). Надо вспомнить, как доказывается для Евклидовой — может и здесь так получится)
Функция расстояний — это такая дискретная штука, описывающая расстояния от текущей вершины до остальных в порядке обхода? Она и в Евклидовой не обязана быть выпуклой. Возьми правильный 2*N-угольник (вписанный в окружность), разрежь его пополам, добавь еще одну вершину в центре этой описанной окружности и по одной в каждом круговом сегменте. Расстояние от "центральной" вершины к каждой из старых вершин будет равно R, а расстояние от нее к новым вершинам будет меньше R (потому что они внутри круга). Получается настолько немонотонная и невыпуклая функция, насколько это вообще возможно — последовательность расстояний будет пилообразной :)
Ну или даже на твоем примере — подтяни точку В ближе (напр., в 5.5 вместо 6) и в Евклидовой метрике все перестанет быть выпуклым.
Точно, почему-то раньше мне это не казалось очевидным =)
Действительно, если подтянуть точку B в (0, 5.5), то будет {5.83, 5.5, 5.83} в Евклидовой метрике. Получается, тернарник нельзя запускать, из-за того, что функция может быть пилообразная.
Интересно, как он вообще прошел в этой задаче тогда :)
Доказывать нужно через "возьмем интересные направления". Мы на контесте вспомнили доказательство, оно не распространяется на эту задачу.
Сканлайн не нужен. Выберем 8 лучших точек по скалярному произведению с векторами (1, sqrt(2) — 1), (sqrt(2) — 1, 1) и еще 6 таких же векторов с минусами в нужных местах.
Просто попробуем посоставлять пары из каждой из n точек с выбранными 8. Выберем лучшую.
Почему это работает? Почему такие вектора? Какой смысл у произведений?
При умножении на эти вектора получается ровно та формула, которую я написал.
UPD. Только там, похоже, должно быть не
, а 
.
Косяк, исправил.
А это как доказать?
Сначала нужно показать, что расстояние между двумя точками — это всегда максимум из скалярных произведений описанных выше векторов на (dx; dy).
Дальше как в манхэттенском расстоянии. Зафиксируем точку j, и найдем точку i с максимальным (xi — xj) * mulx + (yi — yj) * muly по всем парам (mulx; muly). Для этого можно найти максимум по каждой паре в отдельности, а потом взять максимум из найденных 12 точек. Но при поиске максимума по каждой паре в отдельности -xj * mulx и -yj * muly можно выкинуть как константы.
UPD: произведений на самом деле 8, потому что пары с двумя единицами нам не нужны, как и пары с двумя корнями.
E, B?
E: Запишем, сколько прибавляют к сумме все такие перестановки, в которых А и В встретятся на уровне Х и А победит. Необходимо посчитать число таких перестановок :) Для этого надо выбрать 2X - 1 чуваков после B, еще 2X - 1 чуваков среди всех остальных после А, а также позицию этой игры среди всех игр выбраного уровня, а дальше поумножать все на нужные цэшки/факториалы. Это дает нам наивное решение; чтобы проапдейтить его, достаточно заметить, что все хорошо группируется — каждый множитель зависит либо от А, либо от В, но не от обеих сразу. Погруппируем, посчитаем сумму по всем парам по всем уровням, в конце поделим на факториал.
Наверное, с кодом будет понятнее: link.
B: Удвоим строку A, теперь нужно найти такие D, E, что A + A = ... + D + ... + E + ..., причем E + D = C и расстояние от начала D до конца E максимально, но не больше len(A). Переберем начало E, утверждается, что можно взять максимальный префикс C, который можно набрать с данного места (иначе можно перекинуть символ из начала D в конец E). Это z-функция в данной позиции. Теперь мы знаем D, нужно найти наиболее раннее вхождение D на каком-то отрезке. Это можно сделать, посчитав z-функцию для rev(C) + # + rev(A) + rev(A) и с помощью дерева отрезков найдя "самый левый элемент больше заданного на отрезке" за
.
У нас в J не зашло из-за теста m = 0. Теперь окей.
Ой, все!
How to solve problem B?
Hi, when will the final result of Moscow QF be available?
Edit: It is available now :) thanks
How to solve H?
Если предположить, что удалять выгодно не более 256 элементов, то динамика
ЗЫ Как это доказать??
У нас неравенство для константы чуть больше пятисот. мы легко можем взять >=(1+2+...+n-256*n). И используя n — k мы возьмем <= (1+2+...+n-k+256*(n-k)). Если первое больше второго, то такое k нам не подходит. n+(n-1)+...+(n-k+1)>256*(2*n-k).Понятно, что для k примерно равного 256*2 неравенство сойдется. Победа!
я, если честно, ничего не понял(
Попробую еще раз. Если ты взял k чисел, то i-е из них -- (i ^ coef_i), где coef_i < 256. Так как xor с числом, меньшим 256, не меняет ничего, кроме последних 8 бит, то появляется неравенство: |i — (i xor coef_i)|<256. Комбинируя дважды эти неравенства с разными знаками, мы получим то, что я написал выше.
Глубинный смысл в том, что |(10^5 xor a) — 10^5| очень мало по сравнению с 10^5 (для любого маленького a).
How to solve B?
How to solve B?
Результаты?
А что произошло с командами Moscow SU Trinity / SG и задачей K? Судя по комменту, там надо найти лексикографически максимальную топологическую сортировку. Вроде не особо трудная задача.
Там нужно внезапно догадаться, что это работает. Много кто не сдал. Мы вот тоже не сдали.
В смысле "догадаться"? Разве не очевидно, что всегда нужно поставить самую маленькую из ранее не поставленных вершин в ответ, а перед ней как-то расположить всех ее ранее не поставленных предков. Среди ее предков нужно в обратном порядке выводить самую большую из тех, кого уже можно выводить (с помощью подсчета ссылок можно отследить). Первое даже доказывать не надо. А второе... Ну если у нас есть выбор, кого поставить, а мы не поставим на более позднее место того, кто больше, значит ответ точно будет неверным. Ну а если мы всегда ставим самое большое значение, почему бы ему не быть верным?
Я восхищен авторами контеста. Они подобрали задачу, которая оказалась простой для многих участников, но гробом для большого числа топов. Вообще набор задач очень интересный выдался.
Если попытаться явно реализовать такую логику, то может получиться вот такое решение. Которое получает WA6, потому что непонятно что делать если самую большую вершину поставить пока нельзя.
Как мне кажется, до того факта, что решать необходимо с конца, нужно действительно догадаться.
Снизу я написал более точную версию своего решения и даже код приложил. Все с ним в порядке. А что касается "догадаться", то я в шоке, что многие участники моего уровня догадались, а такие топы не смогли. Может, действительно, слишком сложно думают. Грибоедов, помнится, что-то о подобном писал.
Я восхищаюсь вами. Вы кинулись обсуждать сложность задачи, которую не читали. Ваше решение получает WA 1.
К слову об авторах. Они считали, что это гроб, и не знали того решения, которое сдавали участники.
А известно авторское решение?
Можно ли быстро для орграфа найти кол-во вершин, от которых зависит текущая, для всех вершин? Пытались долго придумать решение такой задачи и не смогли, мб есть алгоритм?
кажется можно в каждой вершине хранить битсет всех кто из нее достижим типо того.
правда памяти многовато получается.
Да, там получается (200000)^2/32= 1 гиг памяти, но и по времени такая же оценка, это долго.
Да если получать в явном виде, хоть как получится квадратичная асимптотика. Если учесть тот факт, что не надо получать тех, кто уже был ранее предком вершины с меньшим номером, то можно воспользоваться обходом в глубину обычным и записать в порядке этого обхода все вершины. Для каждой вершины в таком случае все ее полезные предки будут на некотором непрерывном отрезке.
Почему непрерывном? Да, в порядке обхода в глубину, не заходя повторно в посещенные?
Ну все необходимые вершины будут в поддереве текущей. Оно обходится после посещения текущей, а выход из него происходит снова через текущую.
Вы случайно не о задаче J с 2012-2013 Летние Петрозаводские сборы, Andrew Stankevich Contest 42 (ASC 42) говорите?
Нет, не понимаю, причем тут она. Мы говорим все о той же задаче K из последнего МЧФ. Но я помню, как, сдав нечестное решение по этой задаче с +1, мы очень бурно радовались. Эх... были времена :(
"Можно ли быстро для орграфа найти кол-во вершин, от которых зависит текущая, для всех вершин?" — разве это не J с ASC?
Видимо да, расскажете решение или есть ссылка на видеоразбор?
500 мегабайт получается же.
А. 5 гб вообще получается...
Эм... Я конечно рад, что мной восхищаются. Но я сдал свое решение. Может быть его неправильно поняли по текстовому объяснению. Попробую лаконичнее.
Действуем так: Ищем самое маленькое неустановленное число v. Запускаем дфс из v, чтобы определить всех, кто еще не установлен и требуется для установки v. В ходе дфса для каждой такой вершины посчитаем, сколько вершин требуют ее установки, чтобы их можно было установить. Теперь будем строить обратный порядок для текущего множества вершин. Сама вершина v, очевидно, в нем будет первой. Далее выгодно выбрать наибольшую из тех, у кого количество ссылок равно нулю. Это можно сделать с помощью обычной кучи.
Дабы пояснить за свой "гнилой базар", выложу свой код.
+1 мы прорешивали этот контест. Придумали это, не доказали и забили. И кстати там вроде не совсем лексикографически минимальный, там немного другое надо было искать.
Если перевернуть последовательность, то требовалось сделать ее лексикографически максимальной. Об этом, как мне кажется, говорилось.
Раз уж ты так переформулировал — можно и проще решать: ставим в конец вершину с максимальным номером такую, что из нее все рёбра ведут в уже поставленные :) Реализация в несколько строчек с set-ом получается.
Это я и пытался сказать. Многословие замучало.
P.S. Поздравляю с громкой победой.
Согласен. У нас в команде даже раскол случился, для одного она оказалось гробом, а для другого лёгкой задачей на 20 минут.
P.S. Хз за что тебя заминусовали.
Да мне как-то не особо важно мнение краснофапающих школьников :) Возможно, потому что красный сказал, что мое решение неправильное. Гораздо хуже, что я не смог лаконично рассказать свое решение с двух попыток. Тренер, пусть и не столичного вуза, должен уметь такие вещи.
Лексикографически минимизировать обратную перестановку к топсорту.
А неверно, что ответ — лексикографически максимальная развернутая? Вроде жадность именно такое и даёт.
Anyone else got WA 15 in problem L of Moscow QF (and know how to fix it)? I've been banging my head for so long now and still have no idea what I did wrong :(
Москвский четвертьфинал появится в тренировках?
Ловите — 2015-2016 ACM-ICPC, NEERC, Московский четвертьфинал
how to solve B-Banana Brain's Bracelet? I use kmp both forward(continuous) and backward (split in half),but get wa.
how to solve C-Colder-Hotter? I use bineary-search,first x then y,I test many examples,but still get wa.
My guess is that your solution fails at some point to determine which half should be looked into. It happens when the answer is closer to the middle of the section you're currlently looking at than to left or right section's middle:
L------------l---------*--M------------r------------RHere, if you test whether you should go to left or right it appears that you're moving away from the answer (which is definitely the case). To correctly determine which way to go, ask what happens if you move from
ltor(or vice versa), which is the same as asking which of two "new" middles is closer to the answer.You can ask what happens when you move from x to x+1. If you receive 0, ans <= x. Else, ans > x.
yeah that works as well
Thanks,I have found the reason(I didn't receive the first answer)
Убедительная просьба организаторам четвертьфиналов и не только: вместо неполного и торопливого разбора перед торжественным закрытием просто выложите на сайте .pdf с разбором, пожалуйста.
Does somebody try B?I get wa on test 60.If anyone has the same experience,please share your ideas with us?
Где можно тесты раздобыть? Написал решение по King's Rout (K): перебираю все вершины, если вершину ещё не посещали, то запускаем dfs из неё, записываем все вершины в порядке обхода в массив, и для каждой вершины запоминаем позицию в этом массиве, и время входа и выхода обхода в глубину (это будет отрезок в массиве обхода в глубину с вершинами, которые нам нужны чтоб выкинуть нашу вершину). Для каждого под графа рекурсивно делаем следующее: запускаемся из вершины из которой мы строили обод в глубину, деревом отрезков ищем минимум и для этого минимума опять запускаем. (При запуске из вершины мы в дерево отрезков кладём в нашу вершину inf). Если для нашей вершины нет детей или минимум = inf выводим её. Потестил, вроде работает, может кто тесты подкинет или скажет где я не прав.
Northern QF Mirror registration is now open!
А как надо зарегистрироваться, чтобы были учтены результаты с онсайта?
Спасибо за отличные авторские решения на Джаве по задачам A, C, D, G. Очень жаль, что вас не хватило на остальные задачи, где они действительно были нужны.
Так же хотелось бы выразить благодарность, что такая ситуация уже продолжается не первый год. Отдельное спасибо за 2013 и задачу про аукцион, которая в принципе наверно на джаве не сдавалась.
Лучшая четверть, слава богу что последняя.
На самом деле, если конструктивней быть, я понимаю, что на джаве в Москве пишет очень мало кто. И так как четверть последняя, я могу с радостью прорешивать следующие. Зовите.
Завтра на нескольких площадках пройдет ЧФ. А после него будут выложены посылки всех команд со всех площадок?
Было крайне полезно, когда так сделали в прошлом году после полуфинала.
А почему минский ЧФ в такое необычное время? Вроде Минск и Москва в одном часовом поясе, не помню, чтобы трансляции раньше начинались в шесть вечера.
Сам чф в 10 утра, инфа стопроц
.
Объединённые результаты по всем трём турам.
Если какие-то результаты одной команды не склеены (или склеены результаты разных команд), пишите в комментариях — будет исправлено.
Через неделю результаты будут считаться окончательными.
Про минский ЧФ.
D — просто напишите двух китайцев
E — копия задачи с projecteuler (да и на А там что-то похожее уже было)
J была уже кучу раз.
Мда.
А как L?
Ответ:
(здесь Snk -- числа Стирлинга второго рода). Отдельное число Стирлинга считается легко считается по формуле с цешечками. Чтобы учесть возможную взаимную непростоту со знаменателем, надо
ВСПОТЕТЬвсе делать отдельно по модулю степеней простых; если модуль делится на pa, а N + 1 делится на pb, нам хватит посчитать по модулю pa + b.L — баян с IMC 2015 (решение для N = L, 8-я задача)
неплохие, у Вас, баяны :)
Ну, похоже авторы как раз и придумали эту задачу, увидев задачу с IMC. Вообще, кажется, они не особо запаривались новые задачи придумывать в этот раз.
D: То есть за ребро платится один раз вне зависимости от количества грузовиков, которые через него поедут?
Там же сказано, что один грузовик может взять сколько угодно грузов.
Да. Не очень понятно написано, конечно.
Я думал в этом и есть фишка задачи. Да и семплы ничего не поясняли :(
Вроде это написано в условии:
he can load any number of units into any truckРасскажите, пожалуйста, как решать E.
Посмотрим, как путь пересекает разрез между первыми k кочками и всем остальным. Разрез надо один раз пересечь слева направо и еще сколько-то раз приходить справа и уходить обратно, причем непосредственно перед пересечением разреза мы находимся не дальше чем на 3 кочки от него. Сгенерируем все возможные состояния (где кончается путь направо, несколько пар (первая и последняя точка пути, пришедшего слева)), сгенерим переходы, накрывающие и не накрывающие следующую точку, потом возведем соответствующие матрицы в степень.
Можешь поподробней объяснить(или скинуть код)? Про состояния понятно, а вот какие бывают переходы я не понимаю.
Переходы: шагнуть в следующую точку концом префикса пути, шагнуть одним из концов пар, начать в новой точке новую пару, слить путь и один из концов пары, после этого путь кончается во втором конце. Если бы можно было шагать дальше, чем на 3, надо было еще сливать пары друг с другом.
Код: http://pastebin.com/kGQQHx5L
Мы вчера попытались разобраться в двух китайцах и написали какой-то ужасный код. Может, у кого-нибудь есть красивая реализация?
Я во время контеста разбирался и написал это. Не знаю, насколько красиво, впрочем.
can you share your code for D?
http://codeforces.net/blog/entry/20970?locale=ru#comment-261060
It is right above your message :P
Western contest is available for virtual participating. Sorry for late reminder.
deleted
deleted
Интересно было бы что-нибудь узнать про B.
Мы пытались разбирать случаи, но дошли только до 9 теста.
Мне тоже было бы интересно. Мой разбор случаев дошел только до 8го теста :(
Как решается J?