56.md (8662B)
1 Source: https://codeforces.com/blog/entry/1147 2 3 **Задача А. Бар** 4 5 Ответом на задачу является количество посетителей, которые удовлетворяют одному из предложенных ограничений: 6 7 > *1) Указан возраст посетителя и он меньше 18 лет* 8 > 9 > *2) Указан напиток посетителя и он является алкогольным* 10 11 Далее остается аккуратная реализация. 12 13 **Задача B. Испорченная перестановка** 14 15 Задача имеет множество решений. В разборе будет расказанно решение с асимптотикой O(N), где N - количество элементов последовательности. 16 17 Найдем такое наименьшее i, такое что Ai не равно i (элементы нумеруются с единицы). Если такого i не существует, то все числа стоят на своих местах и, соответственно, ответом являются два нуля. Иначе, предполагаем, что ответом являются числа i и Ai (мы можем быть точно уверены, что i < Ai). Переворачиваем подпоследовательность элементов с i-ого по Ai-ый и проверяем всю полученную последовательность на то, везде ли Ai равно i. Если да, то ответом является пара (i, Ai), иначе ответ - два нуля. 18 19 **Задача C. Почта в корпорации** 20 21 Для решения задачи вполне подходит решение за O(N2L), где N - количество людей в иерархии, а L - средняя длина имени сотрудника. То есть сравнение строк можно выполнять без использования хэш-функции. 22 23 Первая часть решения - аккуратная реализация примитивного парсинга строки. Наиболее простой способ - рекурсивная функция, которая читает сначала имя сотрудника, а потом и всех его подчиненных до тех пор, пока не достигнет точки. Далее потребуется хранить в памяти дерево из N вершин. Хранение дерева можно организовать как с помощью динамической памяти, так и простой матрицей смежности. Далее можно просто для каждой вершины запустить обход в глубину из нее и посмотреть скольким вершинам в этом поддереве сопоставлено такое же имя. Стоит обратить внимание на то, что сама вершина, из которой изначально запускается обход в глубину, не должна быть посчитана в ответ. 24 25 Такое решение можно улучшить до сложности O(NlogN), используя хэширование и более сложные структуры данных (например map). При данных ограничениях это было бы пустой тратой времени. Даже грубой оценки N < 500 достаточно, чтобы решение уложилось в time limit. 26 27 **Задача D. Получаем строку** 28 29 Наиболее простым решением этой задачи является решение с использованием динамического программирования. Обозначим первую строку за A, а вторую за B. Длина первой строки равна N, а второй - M. Тогда решение имеет асимптотику O(NM). 30 31 Обозначим за S(i, j) - подстроку строки S с i-ого по j-ый символ. 32 33 Введем функцию F(x, y) - сколько минимум действий надо выполнить, чтобы из подстроки A(x, N - 1) получить подстроку B(y, M - 1) (индексы символов нумеруются с нуля). Тогда значание F(x, y) это минимум из: 34 35 > *F(x + 1, y + 1), при x < N, y < M и A[x] = B[x]* 36 > 37 > *F(x + 1, y + 1) + 1, при x < N, y < M* 38 > 39 > *F(x + 1, y), при x < N* 40 > 41 > *F(x, y + 1), при y < M* 42 43 Очевидно, что F(N, M) равно нулю. 44 45 Если при обработке очередного перехода не только обновлять значение функции, но и запоминать тип перехода, то по окончании подсчета функции F(0, 0) можно будет восстановить набор необходимых операций для превращения строки A в строку B. Ну а само значение F(0, 0) и будет искомым ответом. 46 47 **Задача E. Принцип домино** 48 49 Задача вполне может иметь множество решений, но в данном разборе будет рассказано одно из наиболее тривиальных. 50 51 Для начала отсортируем все доминошки по координате x слева направо, запомнив изначальную нумерацию. Эта нумерация потребуется только для вывода ответа в правильном порядке. Далее нужно сформулировать несколько тривиальных утверждений: 52 53 > *1) Если толкнуть какую-либо доминошку вправо, то среди упавших доминошек все (кроме самой доминошки) будут находиться справа от той, что толкнули.* 54 > 55 > *2) Если какая-либо доминошка упала, то упали и все доминошки, которые находятся левее этой, но не левее той, что изначально толкнули.* 56 > 57 > *3) Для каждой доминошки можно определить номер наиболее правой доминошки такой, что она упадет, если толкнуть данную.* 58 59 Обозначим за F(i) номер наиболее правой доминошки, которая упадет, если толкнуть i-ую доминошку. Сама по себе i-ая доминошка может не упасть на F(i)-ую, но из-за "принципа домино" F(i)-ая все же упадет. Если доминошка при падении вообще не задевает никакую другую доминошку, то F(i) = i. Очевидно, что такое равенство выполняется для самой правой доминошки. Для остальных доминошек можно найти значение F(i) с помощью уже найденных F(j), где j > i. 60 61 Для каждой доминошки с номером i можно найти такую доминошку с номером j, что при падении i-ая повалит j-ую (непосредственно), и такое j максимально. То есть найти самую правую из доминошек, которую повалит непосредственно i-ая. Далее F(i) = max(F(k)), где k принимает значения на интервале [i + 1, j]. 62 63 Реализация решения с асимптотикой O(N2) точно не влезет в ограничения по времени. Поэтому необходимо написать решение как минимум за O(NlogN), для чего достаточно воспользоваться структурой данных типа дерева интервалов. Короче говоря, решить задачу Range Maximum Query.