Сначала расположим задачи по сложности, как предполагалось авторами: A, D, B, C, E. Теперь разберем задачи по порядку следованию в соревновании.

208A - Дабстеп

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

208B - Пасьянс

В этой задаче можно было написать поиск в ширину. В качестве состояния можно взять следующую четверку: количество оставшихся стопок, а также три строки, которые обозначают три крайние правые карты на трех крайний стопках. Соответственно мы имеем два перехода в общем случае, когда перекладываем последнюю карту на 1, либо на 3 влево. Если количество стопок в какой-то момент окажется равным 0 выводим YES, иначе NO. Состояний O(N⁴), переходов 2, итого временная сложность решения O(N⁴).

208C - Контрольный пункт полиции

В данной задаче для каждой вершины отдельно посчитаем искомую величину и найдем среди них максимальную. Для этого для каждой вершины v посчитаем две величины: cnt1[v] и cnt2[v] — количество кратчайших путей из вершины v в n-ую вершину и 1-ую вершину соответственно. Чтобы это сделать, нужно построить граф кратчайших путей и посчитать на новом графе динамику (поскольку полученный граф будет ациклическим). Чтобы построить граф кратчайших путей, нужно оставить в графе только полезные ребра, предварительно запустив, например, поиск в ширину из вершин 1 и n соответственно.

После того, как величины cnt1[v] и cnt2[v] посчитаны, переберем все полезные ребра исходного графа (u, v) и к вершинам u и v прибавим величину (cnt2[u] * cnt1[v]) / (cnt2[n–1]), которая является вкладом этого ребра в искомую величину для вершин u и v. Заметим, что величина (cnt2[n–1]) — это общее количество кратчайших путей от вершины 1 до n. Все величины, которые были упомянуты, можно посчитать за размер исходного графа. Вычислительная сложность решения O(N + M).

208D - Призы, призы и еще раз призы

В этой задаче после каждого нового получения очков нужно было жадно набрать себе призов. Для этого переберем призы, начиная с самого дорогого, и попробуем взять как можно больше. Если у нас cnt очков, а текущий приз стоит p очков, то мы можем получить призов. Получаем простое решение за O(5 * N).

208E - Братья по крови

В задаче нам задан набор ориентированных вниз корневых деревьев. Сначала обойдем поиском в глубину каждое дерево в отдельности и перенумеруем вершины. Пусть размер поддерева вершины v — cnt[v].Тем самым получится, что все потомки вершины v, учитывая саму вершину v, будут иметь номера в отрезке [v;v + cnt[v]–1].

После этого будем обрабатывать запросы (v, p) по очереди. Поднимемся из вершины v запроса на p вершин вверх к корню, используя двоичный подьем, похожий на поиск lca в дереве. Пусть мы пришли в вершину u. Если у вершины нет предка на расстоянии p, сразу выводим 0, иначе нужно посчитать количество потомков полученной вершины u, которые имеют ту же высоту в дереве, что и вершина v.

Для этого, для каждой высоты выпишем в отдельный массив номера всех вершин с этой высотой. Тогда для ответа на запрос, нужно узнать, какие из вершин этого массива являются потомками нашей вершины u. Для этого можно бинарным поиском в этом массиве выделить отрезок подходящих вершин (поскольку мы знаем номера потомков вершины u) и посчитать их количество. Вычитаем из этого количества единицу (саму вершину v) и получаем ответ. Вычислительная сложность решения O(Nlog(N)) — двоичный подъем и бинарный поиск.

Приветствуем, друзья)

Рады приветствовать вас на очередном раунде Codeforces #130 для участников Div. 2. Как обычно, остальные могут поучаствовать в нем вне конкурса. Некоторое время были проблемы для регистрации участников вне конкурса, но сейчас все в порядке)

Задачи для вас были подготовлены группой авторов в составе: Павел Холкин (HolkinPV), Николай Кузнецов (NALP) и Геральд Агапов (Gerald). Традиционно хотим поблагодарить Михаила Мирзаянова (MikeMirzayanov) за прекрасную систему Codeforces и Марию Белову (Delinur) за перевод условий. А также благодарим за помощь Александра Куприна (Alex_KPR) и Кунявского Павла (PavelKunyavskiy).

Распределение баллов вновь будет динамическим) Подробнее информацию об этом можно найти здесь.

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

Всем участникам мы желаем успехов, удачных взломов и высокого рейтинга!

UPD: контест завершен, несмотря ни на что, надеемся соревнование вам понравилось

UPD2: Авторы просят прощения за ситуацию с задачей Е. Так как задача оказала влияние на небольшое количество участников из див2 (22 участника), а решение первоначальной версии задачи не сильно отличается от измененной версии (в большинстве решений достаточно удалить пару строчек) в сторону упрощения решения, было принято следующее решение:

• для всех 22-х участников див2, кто имел проблемы с задачей E из-за условия и имел бы понижение рейтинга по результатам раунда, раунд будет нерейтинговым
• для всех остальных раунд рейтинговый.

UPD3: после пересчета оказалось, что таких участников 20, а не 22

UPD4: добавлен разбор задач

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

195A - Посмотрим футбол

Полное видео скачается через all = (c·a + b - 1) / b секунд. В этой задаче можно было перебрать величину ответа 1 <  = t <  = all. Чтобы удовлетворить условию задачи, достаточно проверить, что в последний момент времени t0 = all выполняется условие, написанное в тексте задачи, а именно t0·b >  = (t0 - t)·a.

195B - После тренировки

В этой задаче нужно было аккуратно реализовать описанный в условии процесс. Вначале заметим, что мяч с номером i > m попадет в одну корзину с мячом под номером i - m. Поэтому достаточно распределить первые m мячей. Это удобно сделать при помощи двух указателей lf, rg, начиная с середины. Поочередно кладем мяч сначала слева, затем справа и двигаем указатели. Единственный раз, когда нужно дважды подвинуть левый указателей, возникает в самый первый момент, если m нечетно.

195C - Попробуй поймай

Данная задача носила реализационный характер. В своем решении я поступал следующим образом. Удалим из текста все пробелы, кроме пробелов в сообщениях try-catch блоков. Затем при появлении слова try, кладем номер нового try-catch блока в стек. При появлени слова throw, запомним его тип, а также текущее состояние стека (то есть какие try-catch блоки открыты). Для этого, например, положим номера открытых блоков в set. При появлении слова catch, если тип блока совпадает с типом оператора throw, а также номер текущего блока находился в стеке при появлении оператора throw (то есть он есть в нашем set-е), то сразу выводим ответ. Иначе удаляем текущий try-catch блок из стека. Если подходящего try-catch блока так и не найдется, в конце выводим фразу "Unhandled Exception".

195D - Исследование ломаной

Разбор от автора Igor_Kudryashov

В данной задаче были заданы по сути прямые в виде y_i = k_i * x + b_i, но в тех точках, где y принимает отрицательное значение, оно заменено нулем. Необходимо было найти количество углов, не равных 180 градусам, в графике функции, равной сумме функций указанного вида.

Во-первых, несложно показать, что сумма прямых является прямой. В самом деле, если y = y₁ + y₂, то y = k₁ * x + b₁ + k₂ * x + b₂ = (k₁ + k₂) * x + (b₁ + b₂). Рассмотрим точки, в которых y_i = 0, т.е. x_i =  - b_i / k_i. Пока предположим, что k_i не равно 0. Тогда i-ая функция разбивается на две прямые, одна из которых тождественно равна 0. Оставим среди x_i различные точки и упорядочим их по возрастанию значения. Тогда, очевидно, между двумя соседними точками суммой заданных функций является прямая. Найдем уравнение этой прямой. Предположим, мы рассматриваем i-ую слева точку. Тогда если уравнение прямой между i-ой и (i + 1)-ой точками, отлично от уравнения прямой между (i - 1)-ой и i-ой точками, тогда в i-ой точке образуется угол, не равный 180 градусам.

Таким образом, нам необходимо найти уравнение прямых на отрезках между соседними точками x, т.е. найти коэффициенты k и b. Это можно легко сделать с использованием 2 массивов запросами увеличения на отрезке в оффлайне.

Когда мы обрабатываем очередную функцию, мы смотрим, если k_i равно 0, то нужно ко всем отрезкам прибавить одну и ту же величину, но т.к. данное изменение не повлияет на ответ, то можно не обрабатывать функции такого вида. Если k_i не равно 0, то найдем индекс j точки x_i в упорядоченном списке x. Теперь если k_i больше 0, то нужно сделать увеличение на суффиксе, начиная с позиции j, иначе нужно сделать увеличение на префиксе до позиции j (при этом увеличение на префиксе коэффициента k будет производиться на отрицательную величину).

195E - Построение леса

Разбор от автора Fefer_Ivan

В этой задаче самой долгой операцией является поиск корня вершины и длина пути до него. Эту операцию можно выполнять быстро используя эвристику сжатия путей. Такой же метод применяется в структуре данных Disjoint Set Union.

Для каждой вершины v мы будем хранить два числа: c[v] и sum[v]. c[v] = v, если v — корень, иначе c[v] — следующая вершина на пути от v к корню. sum[v] = сумме длин ребер на пути от v до c[v].

Таким образом для того, чтобы добавить ребро из u в v веса w, достаточно c[u] = v, а sum[u] = w. Теперь мы можем за O(n) находить по вершине нужные нам в задаче root(v) и depth(v) просто переходя каждый раз из v в c[v] и суммируя все sum[v] по пути.

Заметим, что мы только добавляем ребра, но не удаляем. Это значит, что если мы для вершины v нашли root(v) и depth(v), то можно присвоить c[v] = root(v), sum[v] = depth(v). Таким образом в следующий раз мы найдем предка вершины v за О(1). В общем реализация этого подхода выглядит следующим образом:

int root(int v){  
   if(c[v] == v){  
       return v;  
   }else{  
       int u = root(c[v]);  
       sum[v] = (sum[c[v]] + sum[v]) % M;  
       c[v] = u;  
       return u;  
   }  
}  

Доказывается, что такая реализация работает в сумме за время, пропроциональное обратной фунции Аккермана http://en.wikipedia.org/wiki/Ackermann_function#Inverse) на запрос при применении ранговой эвристики. Поскольку в этом случае нельзя её применить, то такой запрос обрабатывается за log(n). Итого получаем решение за время O(n * log * (n)).

Здравствуйте, друзья)

Рады приветствовать вас на очередном раунде Codeforces #123 для участников Div. 2. Традиционно, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас были подготовлены группой авторов в составе: Иван Фефер (Fefer_Ivan), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV), а также Геральд Агапов (Gerald). Также говорим спасибо Кунявскому Павлу (PavelKunyavskiy) и Александру Куприну (Alex_KPR) за помощь в подготовке раунда. Традиционно хотим поблагодарить Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и Марию Белову (Delinur) за перевод условий.

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

Всем участникам желаем успехов и высокого рейтинга!

UPD: контест завершен, разбор задач появился здесь

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

1. bmerry
2. adrian.jaskolka
3. cheshire_cat
4. alexej
5. psw

Всем здравствуйте)

Рады приветствовать вас на очередном раунде Codeforces #117 для участников Div. 2. Традиционно, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас были подготовлены группой авторов в составе: Павел Холкин (HolkinPV), Иван Фефер (Fefer_Ivan), Николай Кузнецов (NALP) и Геральд Агапов (Gerald). Мы благодарим Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и Марию Белову (Delinur) за перевод условий.

Распределение баллов вновь будет динамическим) Подробнее об этом можно найти здесь.

Обращаем внимание, что все задачи сегодня будут даны в произвольном порядке.

Некоторые участники Див. 1 зарегистрировались на соревнование раньше, чем была произведена настройка регистрации. До начала раунда это будет исправлено, и они будут участвовать вне конкурса.

Надеемся раунд пройдет успешно и всем понравится. Желаем удачи и высокого рейтинга!

UPD: условие задачи 182E - Деревянный забор было сформулировано неверно, что привело к несоответствию решений, правильный вариант условия появится совсем скоро, приносим участникам свои извинения.

UPD2: контест объявлен нерейтинговым.

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

Здравствуйте дорогие друзья)

Рады приветствовать вас на очередном раунде Codeforces #113 для участников Div. 2. Традиционно, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас были подготовлены уже знакомой группой авторов: Холкин Павел (HolkinPV), Николай Кузнецов (NALP), Артем Рахов (RAD). Мы благодарим Геральда Агапова (Gerald) за помощь в подготовке раунда, Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и Марию Белову (Delinur) за перевод условий.

В сегодняшнем раунде будет одно нововведение. Распределение баллов по задачам будет динамическим. Более подробно об этом можно узнать здесь)

Надеемся раунд пройдет успешно для всех участников. Желаем вам удачи и высокого рейтинга!

UPD: Соревнование закончено. Надеемся вам понравилось) разбор задач уже здесь

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

1. Avalanche

2. seiya

3. Konon

4. yongheng5871

5. I_dont_have_girlfriend

6. ibra

7. Doriam30

8. unknown79

9. UESTC_Hetalia

10. lisang

165A - Суперцентральная точка

В этой задаче нужно было реализовать то, что написано в условии. Для каждой точки отдельно проверим, является ли она суперцентральной. Для этого переберем все остальные точки и проверим, что у неё нашелся бы один сосед с каждой из сторон. Решение можно реализовать за время O(N²).

165B - Ночная работа

Эта задача решается бинарным поиском по ответу. Очевидно, что если число v являться ответом на задачу, то и любое число w > v будет являться ответом, поскольку число написанных строк кода могло только увеличиться. Поэтому, чтобы найти минимальный ответ, воспользуемся бинарным поиском. Чтобы проверить, подходит ли конкретное число V, воспользуемся формулой, указанной в условии. В этой формуле будет O(logN) ненулевых членов. В итоге получаем решение за O(log²(N)).

165C - Еще одна строковая задача

Для начала скажем, что вместо бинарной строки у нас есть массив чисел 0 и 1. Тогда нужно посчитать количество отрезков [lf;rg] таких, что сумма чисел на них равна k. Посчитаем для этого массива частичные суммы, а именно массив sum, где sum[i] – сумма чисел в отрезке [0;i]. Ответ на задачу будем считать следующим образом. Будем двигаться по массиву слева направо. Пусть мы находимся в позиции pos. Прибавим к ответу количество отрезков, сумма на которых равна k и которые заканчиваются в позиции pos. Для этого для каждой частичной суммы будем поддерживать массив cnt, где cnt[i] – количество раз, которое встретилась частичная сумма, равная i. Тогда в данный момент к ответу нужно прибавить величину cnt[sum[pos]–k]. Решение можно реализовать за время O(N), где N – длина исходной бинарной строки.

165D - Граф-борода

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

Для каждого пути, которое отходит от корня выпишем вершины и ребра, которые в него попадают. Величину расстояния можно считать отдельно. Для каждой вершины v предподсчитаем расстояние d[v] от неё до корня. Тогда если вершины x и y находятся на разных путях, то расстояние между ними d[x] + d[y], а иначе это разница их расстояний до корня abs(d[x]–d[y]). Также для каждого пути заведем дерево отрезков, которое умеет считать сумму на отрезке и изменять значение в точке, построенное на ребрах каждого пути.

Ребра черного цвета обозначим числом 0, а белого 1. Перекраска ребра осуществляется одним апдейтом в точке. А чтобы проверить, есть ли между вершинами путь только по черным ребрам, нужно аккуратно посчитать сумму на пути между ними. Если сумма больше 0, это значит, что между вершинами есть хотя бы одно белое ребро, то есть ответ на запрос расстояния  - 1, иначе посчитаем расстояние, описанным выше образом. Решение можно реализовать за время O(NlogN).

165E - Совместимые числа

Рассмотрим произвольное число x для которого нужно найти ответ. Инвертируем биты в числе x, назовем это число y. Теперь посмотрим на битовое представление какого-либо числа a[i] из массива. Оно будет ответом для числа x, если для каждой позиции нулевого бита числа y в этой же позиции в a[i] также будет нулевой бит. Тогда остальные нулевые биты числа a[i] можно заменить на единичные (поскольку они не повлияют на результат операции AND).

Тогда будем считать такую динамику z[mask] = {0, 1}, которая означает, можем ли мы поменять некоторые нулевые биты какого-либо числа из массива a на единичные, чтобы получить маску mask. Начальными значениями динамики будут все исходные числа массива (z[a[i]] = 1). Чтобы осуществить переход, переберем каждый бит маски mask и попробуем его заменить на единичный, если он нулевой. Ограничения в задаче таковы, что длины двоичных представлений чисел не превосходят 22.

Посчитав такую динамику, чтобы ответить на запрос YES или NO для числа x, нужно посмотреть значение динамики от числа z[(y)&((1«22)–1)], то есть инвертировать биты в числе x и сделать это число длины 22. Тогда если значение в этой ячейке равно 1, то ответ YES иначе NO. А чтобы получить само число, которое является ответом, можно просто в ячейке z[mask] хранить то число, которое породило данный ответ. Итого решение, которое работает за O(2^K * K), где K – длина бинарного представления чисел (K <  = 22).

Доброго времени суток!

Рады приветствовать вас на очередном раунде Codeforces для участников Div. 2, в котором традиционно могут участвовать все желающие.

Задачи для вас подготовили Холкин Павел (HolkinPV), Рахов Артем (RAD) и Николай Кузнецов (NALP). Выражаем свою благодарность Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему, Марии Беловой (Delinur) за перевод условий, а также Агапову Геральду (Gerald) и Куприну Александру (Alex_KPR) за помощь.

Откроем небольшой секрет по поводу сегодняшних задач. Для их решения вам скорее всего понадобятся сортировки)

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

Всем участникам желаем успехов и высокого рейтинга!

UPD: Соревнование закончено. Разбор задач можно найти здесь.

UPD2: Всем большое спасибо за участие. Надеемся задачи вам понравились. Поздравляем победителей:

1. Touma_Kazusa
2. ZJUT_AA
3. wwhd
4. jikwao425
5. wtiger9999
6. Jolin
7. anmtcel
8. marspeople
9. ztxz16
10. CrazyRabbit

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

Задача "Магический массив" (A в div1, B в div2).

Приветствую всех на Codeforces Beta Round #72.