Hi Codeforces,

We are happy to announce a London meet-up on July 13!

My friend Nadya (from Luna Park) asked me about any competitive programming/math alumni events here in London, and it seemed there weren't any. So we decided we should probably host one ourselves, asked a bunch of friends to come, and now it's happening!

This is by all means an informal meeting — just a picnic in a park to meet both new people and old friends and talk about stuff.

So yess, chances are you may find out that the people you met at ICPC finals a million years ago are living in London too! Or just discuss AI, burnout, taxes and whatever you will feel like discussing and eat some strawberries.

The date is 13th of July, the location will be revealed soon. Here’s the registration link, and we will share a group chat link later.

And feel free to share this post with your friends — here, on Linkedin or on Telegram!

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

408A - Очередь на кассе

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

408B - Гирлянда

В задаче нужно было найти максимально длинную гирлянду, которую можно составить из тех элементов, что у нас есть.
Во-первых, если какой-то цвет нужен, но его нет, то ответ — -1.
Иначе, ответ всегда существует, и является целым числом.
Просуммируем ответы по всем цветам по отдельности.
Пусть у нас есть a кусков бумаги некоторого цвета, а нужно — b. Тогда если a >  = b, то к ответу можно прибавить b — повесить b кусков по одному метру, а если a < b, то к ответу можно прибавить a, использовав все куски, что есть в наличии. Итого, каждый цвет дает к ответу min(a, b).

407A - Треугольник

В задаче требовалось расположить прямоугольный треугольник с катетами a, b на плоскости с вершинами в целых точках.
Если искомое расположение существует, то катет a всегда можно представить как вектор с целыми координатами A{x;y}, при чем a² = x² + y². Переберем все возможные x (1 ≤ x ≤ a - 1), проверим, что y получается целым числом.
Вектор, перпендикулярный вектору {x;y} — { - y;x}. Возьмем вектор B{ - y / g;x / g}, где g = gcd(x, y). Треугольник можно уложить на плоскость лишь тогда, когда b делится нацело на |B|, где |B| — длина вектора B. Кандидат на ответ — треугольник (0;0)(x;y)( - y / g * b / |B|;x / g * b / |B|), нужно лишь не забыть проверку на то, что гипотенуза не параллельна осям координат.
Сложность решения — O(n).

407B - Длинный путь

В задаче требовалось промоделировать путь персонажа по графу.
Заметим, что если мы пришли в вершину i, то ребра во всех вершинах с номерами меньшими, чем i, повернуты в p_i. Это дает нам возможность заметить рекуррентную формулу: пусть dp_i — число шагов, необходимое, чтобы добраться из вершины 1 в вершину i, если все ребра изначально повернуты назад, в p_i. тогда dp_i + 1 = 2dp_i + 2 - dp_pi. Ответом будет dp_n + 1.
Сложность решения — O(n).

BONUS: Умеете ли вы решать задачу, если нет ограничения, что p_i ≤ i? В такой формулировке задача становится более интересной, но я пока не знаю решения.

407C - Занимательный массив

В задаче требовалось научиться прибавлять в оффлайне на отрезке числа сочетаний.
Будем смотреть, как изменяется задача при увеличении k от малых чисел к большим.

1) Все запросы имеют K = 0
Прибавляется каждый раз единица на отрезке.
Для решения задачи нужно прибавить на некотором массиве b[] в ячейку b[L] единицу, вычесть из b[R + 1] единицу, а после выполнения всех операций построить массив a как массив сумм на префиксах массива b.

2) Все запросы имеют K = 1
Прибавляется арифметическая прогрессия 1 2 3 4 ...
Для решения задачи нужно прибавить на некотором массиве c[] в ячейку c[L] единицу, вычесть из с[R + 1] единицу. После выполнения всех операций можно построить массив b как массив сумм на префиксах массива c. В таком массиве мы на каждом отрезке прибавили единицу. Если после этого для каждого запроса вычесть из b[R + 1] число C(R — L + 1, 1) = (R — L + 1), и построить массив а как массив префиксных сумм над массивом b, несложно увидеть, что массив а будет ответом.

3) Все запросы имеют произвольное k
Пускай у нас есть массив a[N][K].
обобщая предыдущие случаи, можно понять, что если поступает запрос L, R, K, нужно сделать операции

a[L][K + 1] += 1
a[R + 1][j] -= C(k + 1 — j + r — l, k + 1 — j) для всех 1 <= j <= K + 1

после чего построить необходимые суммы на префиксах для всех значений K спускаясь от больших K к меньшим.
Доказать, что нужно отнимать именно такое число сочетаний, проще всего, если посмотреть, как расположены эти числа в треугольнике Паскаля — легко увидеть, что это число является суммой всего ряда чисел перед ним.
Сложность решения — O((n + m)k).

407D - Наибольшая подматрица 3

В задаче требовалось найти наибольшую по площади подматрицу, состоящую из различных чисел.
Будем идти от медленных решений к более быстрым.

1) Решение за O(n⁶): Перебираем две противоположные вершины прямоугольника-ответа и проверяем, что все числа внутри различны.

2) Решение за O(n⁴): Фиксируем верхнюю и нижнюю границы прямоугольника-ответа (O(n²)).
Используем метод двух указателей при переборе левой и правой границы: пока в прямоугольнике нет одинаковых чисел, двигаем правую границу, пока есть — двигаем левую границу. Проверка при сдвиге границы — O(n), сдвигов — O(n).

3) Решение за O(n³logn): Введем функцию maxR(Left): наибольшее значение Right, такое, что при фиксированных Up и Down в прямоугольнике (Up, Down, Left, Right) нет одинаковых чисел. Заметим, что для всех i выполняется maxR(i) <= maxR(i + 1).
Как изменяются значения этой функции при сдвиге Down вниз? Каждое значение maxR(Left) может либо остаться таким же (если отрезок(Down, Down, Left, maxR(Left)) добавил лишь новые числа), либо уменьшиться.
Когда maxR(Left) уменьшается? Лишь тогда, когда одно из чисел с только что добавленного отрезка уже было в прямоугольнике.
Сдвигая Down вниз рассмотрим все числа в ряду Down. Для каждого числа в столбце j найдем индексы i и k такие, что i <= j, в столбце j есть вхождение числа a[Down][j] между строками Up и Down-1, i — максимально; k >= j, в столбце k есть вхождение числа a[Down][j] между строками Up и Down-1, k — минимально. Найдя такие индексы i и k (для этого удобно использовать set, для каждого цвета храня столбцы, где он встречался на данный момент между строками Up и Down), можно обновить maxR[i] = j — 1, maxR[j] = k — 1. Этого будет достаточно. Несложно заметить, что после описанных действий, если мы прокинем по всем i = m..1 maxR[i] = min(maxR[i], maxR[i + 1]), то мы вновь будем иметь корректные значения функции maxR(Left), и можно пересчитать ответ для данных Up и Down за O(n).

4) Решение за O(n³):
Предыдущее решение, несмотря на хорошую асимптотику, требует хранения большого количества set'ов. Это работает очень медленно даже на небольших тестах.
Избавимся от логарифма. Set используется лишь при поиске ближайших слева и справа чисел, равных данному, лежащих в строках с номерами от Up до Down. Заметим, что при сдвиге границы Up ближайший сверху элемент для данного a[i][j] отдаляется. Это наводит на мысль, что, двигая Up снизу вверх, можно заставить ближайший к a[i][j] элемент приближаться к столбцу j, и теперь, сдвигая Up вверх, мы можем, взяв число с верхнего ряда, быстро (за O(n)) определить все числа такие, что он будет для них ближайшим, и обновить для них ближайшее число.
Такое решение использует O(n²) памяти и O(n³) времени.

BONUS: Умеете ли вы решать эту задачу быстрее, чем за O(n³)? У меня не получилось, но никаких предпосылок того, что решения нет, я не нашел.

407E - k-d-последовательность

На контесте задачу, к сожалению, никто не решил, но в дорешивании первым оказался hza, с чем мы его и поздравляем.
В задаче требовалось найти наидлиннейший подотрезок, удовлетворяющий условию.

Сведем задачу к d = 1.
Если d = 0, то ответ — наидлиннейший подотрезок из равных чисел, этот случай обрабатываем отдельно.
Если d ≠ 0, то заметим, что если на некотором отрезке есть два числа a_i, a_j таких, что a_i % d ≠ a_j % d, то этот отрезок не может быть хорошим.

Разобьем исходную подпоследовательность на отрезки подряд идущих чисел, дающих равные остатки от деления на d, поделим каждое число на d, будем решать для каждого отрезка задачу отдельно, сказав, что d = 1.

Заметим, что отрезок [L, R] является хорошим тогда и только тогда, когда max(L, R) — min(L, R) — (R — L) <= k, и на отрезке с L по R нет одинаковых чисел. Объясняется это просто — если на отрезке нет повторяющихся чисел, то max(L, R) — min(L, R) — (R — L) — именно количество чисел, которые необходимо добавить, чтобы отрезок состоял из всех чисел с min(L, R) по max(L, R).

Для каждого L найдем такое maxR[L], что на отрезке с L по maxR[L] нет повторяющихся чисел, а maxR[L] — максимально. Это делается за O(nlogn) любым способом, например, проходом с map'ом.

Научимся для каждого фиксированного L поддерживать массив a[R] = max(L, R) — min(L, R) — (R — L). Если у нас есть такой массив, то для того, чтбы найти ответ, необходимо быстро найти такое наибольшее R, что a[R] <= k.

Нам потребуются два стека и дерево отрезков с операциями "Прибавить число на отрезке", "Найти минимальный элемент на отрезке" и "Найти самое правое число, такое, что оно не превышает k". Будем перебирать L справа налево (от n до 1). Как выглядит функция max(L, R) при фиксированном L? Ее значения представляют собой набор отрезков, на которых максимумом является первый элемент отрезка. (пример: для массива 6 4 8 0 7 9 функция max(1, R) будет иметь вид 6 6 8 8 8 9) Как изменяется функция при сдвиге L влево? Некоторые отрезки поглощаются новым элементом, если новый элемент больше значения на отрезке. Заметив, что все значения массива не убывают, будем хранить все такие отрезки в стеке, а при добавлении нового элемента a[L] вытаскивать отрезки из стека, пока значение на вершине меньше нового, и добавим на стек новый отрезок, который покроет L и все, что мы вытащили. Если каждую операцию со стеком сопровождать запросом "Прибавить число на отрезке", то мы уже можем получить массив a[R] = max(L, R).
Функция min(L, R) ведет себя абсолютно аналогично, и используя второй стек мы получаем a[R] = max(L, R) — min(L, R). Для того, чтобы получить член (R — L) достаточно просто каждый раз при сдвиге L влево отнимать единицу на отрезке [L, n].

Теперь запрос "Найти самое правое число, такое, что оно не превышает k". Сначала дерево отрезков разбивает отрезок запроса L..R на log(n) отрезков длиной степени двойки. Разобьем запрос на такие отрезки и выберем самый правый отрезок, минимум на котором <= k. Теперь будем спускаться по этому отрезку вниз в дереве отрезков — если в правом сыне min <= k, то в правого, иначе в левого. Так мы найдем искомый элемент.

Итак, для каждого фиксированного L делаем запрос на отрезке L..maxR(L) о самом правом числе, не превышающем k. Это один из кандидатов на ответ. Все. Раз мы делаем запрос на отрезке, на котором нет различных чисел, то любое число на этом отрезке неотрицательно, и min работает корректно.

Суммарное время работы — O(nlogn).

BONUS: Задача и сама по себе не из простых, но умеет ли кто-нибудь решать ее по методу "навороти побольше"? Интересно, как решать хотя бы на дереве.

BONUS2: Есть очень быстрое решение за O(n²). Давайте для отрезка [L; R] так же посмотрим на значение f(L, R) = max(L..R) — min(L..R) — (R — L) — K. f(L, R) можно считать для отрезка за O(1). Если f(L, R) <= 0, то отрезок — кандидат на ответ. Если f(L, R) > 0, то следующий отрезок, который стоит рассмотреть — [L; R + f(L, R)], потому что для всех r: R < r < R + f(L, R) отрезок [L; r] не будет k-d последовательностью, поскольку при добавлении одного числа в отрезок f(L, R) может либо возрасти на произвольное число, либо уменьшиться на единицу. Если так написать решение за квадрат, используя для начального R при фиксированном L значение L + curAns, то решение в среднем работает очень быстро, и получает ТЛ лишь на специальных тестов. Вполне возможно, что это решение можно оптимизациями довести до такого, что оно пройдет все тесты.

Всем привет!

В это воскресенье, 30 марта, в 11:00 MSK, состоится Codeforces Round #239 для участников обоих дивизионов. Обратите внимание на необычное время проведения раунда.

Автором задач являюсь я, izban. Большое спасибо команде Codeforces: координатору задач Геральду Агапову (Gerald) за неоценимый вклад в подготовку задач и Марии Беловой (Delinur), которая перевела задачи на английский язык. Также спасибо Ниязу Нигматуллину (niyaznigmatul) за прорешивание задач.

Желаю всем хорошо написать раунд и с удовольствием провести выходные!

UPD: Разбалловку вы можете увидеть на странице с задачами.

UPD2: Разбор вы можете найти по этой ссылке. Обратите внимание на бонусы в некоторых задачах!

Задача А:

Заметим, что в конец копируется элемент, который был k-тым. Затем копируется элемент, который был (k+1)-м в исходном массиве, затем (k+2)-й, ... , n-й, k-тый, (k+1)-й etc. Значит, все числа станут одинаковыми тогда и только тогда, когда в исходной последовательности все числа с k-го по n-й были одинаковы. Теперь очевидно и то, что количество операций, требуемое для этого, равно номеру последнего не равного n-му элемента последовательности, так как ровно столько удалений понадобится для того, чтобы убрать не равные ему элементы. Если этот номер больше, чем k, то ответа нет. Асимтотика — O(N).

Задача B:

Давайте на каждом шаге будем хранить текущий порядок строк и порядок столбцов в таблице, относительно начального. То есть, row[x] — номер строки x в начальной таблице, а column[x] — номер столбца x в начальной таблице. Тогда значение элемента в строке x и столбце y текущей таблицы будет равно t[row[x], column[y]], где t — начальная таблица. В запросах обновления нужно просто поменять местами ячейки соответствующего массива с номерами x и y. Асимптотика O(n * m + k).

Задача C:

Для начала факторизуем числитель и знаменатель. Теперь для каждого простого числа x мы знаем степень этого числа в факторизации числителя(a[x]) и в факторизации знаменателя(b[x]). Для любого простого числа x мы можем вычислить его степень в факторизации числителя числа после сокращения(newa[x]) и в факторизации знаменателя этого числа(newb[x]): newa[x] = a[x] — min(a[x], b[x]), newb[x] = b[x] — min(a[x], b[x]). У нас есть числитель и знаменатель ответа(в факторизованном виде), осталось только привести их в вид, требуемый в условии. Один из способов — заметить, что дробь из условия подходила под все требования. Поэтому можно факторизовать ее еще раз и вывести такую же дробь, но так, чтобы ни одно простое число не имело большую степень, чем в посчитанных нами newa и newb. Получившиеся числа будут подходить под ограничения и их частное будет равно искомому числу. Если пробовать строить ответ жадно (набирать множители, пока их произведение <= 10^7), то количество чисел в ответе выходит за рамки 10^5. Асимптотика решения O(max + n * log max). Факторизация за O(sqrt(max)) получала TL, поэтому нужно было воспользоваться более быстрыми способами. Например — посчитать для каждого числа его наименьший простой делитель с помощью линейного решета эратосфена.

Задача D:

Во-первых, заметим, что наилучшее место, которое мог занять Вася — это первое, ведь ограничений сверху на его балл нет. Теперь нужно найти самое худшее место из тех, что он мог занять. Переформулируем. Нужно максимизировать количество таких участников, что если участник в первом туре набрал a[i] баллов, во втором — b[j], то a[i]+b[j] >= x. То есть, нам нужно найти максимальное паросочетание в двудольном графе, в котором ребро между вершинами i первой доли, j второй доли есть тогда, когда a[i] + b[j] >= x. Для решения этой подзадачи достаточно было отсортировать вершины в обоих долях по весу, и пройтись двумя указателями. Допустим, мы отсортировали по убыванию веса. Возьмем два указателя L = 1 в левой доле и R = N в правой доле. Пока a[L] + b[R] < x (то есть нет ребра L->R) нам стоит уменьшить R — взять вершину во второй доле с большим весом. Как только мы нашли R такое, что a[L] + b[R] >= x, мы берем ребро L->R и добавляем в ответ. Все — переходим к следующим L и R. Несложно показать, почему этот алгоритм найдет оптимальное решение. Я нашел поистине удивительное доказательство этому, но поля этого разбора слишком узки для него. Асимптотика — O(N log N) на сортировку и O(N) на два указателя.

Задача Е:

1) Решение за O(n*m*m): Простая динамика. Состояние — d[n][m] — сколько возможных цепочек длины n могут заканчиваться на символ m. Переход — перебираем все возможные символы, и смотрим, можно ли поставить символ k после символа m.

2) Решение за O(m*m*m*log n): Заметим, что в нашей динамике переход всегда одинаковый. Можно составить матрицу перехода A размером MxM. Если jый символ может идти за iым, то A[i][j]=1, иначе A[i][j]=0. Пусть есть вектор размером 1хМ b={1,1,...,1}. Тогда можно заметить, что b * a^(n-1) = ans. Воспользуемся бинарным возведением в степень для того, чтобы посчитать a^(n-1). Отдельно следует рассмотреть случай n==1. Ответом будет сумма элементов в векторе ans. Асимптотика — m^3 на перемножение матриц и log n на бинарное возведение в степень.

Всем привет!

Сегодня пройдет Codeforces Round #137 для участников второго дивизиона. Как обычно, остальные могут принять участие вне конкурса.

Задачи подготовила группа авторов из Владивостока — Илья Збань (izban), Алексей Евсюков (aevsyukov), Захар Войт (zakharvoit). Огромный вклад в подготовку раунда внес Геральд Агапов (Gerald), большое ему спасибо. Перевела задачи Мария Белова (Delinur). Также выражаем благодарность Павлу Кунявскому (PavelKunyavskiy), который тоже предложил свою помощь в подготовку контеста.

Разбалловка сегодня стандартная (500 — 1000 — 1500 — 2000 — 2500).

Всем удачи!

UPD: Начало контеста передвинуто на 15 минут по техническим причинам, приносим свои извинения.

UPD2: Опубликован разбор. Пока только на русском.

UPD3: Поздравляем победителей!

Во втором дивизионе первые 10 участников:

1: zxl0714

2: resodo

3: mugurelionut

4: hmspmy077

5: CCC

6: white_rich_beautiful

7: loveSakura

8: gcwtft827

9: yuxingdubai

10: b821213

В первом дивизионе, оторвавшись на взломах по задаче С, первые места заняли

1: navi

2: Shik

3: SteamTurbine

Надеюсь, вам понравилось!

15 - 21 января 2012 года в городе Алматы пройдет VIII Международная Жаутыковская олимпиада по математике, физике и информатике.