Задача А. Бар
Ответом на задачу является количество посетителей, которые удовлетворяют одному из предложенных ограничений:
1) Указан возраст посетителя и он меньше 18 лет2) Указан напиток посетителя и он является алкогольным
Далее остается аккуратная реализация.
Задача B. Испорченная перестановка
Задача имеет множество решений. В разборе будет расказанно решение с асимптотикой O(N), где N - количество элементов последовательности.
Найдем такое наименьшее i, такое что Ai не равно i (элементы нумеруются с единицы). Если такого i не существует, то все числа стоят на своих местах и, соответственно, ответом являются два нуля. Иначе, предполагаем, что ответом являются числа i и Ai (мы можем быть точно уверены, что i < Ai). Переворачиваем подпоследовательность элементов с i-ого по Ai-ый и проверяем всю полученную последовательность на то, везде ли Ai равно i. Если да, то ответом является пара (i, Ai), иначе ответ - два нуля.
Задача C. Почта в корпорации
Для решения задачи вполне подходит решение за O(N2L), где N - количество людей в иерархии, а L - средняя длина имени сотрудника. То есть сравнение строк можно выполнять без использования хэш-функции.
Первая часть решения - аккуратная реализация примитивного парсинга строки. Наиболее простой способ - рекурсивная функция, которая читает сначала имя сотрудника, а потом и всех его подчиненных до тех пор, пока не достигнет точки. Далее потребуется хранить в памяти дерево из N вершин. Хранение дерева можно организовать как с помощью динамической памяти, так и простой матрицей смежности. Далее можно просто для каждой вершины запустить обход в глубину из нее и посмотреть скольким вершинам в этом поддереве сопоставлено такое же имя. Стоит обратить внимание на то, что сама вершина, из которой изначально запускается обход в глубину, не должна быть посчитана в ответ.
Такое решение можно улучшить до сложности O(NlogN), используя хэширование и более сложные структуры данных (например map). При данных ограничениях это было бы пустой тратой времени. Даже грубой оценки N < 500 достаточно, чтобы решение уложилось в time limit.
Задача D. Получаем строку
Наиболее простым решением этой задачи является решение с использованием динамического программирования. Обозначим первую строку за A, а вторую за B. Длина первой строки равна N, а второй - M. Тогда решение имеет асимптотику O(NM).
Обозначим за S(i, j) - подстроку строки S с i-ого по j-ый символ.
Введем функцию F(x, y) - сколько минимум действий надо выполнить, чтобы из подстроки A(x, N - 1) получить подстроку B(y, M - 1) (индексы символов нумеруются с нуля). Тогда значание F(x, y) это минимум из:
F(x + 1, y + 1), при x < N, y < M и A[x] = B[x]F(x + 1, y + 1) + 1, при x < N, y < MF(x + 1, y), при x < NF(x, y + 1), при y < M
Очевидно, что F(N, M) равно нулю.
Если при обработке очередного перехода не только обновлять значение функции, но и запоминать тип перехода, то по окончании подсчета функции F(0, 0) можно будет восстановить набор необходимых операций для превращения строки A в строку B. Ну а само значение F(0, 0) и будет искомым ответом.
Задача E. Принцип домино
Задача вполне может иметь множество решений, но в данном разборе будет рассказано одно из наиболее тривиальных.
Для начала отсортируем все доминошки по координате x слева направо, запомнив изначальную нумерацию. Эта нумерация потребуется только для вывода ответа в правильном порядке. Далее нужно сформулировать несколько тривиальных утверждений:
1) Если толкнуть какую-либо доминошку вправо, то среди упавших доминошек все (кроме самой доминошки) будут находиться справа от той, что толкнули.2) Если какая-либо доминошка упала, то упали и все доминошки, которые находятся левее этой, но не левее той, что изначально толкнули.3) Для каждой доминошки можно определить номер наиболее правой доминошки такой, что она упадет, если толкнуть данную.
Обозначим за F(i) номер наиболее правой доминошки, которая упадет, если толкнуть i-ую доминошку. Сама по себе i-ая доминошка может не упасть на F(i)-ую, но из-за "принципа домино" F(i)-ая все же упадет. Если доминошка при падении вообще не задевает никакую другую доминошку, то F(i) = i. Очевидно, что такое равенство выполняется для самой правой доминошки. Для остальных доминошек можно найти значение F(i) с помощью уже найденных F(j), где j > i.
Для каждой доминошки с номером i можно найти такую доминошку с номером j, что при падении i-ая повалит j-ую (непосредственно), и такое j максимально. То есть найти самую правую из доминошек, которую повалит непосредственно i-ая. Далее F(i) = max(F(k)), где k принимает значения на интервале [i + 1, j].
Реализация решения с асимптотикой O(N2) точно не влезет в ограничения по времени. Поэтому необходимо написать решение как минимум за O(NlogN), для чего достаточно воспользоваться структурой данных типа дерева интервалов. Короче говоря, решить задачу Range Maximum Query.
По задаче D.
Хочется отметить удобный способ "универсального восстановления пути", применимый к большинству рекурсивных динамик, и не использующий никакой доп. памяти (кроме самих значений динамики).
А именно, пусть у нас динамика реализована в виде некой рекурсивной функции - назовём её get_d (param1, param2, ...). Тогда чтобы восстановить ответ по этой динамике, но не запоминать нигде никаких "предков", мы можем снова вызвать эту же функцию, но указав ей каким-нибудь флагом, чтобы она выводила найденный ей самый лучший переход.
Т.к. словами это объяснить довольно сложно, давайте схематический код:
int get_d (int n, int k) {
... обычная рекурсивная динамика с меморизацией ...
}
void restore_ans (int n, int k) {
int ans = get_d (n, k);
if (ans == ответ_если_мы_сделаем_первый_переход) {
cout << "сделан первый переход\n";
restore_ans (новое_n, новое_k);
return;
}
if (ans == ответ_если_мы_сделаем_второй_переход) {
cout << "сделан второй переход\n";
restore_ans (новое_n, новое_k);
return;
}
... и так все переходы ...
throw; // уж хоть один переход да должен был дать лучшее значение
}
При реализации на соревновании это выглядит так: сначала пишем просто динамику функцией get_d, даже не задумываясь о восстановлении пути, потом запускаем её и проверяем, что она работает правильно, а потом копируем эту функцию get_d в restore_ans, только немножко переоформляя каждый переход в соответствии с тем, как описано выше. Эта универсальная схема поможет нам - сэкономить наши силы, а программе - компьютерную память :)
А ответ вывожу в конце.
На счет потери времени при решении задачи C.
Восстанавливать дерево и потом запускать по нему DFS не нужно, так как строка во входном файле как раз и является DFS-обходом. Каждое имя сотрудника соответсвует спуску вглубь дерева, а точки — подъему. Итого задача решается одним стеком (сумма по количествам совпадений вершины стека с остальными элементами).
Кстати, решение за O(LNlogN) реализуется немного проще, чем квадратичное.
в С можно было делать проще (без графов): завести стек из "открытых" сотрудников — т.е. чей подчиненный в данный момент обрабатывается. Вводим новое имя до точки или двоеточия. Пробегаем весь стек "открытых" сотрудников, попутно увеличивая счетчик результата, если такое же имя уже встречалось. Пушим в стек текущего сотрудника. Далее, пока последний символ — точка, выталкиваем из стека сотрудников. Ссылка на решение на С++
How I use the segment tree to solve problem E ???
You just need to implement a segment tree which supports single assignment and range minimum query. Since there is no range modification, no lazy propagation is needed, and the segment tree implementation is very simple.
For the other part, you can just refer to the tutorial.
For those of us who don't understand russian, if you are looking for a solution of D, then refer here:
E Problem can actually be written in a much easier manner(at least I think so :D). You can use dynamic programming. let us create an array dp initialized with 1-s, which will contain how many dominoes can i-th domino flip. we also use another array where on i-th index is written x, which is index of a domino which will not fall if you trip i-th domino. lets call domino with index x barrier of i-th domino. first you sort the pairs by coordinates. Then you go from end to beginning and implement logic:
1) if i-th domino can cause i+1 to fall, you do dp[i] += dp[i+1]. after this you check if i-th domino can reach i+1-th domino's barrier, if yes dp[i] += dp[x] and then you check x-th domino's barrier and so on. when you find i-th domino's barrier you save it in the second array. we can see that now barrier can only be i-th domino or its barrier(or everything else on its right), so after next iterations we wont have to check dominoes in between. 2) if i-th domino can't flip domino on its right we just save i+1 as i-th domino's barrier.
sorting will take O(nlogn) and the solution with dp O(n).
could you show insert a code link please?
Where can I find the English version of this editorial?