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

A — Вася и автобусы

Во-первых, если n = 0, то ни одного ребенка по условию нельзя провезти. Значит, если при этом m = 0, от ответ (0, 0), иначе ответ Impossible.
Теперь n > 0. Если m = 0, то ответ, очевидно, (n, n). Иначе, чем больше родителей везет с собой по ребенку, тем меньше плата за проезд. Поэтому максимальная плата будет тогда, когда всех детей везет один родитель — получаем ответ n + m - 1. Если n <  = m, то все n родителей везут детей, и ровно n детей не платят за проезд. Если же n > m, то все m детей распределяются по родителям и не платят за проезд. В обоих случаях получаем минимальный ответ max(n, m).

B — Окружение

Найдем минимальное расстояние между окружностями L. Тогда ответ к задаче равен L / 2.
- Пусть окружности лежат вне друг друга. Покажем, что L = d - R - r. Во-первых, ясно, что он достигается. Проведем отрезок соединяющий центры. Его часть, лежащая между точками пересечения с окружностями как раз имеет такую длину.

Докажем, что меньшее расстояние недостижимо, построим отрезок между двумя окружностями. Тогда R + r + L >  = d, откуда L >  = d - R - r, чтд.

• Для окружностей, лежащих внутри друг друга аналогичными рассуждениями получаем L = R - d - r, где R — радиус наружной окружности, r — внутренней.
• Для пересекающихся окружностей ответ 0.

C — STL

Пусть нам дан массив строк (s₁, s₂, ...s_n), где s_i  = pair либо int.
Рассмотрим числа bal_i = разность количества pair и int на отрезке массива от 1 до i. Тогда утверждается, что восстановить тип по данному массиву строк можно, причем однозначно  <  =  >  bal_i >  = 0 при 1 <  = i < n и bal_n =  - 1. Здесь возникает очевидная аналогия с правильными скобочными последовательностями.
Докажем это утверждение по индукции по количеству int в данном массиве. База для n = 1 очевидна. Пусть у нас есть тип pair < type1, type2 > . Тогда bal_n = 1 +  bal_ntype1+bal_ntype2  =  - 1. Также можем получить, что bal_i >  = 0 для 1 <  = i < n.
Пусть теперь у нас есть массив строк s, и в нем выполняется данное утверждение. Тогда первый элемент в нем — pair. Возьмем наименьшее i, что bal_i = 0 — оно существует по соображениям дискретной непрерывности (и не равно n, ибо bal_n =  - 1) — в этой позиции должен заканчиваться type1. Тогда на отрезке [2, i] (для него несложно проверить предположение индукции) можно расставить знаки препинания, чтобы получился тип. Аналогичное верно и для отрезка [i + 1, n]. Значит, и из всего отрезка [1, n] можно составить тип, причем тоже единственным образом.
Теперь, если мы получили, что из данного массива строк можно составить тип, заведем функцию gettype(i), которая будет строить тип, начинающийся в s_i, и возвращать индекс, следующий после того, в котором она завершила построение. Как она будет работать? Пусть сейчас запущена gettype(i). Если s_i = pair, выведем int и вернем i + 1. Иначе выведем "pair < ", запустим gettype(i + 1) — пусть он вернул нам j. Выведем ", " и запустим gettype(j), он вернул нам k, выведем " > " и вернем k. Итого, запустив gettype(0), мы построим и выведем восстановленный тип.
Можно обойтись без предварительной проверки, можно ли составить тип из данного массива. Для этого можно запустить функцию gettype и, если в ходе построения типа получаются противоречия, выводить "Error occurred".
Асимптотическая сложность решения — O(количества данных строк).

D — Несекретный шифр

Решение riadwaw: Воспользуемся методом двух указателей. Будем поддерживать для каждого элемента, сколько раз он встречается на текущем отрезке [l, r]. При фиксированном l будем увеличивать r, если элемент a[r] встречается k раз, то этот отрезок и все отрезки вида [l, t], t > r нужно добавить в ответ и увеличить l. Чтобы поддерживать кол-во элементов нужно либо сжать координаты, либо воспользоваться структурой map. Также нужно не забыть, что ответ может достигать n * (n + 1) / 2, т.е не влазить в int.
Решение Kostroma: для начала сожмем координаты, аналогично первому решению. Выпишем для каждого числа список позиций, в которых оно встречается в нашем массиве. Теперь создадим массив b, в b_i будем хранить номер позиции, в которой стоит число a_i, при этом на отрезке [i, b_i] число a_i встречается ровно k раз (если такой позиции нет, то b_i = n + 1). Это несложно сделать одним проходом по нашим спискам. Найдем, сколько отрезков с началом в i удовлетворяют условию задачи — для этого из n нужно вычесть такое минимальное j, что на отрезке [i, j] есть k одинаковых чисел (если такого отрезка нет, то j будем считать равным n + 1). Но такое минимальное j есть . Такие минимумы для всех i можно найти, пройдя массив a один раз с конца. Осталось только просуммировать ответы для всех i от 1 до n.

E — Контратака

У этой задачи много различных решений. Для начала, конечно же, сопоставим городам вершины графа, а дорогам — ребра. Теперь нам нужно найти все компоненты связности в дополнении данного графа.
Решение Gerald: будем хранить set a вершин, которые еще не были посещены, и запустим серию обходов в глубину. Предварительно отсортируем списки смежности каждой вершины — теперь мы можем за O(logn) проверять, есть ли в данном графе произвольное ребро. Пусть мы сейчас находимся в вершине v. Пройдемся по всем элементам a, пусть мы сейчас рассматриваем вершину . Если ребра (v, u) нет в данном графе, то в его дополнении оно есть  =  >  выкинем из a вершину u и добавим ее в очередь. Иначе ничего с вершиной u не делаем. Сколько же раз с вершиной u будет повторена такая операция? Заметим, что вершина u остается в set-е только тогда, когда в данном графе есть ребро (u, v), то есть не больше раз, чем степень вершины u. Значит, асимпотика такого решения равна O(M * logn). Логарифм появляется из бинарного поиска. Это решение без каких бы то ни было оптимизаций тратит чуть больше 2 секунд. Если использовать хеш-таблицы, чтобы узнавать, есть ли в графе определенное ребро, получим асимптотику O(m).
Решение Kostroma: Рассмотрим компоненты дополнения нашего графа. Рассмотрим такой набор компонент дополнения, что их суммарный размер не больше n / 2 и наиболее близок к n / 2 (если такого набора не существует, то в дополнении одна компонента) — пусть в них в сумме c вершин — назовем это множество A. Тогда все ребра между этими с вершинами и остальными n - c вершинами должны быть в данном графе, то есть c·(n - c) <  = m. Отсюда получаем, что . Если n² <  = 4·m, то n <  = 2·10³, тогда c <  = 10³. Иначе при фиксированном m для роста оценки на c нужно уменьшать n — вплоть до того, пока не выполнится n² = 4·m. Тогда . Значит, мы получили, что c <  = 10³.
Рассмотрим теперь любую другую компоненту, пусть в ней b вершин. Тогда c + b >  = n - c, так как c + b > n / 2 в силу выбора множества A, а значит, если c + b < n - c, то можно взять множество компонент, в которое входят все компоненты, кроме A и еще одной компоненты из b вершин — в нем n - c - b вершин, и c < n - c - b, n - c - b <  = n / 2. Значит, если в дополнении больше одной компоненты, то есть компонента размеров не меньше чем n - 2·c (назовем ее большой), значит, во всех остальных компонентах в сумме не больше чем 2·c вершин (причем в A ровно c вершин, значит во всех компонентах, кроме большой, не больше чем c вершин). Тогда не лежать в большой компоненте могут только вершины, степень которых в исходном графе как минимум n - c. Значит, все вершины со степенью  < n - c лежат в одной компоненте, а значит, все вершины со степенью  < n - 1000 тем более лежат в одной компоненте. Множество этих вершин назовем B. Построим новый граф из вершин, не принадлежащих множеству B и еще одной вершины: для каждой пары вершин не из B ребро будет проведено тогда и только тогда, когда в исходном графе его не было. Сопоставим множеству B вершину D, тогда ребра между D и произвольной вершиной v не будет тогда и только тогда, когда в исходном графе v соединена со всеми вершинами из B.
Сколько же в новом графе будет вершин? Количество вершин, степень которых в данном графе как минимум n - 1000, и еще вершина D, то есть не больше чем  + 1 =  . Значит, ребер в графе будет O(m). Теперь запустим серию обходов в глубину или ширину на таком графе и найдем в нем компоненты связности. Теперь нетрудно восстановить компоненты связности дополнения: для этого нужно лишь вспомнить, какие вершины попали в множество B. Получаем решение за O(m), работающее чуть меньше секунды.
Решение riadwaw:
- Посчитаем степень каждой вершины в исходном графе, выберем вершину с минимальной степенью — назовем её V. O(m)
- Заметим, что ее степень не больше средней степени вершин, т.е .
- Заметим, что все вершины, кроме соединенных с V в исходном графе, будут лежать в дополнении в той же компоненте связности, что и V — назовем это множество вершин A.
- Таким образом, можно явно построить дополнение графа, содержащего V и все вершины, соединенные с ней. Всего ребер там , так как m < n·n. Переберем все эти ребра, объединим с помощью СНМ соединенные вершины. Кроме того, объединим с компонентой, содержащей V, вершины, которые в исходном графе соединены не со всеми вершинами из A.
В асимптотике могут вылезать лишние логарифмы из СНМ или сжатия координат. Общая асимптотика от O(m) до O(mlogn), решение работает около секунды.