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