600A - Extract Numbers

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

600B - Queries about less or equal elements

Давайте отсортируем числа первого массива. Теперь будем идти по второму массиву и для текущего числа b_j найдем бинарным поиском индекс первого большего числа в первом массива. Этот индекс и будет являться ответом.

Другим подходом в этой задаче было следующее: отсортируем оба массива сохранив при этом индексы чисел (например можно сортировать пары <значение, позиция>). Теперь будем идти по второму массиву и хранить переменную p — указатель на первый элемент a_p такой, что он больше текущего b_j. Поскольку оба массива отсортированы указатель можно не сбрасывать на каждой итерации, а просто двигать его дальше вправо.

Асимптотическая сложность решения: O(nlogn).

600C - Make Palindrome

Давайте посчитаем для каждого символа c сколько раз он встречается в s. Обозначим эту величину cnt_c. Рассмотрим нечетные cnt_c. В палиндроме нечетных cnt_c может быть не больше одного. Пусть a₁, a₂...a_k — это символы с нечетным cnt_c в алфавитном порядке. Заменим любой символ a_k символом a₁, символ a_k - 1 символом a₂ и так далее пока не дойдем середины. Теперь у нас имеется имеется не более одного нечетного символа. Если нечетный символ есть поставим его в середину ответа. А в первую половину возьмем от всех букв cnt_c / 2 в алфавитном порядке. Например, если s = aabcd мы сначала заменим d на b, после этого поставим символ c в середину и после перестановки остальных символов получим строку abcba.

Асимптотическая сложность решения: O(n).

600D - Area of Two Circles' Intersection

Давайте сразу отбросим случай когда круги не пересекаются, в это случае ответ равен 0. Это можно проверить в целых числах, сравнив квадрат расстояния между центра с квадратом суммы радиусов. Также отбросим случай, когда один круг полностью лежит внутри другого, в этом случае ответ есть площадь маленького круга. Это тоже можно проверить в целых числах, сравнив квадрат расстояния между центра с квадратом разности радиусов. Отлично теперь можно рассмотреть общий случай. Ответ будет складываться из некоторого сегмента первого круга и некоторого сегмента второго круга. Для того, чтобы определить угол первого сегмента рассмотрим треугольник, образованный центрами кругов и одной из точек пересечения. В этом треугольнике мы знаем все три стороны, значит по теореме косинусов может определить угол сегмента. Значит мы можем определить площадь сектора. Теперь остается вычесть из этого площадь треугольника образованного одним из центров и точками пересечения кругов. А это можно сделать, посчитав площадь как половина модуля псевдовекторного произведения. Таким образом получаются следующие формулы: ,

где d — расстояние между центрами. И соответственно тоже самое нужно сделать для первого круга, поменяв индексы 1 ≤ ftrightarrow2.

Асимптотическая сложность решения: O(1).

600E - Lomsat gelral

Название этой задачи является анаграммой к Small to large. И это не спроста :-) Авторское решение по этой задаче использует классическую технику пересчета множеств на дереве. Простейшим решением этой задачи является следующее: давайте для каждой вершины поддерживать один map<int, int> — для каждого цвета, сколько раз он встречается, один set<pair<int, int>> — пары количество повторений и цвет, и число sum являющееся суммой самых частых символов. Для того, чтобы посчитать эти величины для вершины v нужно сначала посчитать их для всех сыновей, а потом просто сливать эти значения. Такой подход правильный, но медленный (сложность получится O(n²logn)). Но давайте немного улучшим это решение, каждый раз когда нам надо склеить 2 map-а a и b, будем клеить меньший из них (просто итерируясь по нему) к большему (это и есть small to large). Давайте теперь рассмотрим цвет какой-нибудь вершины: каждый раз, когда он будет перекидываться из одного map-а в другой размер другого будет как минимум вдвое больше. Таким образом, это цвет поперебрасывается не более logn раз. Каждой перебрасывание делается за O(logn). Просуммировав это по всем вершинам получаем сложность O(nlog²n).

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

600F - Edge coloring of bipartite graph

Введем обозначение d — наибольшая из степеней вершин в графе. Утверждение: ответ равен d. Докажем это утверждение, построив конструктивный алгоритм (он и будет решением задачи). Давайте красить ребра по очереди в любом порядке. Пусть текущее ребро (x, y). Если сейчас существует цвет c, который свободен и в вершине x и в вершине y, мы просто красим ребро в цвет c. Если такого цвета нет обязательно существует пара цветов c₁, c₂ такая, что c₁ есть в x но нет в y, а цвет c₂ есть в y но нет в x. Давайте освободим вершину y от цвета c₂. Рассмотрим другой конец ребра исходящего из вершины y цвета c₂. Пусть это вершина z. Если у вершины z цвет c₁ свободен мы можем покрасить ребра x, y в цвет c₂, а ребро y, z перекрасить в цвет c₁. Таким образом мы проведем чередование. Если же у вершины z цвет c₁ занят посмотрим на следующую вершину по цвету — w. Если это вершина не содержит ребра цвета c₂ мы снова можем провести чередование. И так далее. Поскольку граф двудольный мы обязательно сможем найти чередующуюся цепочку. Поиск цепочки можно сделать обходом в глубину. Длина цепочки порядка O(n). Поэтому окончательно имеем:

Сложность решения: O(nm).