586A - Alena's Schedule

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

586B - Laurenty and Shop

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

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

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

585A - Gennady the Dentist

Давайте посчитаем для каждого символа 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).

585B - Phillip and Trains

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

585C - Alice, Bob, Oranges and Apples

585D - Lizard Era: Beginning

585E - Present for Vitalik the Philatelist

585F - Digits of Number Pi

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