544A - Набор строк

В этой задаче нужно написать то, что написано в условии. Для этого можно воспользоваться массивом, с помощью которого мы будем понимать встречалась буква до этого. Будем будем обрабатывать символы по очереди. И поддерживать некоторую строчку. Если текущий символ ещё не встречался, то тогда начнём новую строку, а текущую строку мы положим в массив ответа. Иначе добавим текущий символ конец текущей строки.

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

Авторское решение: 11035685

544B - Море и острова

В эти задачи нетрудно понять что оптимальный ответ всегда состоит из одиночных клеток обладающих следущим свойством: сумма индекса строчки и столбца четная. Таким образом попробуем разместить ровно k островков в этих в клетках, если не получится, то ответ на задачу NO. Попробуйте доказать почему всегда так действовать оптимально.

Авторское решение: 11035691

543A - Пишем код

Давайте для начала придумаем решение который будет работать медленнее чем нужно. Будем решать задачи динамическим программированием: z[i][j][k] — мы обработали ровно i программистов, написали ровно j строчек кода и при этом возникло ровно k ошибок. Как сделать в такой динамике переходы? Очень просто, переберём сколько строчек напишет i программист (пусть r) и прибавим к z[i][j][k] значение z[i][j - r][k - r[a_i]]. Однако давайте посмотрим на переходы с другой стороны. Очевидно, что i программист либо не напишет ни одной строчки, тогда к ответу прибавится значение z[i - 1][j][k], либо он напишет одну строчку, а остальные строчки учтутся в значении z[i][j - 1][k - a[i]]. Здесь можно провести аналогию c подсчетом биномиальных коэффициентов c помощью треугольника паскаля. Таким образом получим решение за ассимптотику O(n³)

Авторское решение: 11035704

543B - Разрушение дорог

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

Теперь перейдем к искомой задаче. Пусть d[i][j] — кратчайшее расстояние между вершинами. Такую матрицу очень просто насчитать, запустив из каждой из n вершин bfs. Отлично

Теперь разберем два случая: Пути не пересекаются, тогда ответ можно обновить числом m - d[s₁][t₁] - d[s₂][t₂] (при условии, что выполнены условия на длину путей). Иначе, заметим что если пути пересекаются, то тогда тогда ответ имеет вид буквы Н. Более формально, сначала каждый из путей будет содержать различные ребра, потом несколько общих ребер, идущих подряд, и затем каждый из путей будет содержать различные ребра. Таким образом, переберем первую и последнюю общие вершины пути. Пусть эти величины равны (i, j). Тогда обновим ответ величиной m - d[s₁][i] - d[i][j] - d[j][t₁] - d[s₂][i] - d[j][t₂] (при условии, что выполняются ограничения на длину путей). Стоит отметить, что также стоит обменять вершины s₁ и t₁ местами, и снова обновить ответ, поскольку иногда выгодно соединить t₁ и с вершиной i, а s₁ с вершиной j. Решения, которые не учитывали это не проходили 11 тест

Авторское решение: 11035716

543C - Запоминаем строки

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

Далее возможны две ситуации: за одну операцию мы можем взять и заменить символ на любой другой, за это мы заплатим a[i][j] денег ( в зависимости от столбца, в котором мы сделаем строку уникальной). Либо за мы можем взять некоторый столбец, и рассмотреть некоторое множество строк, имеющих одинаковый символ в заданном столбце, и все сделать их уникальными. За это мы оплатим стоимость замены всех символов, кроме одного: самого дорого. Таким образом, получим решение: d[mask] — ответ на задачу, если мы сделали все строки, отвечающие за единичные биты уникальными. Как пересчитывать такую динамику? Пусть lowbit — младший единичный бит. Тогда очевидно, что мы сделаем его уникальным либо с помощью первой операции, либо с помощью второй. Для этого, переберем столбец и рассмотрим множество строк, имеющих такой же символ с со строкой lowbit. И обновим ответ соответствующим значением. Получим решение за ассимптотику O(m2ⁿ), где m — длина строки.

Авторское решение: 11035719

543D - Улучшение дорог

Подвесим дерево за вершину 1. Для начала подсчитаем вспомогательную динамику d[i] — количество способов починить дороги для поддерева с корнем в вершине i. Как такую динамику пересчитывать — где j это дети вершины i. Отлично. Таким образом ответ на задачу для вершины 1 — это d[1] Далее научимся переподвешивать дерево за некоторого ребенка j текущей вершины i. Очевидно, пересчитаем величину d[i]: suf[i][j] * pref[i][j] * d[parent], где parent — это родитель вершины i, (для вершины 1 d[parent] = 1), а массивы suf[i][j] — это произведение величин d[k], для всех детей i, k < j (pref[i][j] — k > j). После этого, обновим значение d[j] значением d[j] * (d[i] + 1). Все, теперь вершина j стала корнем, и ответ для нее — текущее значение d[j]

Авторское решение: 11035737

543E - Слушаем музыку

Отсортируем песни по убыванию. Будем последовательно рассматривать песни и говорить, что теперь песня хорошая и удовлетворяет критерию качества. Пусть s_i = 0, если песня с номером i еще не добавлена в рассмотрение, и s_i = 1 иначе. Тогда пусть . Очевидно, когда мы добавляем новую песню позиции idx в рассмотрение, мы должны сделать  +  = 1 на отрезке [max(0, idx - m + 1), idx] в нашем массиве v. Значит, чтобы ответить на запрос, мы должны поддержать структуру данных которая могла бы восстановить заданные значения в массиве v в на тот момент, когда все песни имели качество  ≥ q. Кроме этого, она должна использовать мало памяти. В итоге ответ на запрос очевидно равен m - max(v_i), l_j ≤ i ≤ r_j.

Каждые добавлений песен сохраним три величины: значение первого элемента в блоке позиций, максимум значения массива v на блоке, и дополнительно не более обновлений, которые пришли в текущем блоке обновлений, но не покрывали полностью заданный блок. Используя эти значения нужно аккуратно восстановить нужную информацию о массиве v и ответить на запрос.

Авторское решение: 11035739

Привет Codeforces!

Скоро состоится очередной раунд Codeforces Round #302, задачи для которого придумал я, Виталий Гриднев.

Хочу сказать большое спасибо Максиму Ахмедову (Zlobober), Александру Игнатьеву (aiMR), Данилу Сагунову (danilka.pro) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Распределение баллов:

1. Div1: 500 — 1000 — 1750 — 1750 — 2500
2. Div2: 500 — 1000 — 1500 — 2000 — 2750

Контест закончен, поздравляем победителей:

Div1:

1. Petr
2. qwerty787788
3. -XraY-
4. kraskevich
5. Merkurev

Div2:

1. nka55
2. never_retired_phoenix
3. lowsfish

Разбор задач

Скоро состоится очередной раунд Codeforces Round #284, задачи для которого готовили Виталий Гриднев (gridnevvvit), Илья Лось (IlyaLos), Данил Сагунов (danilka.pro).

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

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

Раунд окончен, поздравляем победителей!

Div1:

1. yeputons
2. rng_58
3. Endagorion
4. KADR
5. Egor
6. uwi
7. mmaxio
8. atetubou
9. RAVEman

Div2:

1. sorry_dreamoon
2. dreamoon_love_AA
3. dreamoon_fan

Разбор задач

Удачи!

Скоро, 24 октября, 21:00 MSK, состоится очередной Codeforces Round #275 для участников из обоих дивизионов. Обратите внимание на необычное время старта раунда!

Задачи этого раунда готовила команда Саратовского ГУ #3 в составе: Гриднев Виталий (gridnevvvit), Данил Сагунов (danilka.pro), Роман Киреев (RoKi).

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Распределение баллов:

Div1: 500 1500 1500 2000 2500

Dvi2: 500 1000 1500 2500 2500

Соревнование закончено, поздравляем победителей!

UPD:

Div1:

1. tourist
2. Petr
3. subscriber
4. uwi
5. PavelKunyavskiy
6. mmaxio
7. Ra16bit

Div2:

1. dickXD
2. meodorewan
3. charlie

Скоро 8 июня, в 19:30 состоится очередной Codeforces Round для участников из второго дивизиона. Участники из первого дивизиона могут поучаствовать вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), и Данил Сагунов (danilka.pro). Традиционно большое спасибо Gerald за помощь в подготовке в раунда, Delinur за переводы на английский и MikeMirzayanov за системы Codeforces и Polygon.

Распределение баллов по задачам будет таким 500 — 1000 — 1500 — 2000 — 2500.

Соревнование закончено, поздравляем победителей!

1. kuangbin10
2. ToumaKazusa
3. qiaoranpenxiang
4. rotoZOOM
5. umczca195

Разбор задач можно найти здесь

Удачи!

402A - Орехи

Достаточно просто перебрать количество коробок, которыми мы воспользуемся. Предположим, это число равно ans. Тогда всего мы можем получить ровно cnt = ans + min((k - 1) * ans, B) отсеков. Если cnt * v ≥ a, тогда ответ равен ans.

402B - Деревья в ряду

Достаточно перебрать высоту первого дерева от 1 до 1000. При фиксированной высоте первого дерева высоты деревьев однозначно определены, то есть имеют вид: a, a + k, a + 2k и так далее. После этого необходимо подсчитать количество операций, чтобы получить красивый ряд из деревьев при фиксированной минимальной высоте. Обновим ответ. После этого выведем для самой оптимальной высоты все операции.

402C - Ищем граф / 403A - Ищем граф

Опишу два решения.

Первое. Рассмотрим все пары чисел (i, j) (1 ≤ i < j ≤ n). Выведем 2n + p пар в лексикографическом порядке.

Во-первых, понятно что достаточно доказать, что 0-интересный граф верный. Более того, достаточно показать, что  - 3 интересный граф является верным. А как выглядит граф из первых 2n - 3 ребер. Очевидно, это граф имеет вид треугольников с общим ребром 1-2. Теперь предположим мы возьмем подмножество, которое не содержит вершины 1 и 2. Нетрудно увидеть, что в таких подграфах будет ноль ребер. Если в подмножестве ровно одна из вершин 1 или 2, то таких ребер будет k - 1, где k размер такого подграфа. Если две, то таких ребер 2 * (k — 2) + 1, где k размер подграфа.

Второе. Напишем перебор, который построит нам 0-интересные графы с количеством вершин 5, 6, 7, 8, 9. Теперь заметим, чтобы построить p-интерсный граф с n вершинами, достаточно построить 0-интересный граф, и потом в него p любых ребер, которых еще нет в графе. Как построить 0-интересный граф с n вершинами? Очень просто. Мы просто возьмем k несвязных компонент из построенных нами графов с вершинами от 5 по 9 так, чтобы суммарно в них было ровно n вершин.

402D - Улучшаем массив / 403B - Улучшаем массив

Опять опишу два решения.

Первое. Динамическое программирование. Подсчитаем динамическое программирование d[i][j] какое максимальный ответ мы можем получить, если перед нами сейчас префикс длины i и последний раз мы сокращали на gcd в позиции j. Понятно, что позиции следует перебирать в порядке убывания, как и размер префикса. Всего мы можем улучшить ответ в двух позициях в динамике из текущего состояния. А именно, d[i - 1][j] = max(d[i - 1][j], d[i][j]) — просто не будем сокращать на gcd текущий префикс. d[i - 1][i - 1] = max(d[i - 1][i - 1], d[i][j] + f(tgcd[j]) * i - f(tgcd[i - 1]) * i — выполним сокращение в текущей позиции. tgcd[i] — gcd всех чисел на префиксе длины i. Функция f(a) — возвращает красоту числа. Такую функцию просто реализовать за . Кроме того, можно ускорить работу этой функции, достаточно просто насчитать массив маленьких простых чисел. В таком решении очень важно не забыть, что каждый раз пересчитывать красоту чисел не нужно. Достаточно завести map < int, int >  — который сохранит уже посчитанные значения. База динамики d[n][n] = curBeauty — текущая красота массива.

Второе. Жадность. Возьмем самую правую позицию, которая может улучшить ответ. Выберем эту позицию, и сократим в ней на gcd. Докажем, почему так делать верно. Пусть оптимальное решение (последовательность сокращений) имеет вид r₁ > r₂ > ... > r_k. А мы построили решение l₁ > l₂ > ... > l_m используя жадность. Понятно, то r₁ ≤ l₁, поскольку до этого позиции  > l₁ не могли ничего улучшить, ведь иначе наша жадность взяла бы их в качестве своего первого выбора. С другой стороны, r₁ ≥ l₁, ведь иначе мы можем взять и сократить в позиции l₁ и только улучшить ответ, а это противоречило бы оптимальности решения r_i. То есть, r₁ = l₁, а значит, мы можем воспользоваться нашими соображениями и далее, для больших индексов i.

402E - Строго положительная матрица / 403C - Строго положительная матрица

Будем смотреть на матрицу a как на матрицу смежности некоторого графа из n вершин. Причем, если a_ij > 0, значит мы имеем ориентированное ребро в графе между вершинами (i, j). Иначе, мы получим, что ориентированного ребра нет. Тогда, пусть b = a^k. Тогда что обозначает b_ij? Верно, количество путей длины ровно k в нашем графе из вершины i в вершину j. Пусть pos такое, что a[pos][pos] > 0. То есть, у нас есть петля в графе. Значит, если из вершины pos достижимы все остальные вершины и наоборот, из всех остальных вершин достижима вершина pos, то тогда ответ YES, иначе ответ NO. Понятно, что если достижимость отсутствует, то понятно что для любого k a^k_ipos = 0. Если же достижимость имеется, то мы сможем добраться до петли, покрутиться некоторое количество раз в петле, а потом отправиться в нужную вершину.

403D - Красивые пары чисел

Во первых отметим, что на самом деле, длина последовательности не больше чем 50. Уже хорошо, а почему? Поскольку все числа b_i - a_i различны, то 0 + 1 + ... + 50 > 1000. Также представим, что мы имеем на самом деле последовательность попарно не пересекающихся отрезков, c_i = b_i - a_i + 1 — длина отрезка. . Хорошо. Посчитаем динамическое программирование: d[i][j][k] — количество последовательностей из чисел c₁ < c₂ < ... < c_i таких, что c_i ≥ 1 и c₁ + c₂ + ... + c_i = j и максимальное число в ней строго меньше чем k. Такая динамика поможет нам посчитать количество способов назначить длины отрезкам. Пересчитать такую динамику очень просто:

• база d[0][0][1] = 1,
• d[i][j][k + 1] = d[i][j][k + 1] + d[i][j][k] — просто увеличим верхнюю границу.
• d[i + 1][j + k][k + 1] = d[i + 1][j + k][k + 1] + d[i][j][k] — ставим текущую границу в последовательность, тем самым увеличиваем сумму и верхнюю границу.

Такую динамику нужно написать, используя O(N²) памяти, где N = 1000. После этого, умножим каждое d[i][j][k] на i!, поскольку мы располагать последовательность c_i не в порядке возрастания. Таким образом мы умеем считать количество способов назначить длины отрезков.

Хорошо. Теперь как получить ответ для n, k? Пусть sum[len] = d[k][len][x], где x — некоторая верхняя граница. Очевидно, что нам дополнительно нужно еще раздать еще n - len единичек. С помощью этих единиц мы можем увеличивать расстояние между отрезками. Количество способов раздать эти единички равно числу C(n - len + k, k). Таким образом, для каждого n просуммируем по len полученные величины и сложим в ответ.

Также следует обратить внимание на то, массив C[n][k] должен быть достаточно большим и аккуратно расставить размерности.

403E - Два корневых дерева

Во-первых для каждой вершины первого и второго дерева подсчитаем две величины in[s], out[s] — время входа и время выхода из вершины в порядке обхода dfs из вершины 1. Теперь с каждому ребру из обоих деревьев мы сопоставим пару (p, q) — где p = min(in[u], in[v]), q = max(in[u], in[v]) где величины in, out для каждой вершины мы берем из дерева другого цвета. Теперь для каждой дерева мы построим два дерева отрезков (в сумме 4 дерева отрезков, да). В первом дереве отрезков мы будем пары хранить в следующем виде: мы будем хранить пару в вершине (вершина дерева отрезков это некоторый отрезок (l, r)) дерева отрезков тогда и только тогда, когда ее левая граница лежит внутри отрека (l, r). Аналогично, во втором дереве отрезков мы будем хранить пару в вершине (вершина дерева отрезков это некоторый отрезок (l, r)) дерева отрезков тогда и только тогда, когда ее правая граница лежит внутри отрека (l, r). Все пары в дереве отрезков мы будем хранить по возрастанию правой границы (левой во втором дереве). Такие деревья отрезков требуют памяти, и построить можно за время .

Хорошо. Как теперь ответить на запрос (l, r) — удалить ребра из дерева, такое что одна из вершин имеет время входа внутри (l, r) ? Будем спускаться по дереву отрезков. Предположим, мы сейчас находимся в некоторой его вершине. Поскольку в первом дереве мы храним все пары по возрастанию правой границы, то ответ на запрос, это некоторый суффикс массива его правый границы. После того, как мы обработаем эти ребра и начнем следующий этап, нам нужно модифицировать наше дерево. А именно, для каждой вершины дерева, в которой мы рассматривали суффиксы мы должны их удалить, иначе мы можем обработать их несколько раз. Таким образом, имеем решение за .

Авторское решение по Е: 6052738

Скоро, 16 марта, 19:30 MSK, состоится очередной Codeforces Round #236 для участников из обоих дивизионов.

Автором задач являюсь я. Это мой первый раунд для обоих дивизионов, и я надеюсь не последний. Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке задач, Лось Илье (IlyaLos) и Александру Игнатьеву (aiMR) за тестирование, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

UPD: Распределение баллов:

Div. 2: 500 — 1000 — 1500 — 2000 — 2500

Div. 1: 500 — 1000 — 1500 — 1500 — 2000

UPD:

Соревнование закончено, поздравляем победителей!

Div.2 :

1. vladb
2. iceiceice
3. LoneFox
4. ofpsxx
5. adsz

Div. 1:

• 1 sillycross
• 2 KADR
• 2 vepifanov
• 4 Endagorion
• 5 glassices
• 6 cgy4ever
• 7 rowdark
• 8 snuke
• 9 ftiasch
• 10 fsouza

UPD:

Разбор задач на русском

UPD:

Статистика раунда от DmitriyH.

387A - Георгий и сон

Я опишу достаточно простое решение. Пусть Георгий проснулся в h₀ часов и m₀ минут, а спал ровно h₁ часов и m₁ минут. Получим числа h_p = h₀ - h₁ и m_p = m₀ - m₁. Если m_p < 0, то прибавим к нему 60 минут, а из h_p вычтем единицу. Потом, если окажется что h_p < 0, то прибавим к нему 24 часа. Вывести ответ на C++ очень просто следующей строкой:

Сложность решения: O(1) по времени / O(1) по памяти.

printf("%02d:%02d", h[p], m[p]).

Авторское решение: 5850831

387B - Георгий и раунд

Переберем количество требований на сложности, которые мы удовлетворим, остальные задачи мы придумаем и подготовим. Понятно, что если мы решили удовлетворить i требований, то выгодно взять те, что обладают минимальной сложностью. Упростим i самых сложных задач до самых легких требований. Если все прошло успешно, то обновим ответ величиной n - i.

Сложность решения: O(n²) по времени / O(n) по памяти. Отмечу, существует решение и за линейную сложность O(n + m).

Авторское решение: 5850888

387C - Георгий и число

Получим следующее неприводимое представление числа p = a₁ + a₂ + ... + a_k, где  +  — конкатенация, а числа a_i имеют вид x00..000 (некоторая ненулевая цифра, потом нули). Найдем самой большой индекс i, такой, что число a₁ + a₂ + ... + a_i - 1 < a_i. Если такого i нет, то i = 1. Тогда ответом на задачу будет число k - i + 1. Сравнения чисел можно производить, используя длину чисел и первые цифры. Попробуйте доказать это, используя единственность неприводимого разложения.

Сложность решения: O(n) по времени / O(n) по памяти.

Авторское решение: 5850919

387D - Георгий и интересный граф

Для решения данной задачи нужно знать что такое максимальное паросочетание.

Переберем центр графа i. Удалим все дуги вида (i, u) и (u, i). Пусть таких дуг cntWithI. Количество остальных дуг обозначим за Other. На остальных дугах и всех вершинах, кроме i, запустим алгоритм поиска максимального паросочетания, если полагать в качестве левой доли степень исхода, а в качестве правой степень захода. Дуга из нашего графа (i, j) будет равна дуге (i, j) — где i в левой доле, а j — в правой. Пусть его размер равен leng. Тогда ответ равен для текущей вершины равен 2n - 1 - cntWithI + Other - leng + (n - 1) - leng. Обновим глобальный ответ. Почему так можно делать? Понятно, что если мы найдем максимальное паросочетание в графе, мы удовлетворим максимально возможное количество требований на степени исхода и захода. Поэтому ребра из максимального паросочетания мы удалять не будем, удалим все кроме максимального паросочетания, и дополним его до полного паросочетания добавив (n - 1) - leng ребер. Следует добавить, что важно требование, что петли разрешены. Без этого разрешения так решать задачу нельзя.

Сложность решения: O(n²m) по времени / O(n + m) по памяти.

5850946

387E - Георгий и карточки

Посчитаем массивы pos[i] — позиция числа i перестановке p, и need[i] — нужно ли удалить число i из перестановки p.

Теперь рассмотрим числа a₁, a₂, ..., a_n - k — числа, которые нужно удалить. Понятно, что их выгодно удалять в порядке возрастания, это нетрудно доказать.

Теперь будем иди по всем числам от 1 до n. Дополнительно будем поддерживать упорядоченное множество (set <> в с++, TreeSet в Java) — позиции не удаленных чисел, строго меньших текущего. Эти числа, как раз, могут создать <<препятствия>> для позиции текущего числа. Данное множество очень просто поддерживать. Для удобства, можно добавить в данное множество числа  - 1 и n. Теперь очень просто узнать размер максимального подотрезка, на котором число будет минимум. Это делается с помощью стандартных функций языка программирования (lower и higher в Java) Теперь осталось воспользоваться деревом Фенвика, чтобы узнать количество еще не удаленных чисел на данном отрезке.

Сложность решения: по времени / O(n) по памяти.

Очень короткая реализация решения на языке Java: 5850986

Всем привет!

Скоро, 30 января, 19:30 MSK, состоится очередной Codeforces Round #227 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Автором задач являюсь я. Большое спасибо Гере Агапову (Gerald) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Главный герой задач этого раунда — кот Георгий.

UPD1: Распределение баллов будет таким: 500, 1000, 1500, 2000, 2500.

UPD2: Соревнование закончилось, поздравляем победителей!

1. Sorto
2. graphis
3. InternationalGrandmaster
4. Skedar
5. mateusz

UPD: Разбор на русском

UPD: Статистика

369A - Валера и тарелки

Будем действовать жадно. Пусть сейчас i-й день, и текущее блюдо типа 1. Тогда если у нас есть чистая глубокая тарелка, то воспользуемся ею. Иначе увеличим ответ. Если текущее блюдо типа 2, то мы сначала попробуем взять плоскую тарелку, а потом глубокую. Если чистых тарелок нет совсем, то увеличим ответ.

Авторское решение: 5306397

369B - Валера и олимпиада

В этой задаче требовалось найти такой массив a₁, a₂, ..., a_n, что верны условия:

1. r ≥ a₁ ≥ a₂ ≥ ... ≥ a_n ≥ l;
2. ;
3. ;

Понятно, что сумму s_k нужно распределить равномерно между первыми k элементами. Например, так:

remainder = (s_k mod k);
for(int i = 0; i < k; i++) 
{
	a_i = s_k / k + (remainder > 0);
	remainder = remainder - 1;
}

Если k ≠ n, то аналогично нужно поступить с остальными элементами, причем распределить им нужно s_all - s_k.

Многие не учитывали случай k = n, в результате получали RE11.

Авторское решение: 5306414

369C - Валера и выборы

Рассмотрим все дороги, которые нам нужно отремонтировать. Пометим их концы u, v белым цветом. После этого, посчитаем простую динамику d[v] (v — вершина в дереве) на дереве, которая для каждой вершины в дереве посчитает количество белых вершин в поддереве. Это просто посчитать примерно так c помощью рекурсивной функции calc(v, prev) (v — текущая вершина, а prev — ее непосредственный предок):

calc(v, prev)
{
	d[v] = 0; 
	if (white[v])
		dv += 1; 
	для всех u, таких что существует ребро (u,v) или (v,u) u != prev:
		calc(u, v);
		d[v] += d[u];  
}

После этого, добавим к ответу количество белых вершин v, для которых d[v] = 1

Авторское решение: 5306500

369D - Валера и дураки

Пусть p[A] — вероятность того, что дурак с номером A попадет, если совершит выстрел.

Заметим, что состояние очень просто описать парой чисел (A, B), где A — номер самого левого дурака, B — второго слева по порядку дурака. Понятно, что все дураки с индексами  ≥ B останутся живы. Выполним bfs по этим состояниям.

Состояние (0, 1) достижимо в любом случае, потому что оно изначально. Поэтому сразу положим его в очередь. Далее, из текущего состояния в очереди мы можем перейти максимум в три состояния:

1. (B + 1, B + 2) — только если p[A] > 0 и существует такой дурак с номером j ≥ B, у которого p[j] > 0.
2. (A, B + 1) — только если p[A] > 0 и не существует такой дурак с номером j ≥ B, у которого p[j] = 100.
3. (B, B + 1) — только если p[A] ≠ 100 и существует такой дурак с номером j ≥ B, у которого p[j] > 0.

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

Авторское решение: 5306516

369E - Валера и запросы

Давайте поддержим множество xs[y] — все отрезки, чьи правые границы в точности равны y. Теперь сведем нашу задачу к другой. Для каждого запроса посчитаем количество отрезков, которым не принадлежит ни одна точка. Пускай это значение v. Тогда ответ на запрос это n - v. Добавим к нашему запросу точки 0 и точку MV + 1, где MV = 1000000. Пусть точки запроса имеют вид x₁ < x₂... < x_n. Рассмотрим x_i и x_i + 1. Пусть p_i это количество отрезков которые лежат строго внутри x_i и x_i + 1. Тогда v = p₁ + p₂ + ... + p_n - 1. Чтобы найти значения p_i нужно поступить так. Рассмотрим все такие пары (x, x_i + 1) по всем запросам и сложим их во второе множество xQ[r] — все пары, у которых правая граница равна r. Тогда чтобы узнать значения p для пар (x_i, x_i + 1) будем перебирать по возрастанию правую границу. Дополнительно будем поддерживать дерево Фенвика, которое умеет делать  +  = 1 в точке, и брать сумму на префиксе. Пусть i — текущая правая граница. Тогда мы можем узнать значение p для всеx пар (l, r), у которых правая граница равна i (l, i). Пусть j левая граница пары. Тогда ответом для пары будет значение S - sum(j), где S — количество добавленных в дерево Фенвика левых границ, а sum(j) — сумма на префиксе j. После этого, для текущей координаты нужно рассмотреть все отрезки, в множестве xs[i]. Пусть j левая граница отрезка. Тогда нам нужно сделать  +  = 1 в точке j в нашем дереве Фенвика. Итого, общая сложность решения .

Авторское решение: 5306535

Всем привет!

Скоро, 29 ноября в 19:30 MSK, состоится очередной Codeforces Round #216 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Лось Илья (IlyaLos).

Большое спасибо Гере Агапову (Gerald) и Сергею Сухову (Serega) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

UPD1: Распределение баллов будет таким: 500, 1000, 1500, 2000, 2500.

UPD2: Это была опечатка с распределением, теперь все верно.

UPD Соревнование закончено, поздравляем победителей!

1. Dshovn
2. WhitedarkWalker
3. hexor
4. Pandii
5. Ronnoc_2

Удачи!

359A - Таблица

Давайте рассмотрим все ячейки, которые расположены в первой строке. Очевидно, что если хотя бы одна из них хорошая, то ответ равен двум. Аналогично, если хорошая ячейка расположена в первом столбце, либо в последней строчке или в последнем столбце, ответ также два. Иначе, ответ равен четырем.

Авторское решение: 4968279

359B - Перестановка

Ответом будет являться немного изменненая перестановка 1, 2, ..., 2n. Для каждого 1 ≤ i ≤ k поменяем местами числа 2i - 1 и 2i. Не трудно проверить, такая перестановка будет хорошей.

Авторское решение: 4968385

359C - Простое число

Очевидно, что ответ это x^v. Пусть sum = a₁ + a₂ + ... + a_n. Тогда рассмотрим все числа вида s_i = sum - a_i. Тогда, чтобы узнать, чему равно v мы поступим так: Рассмотрим систему счисления по основанию x, где s_i — разряд. Тогда, когда мы выполним все переносы по степеням, нужно найти минимальный разряд, в котором стоит не ноль. Тогда v будет равно именно этому разряду. Чтобы выполнить переносы, можно было бы поступить так. Рассмотрим последовательность степеней как убывающую последовательность. Теперь будем выполнять следующее "пока можно". Возьмем минимальную степень v, посчитаем количество слагаемых cnt, которые имеют такую же степень. Если cnt кратно x, тогда мы их заменим cnt / x слагаемых вида v + 1. Поскольку последовательность степеней была убывающей, мы можем просто приписать их в конец. Если же cnt не кратно x, тогда мы нашли нужную минимальную степень v. Также стоит не забывать, что v = min(v, sum).

Авторское решение: 4968346

359D - Пара чисел

Достаточно очевидное замечание: если пара (l, r) удовлетворяет условию 1, тогда min(l, r) = НОД(l, r). Где min(l, r) — минимум на подотрезке (l, r). Аналогично, НОД(l, r) — НОД всех чисел на подотрезке (l, r). Посчитаем структуру данных, которая позволит нам быстро отвечать на запросы минимума на отрезке и НОД на отрезке, например за O(1). Это можно достичь используя структуру данных Sparce Table. Конечно, на запрос НОД(l, r) мы не сможем отвечать за O(1), однако будет достаточно быстро работать. Также стоит отметить, что решение, которое использует дерево отрезков, очень вероятно получит TL. Воспользуемся бинарным поиском для того, чтобы найти максимальное возможное значение r - l:

lf = 0;  //левая граница поиска
rg = n;  //правая граница поиска
while (rg - lf > 1) {
  int mid = (lf + rg) / 2;
  if (ok(mid))   //ok(mid)
    lf = mid;
  else
    rg = mid;
}

ok(mid) — функция, которая определяет, существует ли отрезок который удовлетворяет условию min(l, r) = НОД(l, r) и mid = r - l. Если таковой есть, то обновим границы бинпоиска. После того, когда мы узнаем величину r - l восстановить ответ не составит труда.

Здесь есть информация про Sparce Table

Авторское решение: 4968587

359E - Порядок

Запустим рекурсивную функцию, которая включит свет во всех комнатах, где это возможно. Кроме того, она посетит все комнаты, среди тех, которые возможно посетить. Пусть эта функция называется paint(x, y), где x, y — текущая комната. Эта функция будет работать так: Посмотрим во все 4 направления. Если в заданном направлении идти можно по правилу 3 из условия, и клетка (nx, ny) еще не посещена, рекурсивно пойдем именно в эту клетку. Кроме этого, будем включать свет везде, где можно. Если мы не посетили нашей функцией некоторую клетку, где есть свет, то ответ NO. Иначе ответ есть. Далее с помощью обхода в ширину посчитаем для каждой комнаты, в которой включен свет, расстояние от старта, причем разрешается ходить только по тем комнатам, где свет горит. Пусть для комнаты (x, y) это значение равно dist(x, y). Теперь запустим похожую рекурсивную функцию, которая будет выключать свет. Эта функция будет работать так: Посмотрим во все 4 направления. Если в заданном направлении в комнате (nx, ny) еще горит свет, а dist(nx, ny) > dist(x, y), то запустим нашу функцию рекурсивно от (nx, ny), а потом вернемся в текущую комнату. Если такой соседней клетки нет, выключим свет. Более подробно детали можно изучить в моем решении.

Авторское решение: 4968657

Всем привет!

Скоро, 2 ноября, 12:00 MSK, состоится очередной Codeforces Round #209 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса. Обратите внимание на время старта раунда!

Автором задач являюсь я. Большое спасибо Гере Агапову (Gerald) и Лось Илье (IlyaLos) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

UPD1: Распределение баллов будет таким: 500, 1000, 1500, 2500, 2500.

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

1. cptbtptp
2. FancyCoder
3. Oyk
4. E.B.
5. orzkbc

UPD3: Разбор задач

Удачи!

350A - TL

Пусть v = min(a_i), p = max(a_i), c = min(b_i). Тогда если max(2 * v, p) < c, то ответ max(2 * v, p). Иначе ответ  - 1.

Авторское решение: 4632352

350B - Курорт

В этой задаче достаточно было реализовать следующее. По сути там задан граф, в виде массива предков для каждой вершины. Поскольку у каждой вершины максимум один предок, то для каждой вершины, являющейся отелем запустим такой алгоритм: будем подниматься по предкам prev[v] до тех пор, пока не встретим вершину со степенью исхода большей единицы. Степень исхода лучше посчитать заранее. После всего обновим ответ.

Асимптотика решения O(n) по времени и O(n) по памяти.

Авторское решение: 4632399

350C - Бомбы

Главная идея, это отсортировать все точки в порядке возрастания величины |x_i| + |y_i|. Дальше будем обрабатывать каждую точку жадно, максимум за шесть ходов. А именно, пусть мы хотим дойти сейчас до точки (x, y). Пусть x ≠ 0. Тогда нам нужно переместиться ровно на |x| в нужном направлении (если x < 0 то по направлению L, x > 0 — R). Аналогично сделаем для y-координаты. Теперь мы пришли в точку (x, y), возьмем в этой точке бомбу, и аналогично вернемся назад. Почему верно сортировать по так называемому манхэттенскому расстоянию? Понятно, что если мы посмотрим на путь, который мы получили, можно заметить, что все точки пути имеют меньшее манхэттенское расстояние, а значит их мы обработаем раньше.

Асимптотика авторского решения

Авторское решение: 4632478

350D - Поиск сов

Будем решать задачу в целых числах. Поэтому всегда будем строить прямую в целых числах. Операцией нормализации прямой будем называть следующее: Пусть у нас есть прямая Ax + By + C. Пусть также g = gcd(A, gcd(B, C)) (gcd(0, 0) = 0).
Если А < 0 (или A = 0 и B < 0), то умножим уравнение на -1 и поделим все коэффициенты на g.

Теперь решение. Будем поддерживать два отображения (map<> на С++, TreeMap(HashMap) на Java) из прямой, в множество точек (некоторые точки могут встречаться несколько раз). В первом отображении в качестве множества точек мы будем хранить левые границы отрезков, во втором правые границы отрезков (в отсортированном виде).

Заранее по каждому отрезку построим прямую, нормализуем ее, и поддержим наши указанные выше множества множества. Далее, для каждого возможного уравнения отсортируем указанные множества.

Теперь переберем две окружности. Проверим, что расстояние между их центрами больше суммы радиусов и что радиусы одинаковы. Пусть мы построили прямую через центры (x1, y1) и (x2, y2). Перпендикулярная ей прямая, проходящая через центр отрезка [(x1, y1), (x2, y2)] будет иметь уравнение A = 2(x1 - x2), B = 2(y1 - y2), C =  - ((x1 - x2) * (x1 + x2) + (y1 - y2) * (y1 + y2)). После этого бинарным поиском по множеству точек, соответствующих указанной прямой, найдем две величины: cntL — количество отрезков, у которых левая граница правее ((x1 + x2) / 2, (y1 + y2) / 2) и cntR — количество отрезков, у которых правая граница левее ((x1 + x2) / 2, (y1 + y2) / 2). Тогда к ответу нужно прибавить величину cntV - cntR - cntL, где cntV — количество отрезков соответствующих заданной прямой в отображении.

Итого, решение за .

Код: 4632546

350E - Неверный Флойд

Решение задачи очень простое, главное придумать почему это верно. Будем действовать так: построим граф с максимальным возможным количеством ребер, потом удалим лишнее. Во-первых, если k =  = n, то ответ -1. Иначе зафиксируем некоторую помеченную вершину, например a₁. Возьмем в наш граф все ребра, кроме ребер вида a₁ <  -  > x, где x — помеченная вершина. Теперь почему так действовать верно. Если алгоритм Валеры работает неверно, значит существуют пара вершин (i, j) такая, что кратчайшее расстояние посчитано неверно. Значит, на кратчайшем пути из вершины i в вершину j есть хотя бы одна не помеченная вершина (причем, что важно, она не должна совпадать ни с i, ни с j. Если бы такой вершины не было, кратчайшее расстояние посчиталось бы верно. Более того, не нарушая общности, будем считать, что кратчайшее расстояние между i и j равно двум, а алгоритм Валеры нашел больше. Далее, для более формального доказательства нужно рассмотреть случаи, в зависимости от того какой тип имеет каждая из вершин (i, j), однако я рассмотрю случай, когда мы получим больше всего ребер, а именно когда и i, и j — помеченные вершины (а их по условию всегда не меньше двух :)). Во-первых, проведем все ребра во между не зафиксированными ребрами. Дальше проведем и из i и из j ребра в не помеченные вершины. После этого проведем из i все ребра в помеченные, кроме вершины j. Понятно, что больше добавлять ребер нельзя, так как иначе алгоритм Валеры посчитает все верно. Таким образом, мы проведем ровно ребер.

Код: 4632600

BONUS Простой бонус. Можете ли вы для аналогичных входных построить граф, где алгоритм Валеры будет работать верно?

Всем привет!

Скоро (1 октября, 19:30 MSK) состоится очередной Codeforces Round #203 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Автором раунда являюсь я. Хочется сказать большое спасибо Гере Агапову (Gerald) за помощь в подготовке и за хорошие предложения по задачам. Спасибо Лось Илье (IlyaLos) за тестирование задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon. Также спасибо Игнатьеву Александру (aiMR) за тестирование задач и идею одной из них.

Удачи!

UPD: Будет использоваться динамическое распределение баллов. Задачи расположены в порядке увеличения сложности (по мнению авторов).

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

1. fanhqme
2. FAU.COACH
3. Witalia
4. sokian

UPD: Разбор

336A - Медведь Василий и треугольник

Пусть val = |x| + |y|. Тогда первая точка имеет вид (val * sgn(x), 0), а вторая — (0, val * sgn(y)), где sgn(a) — знак числа a. При необходимости нужно поменять точки местами.

Теперь поймем, почему это верно. Во-первых, заметим, что из условий x ≠ 0 и y ≠ 0 следует, что одна точка находится на оси OX, другая — на оси OY. Рассмотрим случай, когда x > 0 и y > 0 (остальные случаи рассматриваются аналогично). Построим треугольник с вершинами, указанными выше. Нужно показать, что точка (x, y) находится строго на границе треугольника, т.е. принадлежит отрезку, проходящему через точки: (x + y, 0) и (0, x + y) (если она находится внутри треугольника, то условие 5 задачи не будет выполняться). Через точки (x + y, 0) и (0, x + y) проходит прямая Y =  - X + x + y. Подставив точку (x, y) вместо X, Y соответственно, получим, что точка (x, y) принадлежит прямой, проходящей через точки (x + y, 0) и (0, x + y). А так как x > 0 и x < x + y, то точка (x, y) принадлежит и отрезку между точками (x + y, 0) и (0, x + y).

Авторское решение

336B - Медведь Василий и муха

Можно было итеративно посчитать все пройденное расстояние и поделить его на m² в конце. Переберем стартовую окружность 1 ≤ i ≤ m. Нетрудно заметить, что до окружности с номером m + i мы дойдем за 2R. Далее если |j - i| = 1 то расстояние равно . До остальных окружностей расстояние посчитать нетрудно: слева у нас i - 2 окружности причем расстояние сумма расстояний до них равна сумме . Аналогичная ситуация справа.

Авторское решение

336C - Медведь Василий и последовательность

Переберем красоту ответа по убыванию от 29 до 0. Попробуем найти для текущего значения красоты i такое подмножество, красота которого была бы равна i. Возьмем все числа, в двоичном представлении которых есть бит i. Возьмем побитовое И всех этих чисел. Если значение побитового И делится на 2ⁱ, то мы нашли искомое подмножество, иначе такого подмножества нет. Таким образом, получили решение за O(30n). Доказательство того, что данный алгоритм найдет оптимальный ответ, предоставлю читателю.

Авторское решение

336D - Медведь Василий и красивые строки

Пусть any — любая строка из нулей и единиц, s + g — конкатенация строк, MOD = 1000000007.

Нетрудно заметить, что строка вида 1 + any всегда перейдет в 0, а строка 1 — в 1. Строка вида 01 + any всегда перейдет в 1, а строка 01 — в 0. Аналогично, строка вида 001 + any всегда перейдет в 0, а строка 001 — в 1, и так далее. На основе этих утверждений получаем описанное ниже решение.

Рассмотрим отдельно случаи, когда в строке ноль нулей или ноль единиц. Теперь переберем позицию i (в 0-индексации) первой единицы в нашей строке и определим, во что перейдет наша строка. Если она перейдет в то число, которое нужно нам, то добавим к ответу число C(cnt[0] + cnt[1] - i - 1, cnt[1] - 1), где C(n, k) — биномиальный коэффициент. Заметим, что использовать для вычисления биномиальных коэффициентов треугольник Паскаля нельзя, поскольку число n слишком большое. Подсчитаем массив fact[i] = i!%MOD, . Тогда C(n, k) = fact[n]inv(fact[n - i]fact[i]), где inv(a) — обратный элемент в кольце по модулю MOD. Так как модуль простой, то inv(a) = a^MOD - 2. Для вычисления этой величины можно применить бинарное возведение в степень.

Авторское решение

336E - Медведь Василий и покраска квадрата

Достаточно трудная задача. Будем считать динамику dp[lvl][op][cur][type] — количество способов зафиксировать на рисунке op треугольников, если у нас на рисунке 2lvl + 1 квадратов (cur, type — вспомогательные параметры). Ответом на задачу тогда будет число dp[n][k][0][2]k!. Поясним, что значат параметры cur, type. Параметр type отвечает за тип переходов, который мы будем производить, cur — количество использованных четвертей на рисунке (cur = 4 — 2 четверти, cur < 4 — cur четвертей). Следует отличать cur = 2, cur = 4, так как количество последовательных пар неиспользованных четвертей различно.

Теперь переходы. type = 2. Переберем количество пар (с учетом значения cur) последовательных четвертей, которые мы зафиксируем. Очень важно, чтобы эти пары не пересекались по четверти. (Таким образом, мы можем взять две пары только в случае cur = 0). Также зафиксируем некоторые одиночные четверти. Посчитаем количество способов выбрать соответствующие треугольники. И прибавим к текущему значению динамики dp[lvl][op - choosen][newcur][1] * cntwaystochoose. Более подробно можно изучить переходы type = 2. в моем решении. (calc(n, k, cur, type) — считает как раз dp[n][k][cur][type]).

Теперь type = 1. Теперь мы будет фиксировать треугольники по краям рисунка (количество квадратов на рисунке 2*lvl + 1). По краям рисунка имеются в виду треугольники помеченные крестиком на рисунке.

Переберем количество пар (с учетом значения cur) последовательных треугольников, которые мы зафиксируем. Очень важно, чтобы эти пары не пересекались по треугольнику. Также зафиксируем некоторые одиночные треугольники. Посчитаем количество способов выбрать соответствующие треугольники. И прибавим к текущему значению динамики dp[lvl][op - choosen][cur][0] * cntwaystochoose.

Теперь type = 0. Вновь фиксировать треугольники по краям рисунка (количество квадратов на рисунке 2*lvl). По краям рисунка имеются в виду треугольники помеченные крестиком на рисунке.

Зафиксируем некоторые одиночные треугольники. Посчитаем количество способов выбрать соответствующие треугольники. И прибавим к текущему значению динамики dp[lvl - 1][op - choosen][cur][2] * cntwaystochoose. База динамики: dp[0][0][cur][1] = 1, dp[0][cnt][cur][1] = 0, cnt > 0.

Авторское решение

Всем привет!

Скоро (9 августа, 19:30 MSK) состоится очередной Codeforces Round #195 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Автором раунда являюсь я. Выражаю благодарность Геральду Агапову (Gerald) за помощь в подготовке задач, Евгению Соболеву (Seyaua), Виталию Аксёнову (Aksenov239) и Сергею Сухову (Serega) за тестирование задач, Александру Игнатьеву (aiMR) за тестирование задач и перевод разбора на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой (Delinur) за перевод задач на английский язык.

Всем удачи и высокого рейтинга!

UPD: Разбор задач

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

1. Triolossus_3
2. WHITE2302
3. PM2.5

Отдельно хочется поздравить Егора Куликова (Egor) — единственного человека, который сдал все задачи!

305A - Странное сложение

Простая задача на реализацию.

1. Если у нас есть в множестве числа 0 или 100, то обязательно возьмем их в подмножество.
2. Если у нас есть число, отличное от 0 и меньшее 10, возьмем его в подмножество.
3. Если у нас число, отличное от 0 и 100, которое делится на 10 без остатка, тоже возьмем его.
4. Если у нас есть число, отличное от чисел, описанных в пунктах 1 - 3 и в изначальном множестве нет чисел из пункта 2 и 3, то возьмем одно такое число.

Решение

305B - Цепные дроби

Указанные ограничения позволяют нам говорить, что представление рациональной дроби в конечную цепную почти единственно. Вернее их не больше чем 2. Поэтому построим жадно представление рациональной дроби в конечную цепную, и проверим, совпадают ли они.

Решение

305C - Иван и степени двойки

Во-первых, выполним все возможные переносы по степеням. Более формально, если у нас пара чисел, a_i = a_j, i ≠ j, заменим ее на одно число a_i + 1. Теперь, когда все a_i различны, то ответ очевиден — max(a_i) — cnt(a_i) + 1, где max(a_i) — максимальное число в массиве, cnt(a_i) — количество чисел в массиве

Решение

305D - Оля и граф

Во-первых, удобно расположить все вершины на координатной прямой. Далее в графе обязательно нужны ребра из i -  > i + 1. Кроме этого, в граф можно добавлять ребра из i -  > i + k + 1 (ребра типа 2). Не трудно доказать, что других ребер добавлять нельзя. Сразу считаем ребра, и определим, ответ 0 или != 0 . Далее ответ 0 еще тогда, когда все ребра 2 типа не имееют общего пересечения, если рассматривать как отрезки на координатной прямой. Причем это верно почти всегда, кроме случаев когда k ≥ n - 1. В этих случаях, ответ всегда 1. Теперь ответ != 0. Из всех ребер которые у нас есть, оставим только ребра типа 2. Если ребер типа 2 нет, то прибавим к ответу 1, так как мы сейчас можем ничего не добавлять. Иначе переберем вершину i, из которой мы проведем ребро 2 типа и аккуратно прибавим к ответу величину 2^cnt, cnt — это количество вершин на промежутке от [i, min(i + k, n — k — 1)] из которых не исходят ребра. Причем важно, чтобы все имеющиеся ребра были на этом промежутке. Таким образом, это решение за O(n + m). Отмечу, что у этой задачи есть решение за O(m + log(n)). Однако, заходит и O(n + m).

Решение O(n + m) Решение O(m + log(n))

305E - Игра со строкой

Чтобы решить эту задачу, необходимы некоторые знания по теории игр. Рассмотрим некоторую подстроку строки s s[i... j], такую, что все символы с i по j являются центрами палиндромов, а символы i - 1, j + 1 уже нет. Утверждается, что такую подстроку можно рассмотреть отдельно. Каждую такую подстрочку нетрудно закодировать единственным числом: len — просто количество символов в ней. И так, будем считать grundy[len] — значение функции Гранди. Пусть мы решили удалить символ в позиции 0 ≤ i < len. Тогда нетрудно понять, что игра распадется на 2 независимых игры: У первой игры будет длина i - 1, а у второй len - i - 2, так как соседние к i символы перестанут быть центрами. Таким образом, получим решение за O(n²). Скажу, что еще есть решение за O(n), но опять таки, это уже не требовалось.

Решение

Всем привет!

Очень скоро, 19 мая в 17:00 MSK, состоится очередной Codeforces Round #184 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Игнатьев Александр (aiMR). Это наш второй раунд, и мы надеемся, что не последний. Выражаем благодарность Геральду Агапову(Gerald) за помощь в подготовке задач, Михаилу Мирзаянову(MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой(Delinur) за перевод задач на английский язык.

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

Настоятельно рекомендую Вам прочесть условия всех задач!

Всем удачи и высокого рейтинга!

UPD1: Распределение баллов будет стандартным: 500, 1000, 1500, 2000, 2500.

UPD2: Разбор задач

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

1. SillyHook06
2. hyplymac
3. HAPKOMAH

300A - Массив

В этой задаче нужно было просто реализовать следующий алгоритм. Разделим входной массив на 3 вектора: первый будет содержать все отрицательные числа, второй — все положительные числа, третий — ноль. Если первый вектор содержит четное количество элементов, то переместим ровно одно число в третий вектор. Если второй вектор пуст, то переместим ровно 2 элемента из первого вектора во второй.Такое решение работает за O(n)

Авторское решение

300B - Тренер

Заметим, что входных данных задан некоторый граф. Заметим, что если в этом графе есть хотя бы одна компонента связности, в которой как минимум 4 вершины, то ответ очевидно  - 1. Сразу следует заметить, что все компоненты связности, в которых уже ровно 3 вершины, уже образуют некоторую команду. Далее у нас остались компоненты связности, в которых либо 1 вершина, либо 2. Не трудно понять, что если количество компонент, в которых ровно 2 вершины больше количества компонент с 1 вершиной, то ответ  - 1. Иначе решение существует. Каждой компоненте из 2 вершин сопоставим одну компоненту из 1 вершины. Далее соединим все одноэлементые компоненты в группы по 3. Таким образом, получим решение за ассимптотику O(n + m).Также следует отметить, что также можно было написать решение и за ассимптотику O(n⁴).

Авторское решение

300C - Прекрасные числа

Пусть MOD = 1000000007. Для начала подсчитаем массив fact[i] = i!%MOD, . Далее будем перебирать, сколько раз встретится цифра a в искомом числе. Пусть она встречается i раз. Тогда очевидно, что мы можем подсчитать какова сумма цифр в нашем числе сейчас: val = ai + b(n - i). Если число val — хорошее, то к ответу нужно прибавить C[n][i]. Однако n слишком большее, чтобы считать биномиальные коэффициенты используя треугольник Паскаля. Тогда C[n][i] = fact[n]inv(fact[n - i]fact[i]). inv(a) — обратный элемент в кольце по модулю. Так как модуль простой, то inv(a) = a^MOD - 2. Возвести число a в степень, можно используя бинарное возведение в степень.

Авторское решение

300D - Покраска квадрата

Эта картинка полезна для понимания.

Переформулируем задачу в терминах графов:

Нам задана таблица n × n, которая представляет некоторый граф следующего вида:

1. Этот граф — дерево
2. У всех вершин, кроме листьев, ровно четыре сына
3. Пусть некоторая вершина удалена от корня на расстояние k. Тогда существует ровно 4^k вершин, которые также удалены на расстояние k.

Нам нужно покрасить ровно k вершин этого графа. Причем, если вершина i покрашена, то тогда покрашены все вершины, лежащие на пути из вершины 1 до вершины i.

Понятно, что мы можем однозначно восстановить дерево по его высоте. Высоту графа можно найти с помощью простого кода:

int height = 0;
while (n > 1 && n % 2 == 1) {
	n /= 2; height++;
}

Поэтому заведем следующее динамическое программирование: z[i][j] — количество способов раскрасить граф высоты i за j операций.

Можно привести простой код решения за ассимптотику O(k⁴log(n)):

z[0][0] = 1; z[0][i] = 0, i > 0; z[i][0] = 1, i > 0
z[i][j] = 0;
for(int k1 = 0; k1 <= j - 1; k1++) 
  for(int k2 = 0; k2 <= j - 1 - k1; k2++)
    for(int k3 = 0; k3 <= j - 1 - k1 - k2; k3++)
      {
         int k4 = j - 1 - k1 - k2 - k3;
	 z[i][j] += z[i-1][k1] * z[i-1][k2] * z[i-1][k3] * z[i-1][k4];
	 z[i][j] %= mod;
      }

Однако такое решение работает долго. Пусть z[i][j] — означает что оно и означало раньше:количество способов раскрасить граф высоты i за j операций. Однако посмотрим на него с другой стороны: z[i][j] — коэффициент при j степени i-ого многочлена. Тогда не трудно заметить что z[i + 1][j + 1] — коэффициент при j степени i-ого многочлена, возведенного в 4 степень. Таким образом получим решение за ассимптотику O(k²log(n)). Модуль, указанный в условии, позволяет так же воспользоваться быстрым преобразованием Фурье и написать решение за ассимптотику O(klog(k)log(n)). Однако такое решение все равно может получить ТЛ, если вы часто будете брать по модулю. Так как модуль довольно не большой ( ≤ 10⁷) можно брать по модулю реже. Это позволяет ускорить работу решения в несколько раз.

Авторское решение. Использует FFT

Авторское решение. Без FFT

300E - Империя наносит ответный удар

Пусть . val это верхняя граница ответа. val! делится на , это просто доказать, используя то факт, что . Так же, — мультиномиальный коэффициент. Итак, ответ не превосходит 10¹³.

Если n! делится на den, тогда (n + 1)! также делится на den. Это означает, что мы можем использовать бинарный поиск по ответу.

Для всех i, i = 2..., 10⁷, посчитаем максимальное простое в i, используя линейное решето Эратосфена. Пусть для i — это lp[i]. Также предпосчитаем все простые  ≤ 10⁷.

Далее предпосчитаем cnt[i] — количество чисел a, i <  = a.

Теперь мы можем посчитать факторизацию знаменателя:

for(int i = max; i>=2; i--) {
 if (lp[i] != i) 
  cnt[lp[i]] += cnt[i];
 cnt[i / lp[i]] += cnt[i];
}

Далее воспользуемся бинарным поиском от lf = 1 до .

Авторское решение

Всем привет!

Очень скоро, 25 апреля в 19:30 MSK, состоится очередной Codeforces Round #181 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Игнатьев Александр (aiMR). Выражаем благодарность Геральду Агапову(Gerald) за помощь в подготовке задач, Михаилу Мирзаянову(MikeMirzayanov) за замечательные системы Codeforces и Polygon, Марии Беловой(Delinur) за перевод задач на английский язык.

Немного информации об авторах: я и Александр — студенты 3 курса Механико-Математического факультета Саратовского Государственного Университета. Для нас это первый раунд и, я думаю, что не последний.

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

Также настоятельно рекомендую Вам прочесть условия всех задач!

Всем удачи и высокого рейтинга!

UPD: Разбалловка задач будет динамической. Задачи расположены в порядке предполагаемой сложности.

UPD1: Разбор задач

UPD2: Соревнование закончено. Поздравляем победителей:

1. ballmaids02
2. VIProgrammer
3. emachaidze