Состоится. Опубликовал обновление с более точными датами. Ссылки на контесты появятся чуть позже.

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

Вообще-то вроде все соревнования официальной ветки ACM ICPC — с задачами исключительно на английском языке.

Скажите название команды, я отменю регистрацию. Сами вы пока этого сделать не можете.

http://codeforces.com/blog/entry/5406#comment-108667

And here it is... The Russian statements :)

Did I just download the practise session Russian problems?

Уже 45 минут контест идет. Пустая страница — какая-то старая версия браузера, видимо. Я сам на это когда-то жаловался, обещали поправить...

Ага, надо будет сделать.

А там что, надо 3 билета держать на руках????

У меня сложность, кажется, O(n B^4 A log что-то), но много отсекается. Решение такое. Сразу поэлементно сложим последовательности, получим последовательность из n нулей, единиц и двоек. Будем двигать окно длиной B по дням. Для каждого положения будем хранить мапу из кортежа значений в этом окне в минимальное количество действий, чтобы такого кортежа достичь (обнулив все левее окна и не трогая все правее). Но будем рассматривать не все кортежи, а только "разумные", то есть достижимые при "разумном" использовании билетов. При каждом положении окна запустим дейкстру по этой мапе, храня пометки в сете. Вершина — кортеж значений в окне, переход — купить билет ровно на этот период времени и каким-то "разумным" образом распределить его поездки внутри окна. Разумное использование билета — выбрать некоторое k и уменьшить первые k единиц до нулей и первые A-k двоек до единиц. После дейкстры посмотрим на все кортежи с нулевым первым элементов и для них сдвинем окно на 1 вправо, получая начальные кортежи для следующего положения окна. Достижимых вершин для каждого положения окна, кажется, O(B^3). Несмотря на длиный текст, пишется очень просто.

там уродство с даблами, у нас упало на этом тесте 3 -0.1 -0.1 0.01

У вас может упасть на какой-то из перестановок этого теста: 3 1 -0.5 -2 Ответ 1. По-крайней мере у нас когда был ВА22 бага была на таком тесте.

а что делать, если ваши тесты проходит, а WA 19?

У нас прошел обычный Mergesort. А Quicksort заваливался. Его интерактивно несложно завалить.

У нас quicksort на линейном порядке с медианой трёх случайных элементов в качестве опорного валился примерно на 15% запусков, посылать не рискнули.

Я не знаю, верно ли то, что я скажу далее. На сколько я понял(переводчик из меня фиговый), что в случае невозможности построить последовательность, то нужно вывести n + 1 0. В qs может возникнуть такая ситуация, что если построить орграф с ребром a-b, означающим, что b > a, то может появиться цикл, что как бы совсем плохо. Строго не доказывал, но проверял на существование этого цикла. Возможно я не прав.

P.S. Писал merge, скорее всего там цикла быть не может 100%. Но qs совсем другая.

P.P.S. Описанный выше способ с бинарным поиском — это вновь изобретенный велосипед. Называется сортировкой бинарными вставками

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

Кое-какие накладки со временем начала. Подробнее ответит жюри, если посчитает нужным.

В одной из аудиторий МГУ произошёл сбой, из-за которого старт для этой аудитории был отложен на 35 минут (дисплеи у участников были выключены; дежурный ошибочно ожидал устной команды о начале контеста). Соответственно, только для этой аудитории турнир продлили.

Кроме того, по техническим причинам (различные инструкции, выданные дежурным площадок) команды, пишущие в остальных аудиториях МГУ, получили условия на 7 минут позже команд в МФТИ.

При подведении итогов жюри пересчитало результаты с помощью электронных таблиц; так как оба сдвига не повлияли на распределение призовых мест и путёвок в полуфинал, то было решено не затягивать закрытие и оставить в предварительных результатах всё "как есть".

В данный момент обсуждается вопрос о пересчёте таблицы перед публикацией окончательных результатов. Лог четвертьфинала для виртуальных контестов будет распространяться в пересчитанном виде.

G: подвесим дерево за какую-то вершину, обойдем dfs, если во время обхода dfs направление ребра совпадает с направлением dfs по этому ребру, запишем на ребре 1цу, иначе 0. будем хранить для каждой вершины сумму ребер до нее от корня, а так же, ее глубину.
когда поступает запрос x, y: нужно чтобы все ребра от lca(x, y) до y были сонаправлены обходу dfs, а ребра от x до lca(x, y) противоположнонаправлены обходу dfs. это проверяется просто, если сумма х (по ребрам, которую мы храним) — сумма lca(x, y) = длине пути от x до lca(x, y), а сумма y — сумма lca(x, y) = 0, то "Yes", иначе "No"

На разборе рассказывали за (N log N + M log N). Суф. массив плюс хитрый стек возможных максимумов при фиксированной правой границей, двигаем правую границу постепенно слева направо, плюс RMQ.

На разборе NlogN решение рассказывали.

Нужна любая структура, которая умеет сравнивать суффиксы и искать lcp (даже хеши сойдут). Далее, можно решить задачу оффлайн — посортить запросы по правому концу, далее двигаем правый конец и поддерживаем 2 множества: для данного правого конца r множество суффиксов всей строки, начинающихся не правее r, которые бывают максимальными (это халява), и множество суффиксов префикса, заканчивающегося в r, которые бывают максимальными (это уже сложнее; будем добавлять туда все встречающиеся префиксы, а в процессе строить граф, если мы не добавляем в первое множество суффикс, начинающийся в r, то добавляем дугу из него в самый короткий элемент первого множества M; и удаляем r и всё, достижимое по дугам, из второго множества в момент времени r + LCP(r, M)).

Upd: Ну и понятно, как обрабатывать запросы, имея второе множество: это просто запрос минимума на отрезке.

Имхо, офигенная задача от Васи Астахова :) Вроде бы, наука до этого такое делать не умела. Ещё кажется, что это можно обобщить на онлайн-запросы.

Считали те же две динамики, но без логарифмов. Чтобы первая динамика не вылезала за экспоненту дабла, делили перед пересчетом всю строчку на одно и то же число.

У меня было 2 динамики. Первая f(n, k) говорит, сколько есть перестановок из n элементов среди которых k выделенных могут принадлежать циклам длины 1, а остальные — нет. Вторая g(n, k) — это то же самое, только не количество перестановок, а суммарное количество циклов в них. Чтобы ничего не переполнялось, сразу считаем это количество, деленное на n!. Для этого каждый раз при переходе делим результат на n.

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

У нас линейное решение.

Считаем такую велечину f[n] = 1 + 1/2 + ... + 1/n это средние число циклов в перестановке длины n. Пусть у нас цепочек a, изолированных точек b, законченых циклов c потом считаем велечину

d = Sum[i = 0, i <= b, C(b, i) * (a + b — i)! * (f[a + b — i] + i + c)(-1) ^ i]

e = Sum[i = 0, i <= b, C(b, i) * (a + b — i)! * (-1) ^ i]

d — это суммарное число циклов в хороших перестановках e — число хороших перестановок

ну и ответ собствено d / e и считали всё в логарифмах

Нет. Там и без хешей с мэпом нормально заходит. UPD Нет — в смысле с хэшами сдалось.

В смысле полные?

Мне очень понравилась легенда задачи про немонотонные последовательности :)

В некоторых задачах было довольно сложно распарсить условие:(

During the last hour it worked very slow

Рекурсивное решение. Разбиваем множество вершин на 2 равных. Решаем задачу для каждого множества. Затем соединяем каждую веришну из первого множества с каждой вершиной из второго, используя наименьший цвет, который не использовался в раскрассках этих множеств. Когда только 1 вершина ничего не делаем. Получается цветов O(logN).

Граф обладает двумя свойствами:
1. Если рассмотреть множество вершин N(v) (соседи вершины v), то граф на этих вершинах связный
2. В графе нет подграфов K1,3.

Я решал так:

1) начинаем с треугольника 2) если можно куда-то вставить вершину в цикл, вставляем 3) если нет, но еще есть вершины, связанные с циклом, то нетрудно видеть, что будут вершины, соединенные с как минимум двумя вершинами цикла, скажем пусть вершина a соединена с v_i и v_j. Тогда заметим, что v_{i-1} и v_{i+1} обязательно соединены, и v_{j-1} и v_{j+1} обязательно соединены. Тогда нам достаточно одного из следующих ребер, чтобы перестроить цикл, включив в него a: v_i-v_{j-1}, v_i-v{j+1}, v_{i-1}-v_j, v{i-1}-v{j+1}, v{i+1}-v{j-1}, v_{i+1}-v_j, так же достаточно, если i+1=j-1 или i-1=j+1. Дальше я просто пытался найти такую тройку a, v_i, v_j, чтобы одно из этих условий было выполнено, и это почему-то всегда получается. Я пытался доказать, что это всегда получится, но не смог :)

Извиняюсь, я криво прочитал условие.

Try this test case:

3
ab
abcc
abdd

интересно, после такого количества недовольных, администрация что-нибудь изменит?

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

K. Для маленьких (<100) напишем перебор. Для четных. Решим для (n-8)/2, умножим все на 2, добавим две 4. Для нечетных. Решим для (n-9)/2, умножим все на 2, добавим 3 и 6.

P.S. Это решение от niyaznigmatul. Мы писали такое же но посложнее. Мы для остатков по модулю 6 делали. Для четных так же. Для кратных трем (3n-6)/6 и прибавить 3 и 3. Для остатка 5- потом добавить 2 и 3. А для остатка 1. Решить для (n-55)/6 и добавить (2,4,21,28).

Задача D. Вроде никто пока нормально не объяснил.

Пусть у нас есть 2 лабы, и мы сначала сдаем первую (в момент времени t). Тогда мы получим штраф, равный w[1] * t + w[2] * (t + p[1]).
А если мы сдаем сначала вторую, а потом первую, мы получаем штраф w[2] * t + w[1] * (t + p[2]).
Эти два значения отличаются на величину w[2] * p[1] — w[1] * p[2]. Если она меньше нуля, выгоднее первый случай, иначе — второй. Теперь можно посортить все лабы в данном предмете с этим компаратором.

Теперь посмотрим, чем равен штраф в группе из k лаб, если начинали мы так же в момент времени t. Он равен w[1] * t + w[2] * (t + p[1]) + ... + w[k] * (t + p[1] + ... + p[k-1]).
Здесь имеют значение только слагаемые (w[1] + ... + w[k]) * t, т.к. оставшиеся произведения (обозначим их за X для краткости) не зависят от времени сдачи лабы.
Соответственно, если сдавать сначала первую группу лаб, а потом вторую, то штраф будет равен (sum_w1 * t + X1) + (sum_w2 * (t + sum_p1) + X2), а если сначала вторую, а потом первую — то (sum_w2 * t + X2) + (sum_w1 * (t + sum_p2) + X1). Видно, что они отличаются на величину sum_w2 * sum_p1 — sum_w1 * sum_p2. Отсортив группы лаб по этому компаратору, получаем искомое разбиение.

Для закрепления можно решить задачу J вот отсюда, правда, она посложнее в реализации, но идея та же.

Рассмотрим строку T = S + S из которой удален последний символ. Тогда все циклические сдвиги — это подстроки длины n = |S| этой строки.

Разобьем наш шаблон на части q₁, q₂, ..., q_k из букв, которые находятся между звездочками. Тогда если мы хотим проверить подстроку [l, r] строки T на то, подходит ли она к шаблону, достаточно чтобы части q_i присутствовали между l и r в качестве подпоследовательности, причем между собой не пересекались. Дополнительно накладывается следующее условие: если шаблон не начинается со звездочки, то начало q₁ должно быть в позиции l. Аналогично, если шаблон не заканчивается на звездочку, то q_k должно заканчиваться в позиции r.

Чтобы это все проверить, достаточно пройти по строке T справа налево и поддерживать динамику f(pos, i) -- самое раннее возможное окончание куска q_k, если мы начинаем прикладывать кусок q_i к позиции pos или правее. Она довольно просто пересчитывается.

Сложность O(|S|·|Pattern|).