205A - Маленький Слоник и Роздол

Это была самая простая задача из набора. Нужно просто отсортировать все расстояния (при этом поддерживая индексы) и, если первые два расстояния равны, вывести "Still Rozdil", иначе вывести индекс первого элемента.

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

205B - Маленький Слоник и сортировка

В этой задачи нужно заметить тот факт (который несложно доказать, но он понятен даже интуитивно), что, так как массив нужно сделать неубывающим, если делать какую-то операцию, то r (правая граница) должна быть равна n. Действительно, подняв правую часть массива мы точно не ухудшим результат. После этого нужно идти слева направо и жадно делать необходимое количество операций на каждом шагу.

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

205C - Маленький Слоник и промежуток

Естественно, для того что-бы решить задачу нужно написать функцию F(x) которая будет решать задачу на промежутке 0..x, тогда ответом будет F(r) - F(l - 1).

Опишем реализацию функции F(x). Если x < 10, результатом будем сам x. Пусть len — длина числа x, а x' — число x без первой и последней цифр, а x_i — i-я цифра числа x (от 0 слева направо). Переберем первую цифру d (она и будет последней) и длину того что внутри (пусть это будет i). Тогда если i < len - 2 или (i = len - 2 и d < x₀), к ответу нужно добавить 10ⁱ. Иначе, если i = len - 2 и d = x₀ то к ответу нужно добавить x', а если еще и i = len - 2, d = x₀ и x_len - 1 ≥ d то нужно добавить еще 1 к ответу.

Также эту задачу можно было решить используя ДП.

205D - Маленький Слоник и карточки

Эту задачу можно удобно решить используя структуру map, но можно и обойтись без нее (используя сортировку и бинарный поиск). Давайте переберем цвет-кандидат который и приведет к веселости набора, для каждого цвета узнаем минимальное количество переворачиваний (если возможно вообще) и выберем минимум. Если никакой цвет не подходит, ответ "-1". Для того чтобы найти минимальное количество переворачиваний нам нужно узнать два числа — количество карточек которые изначально лежат текущим цветом вверх, а также количество карточек у которых сзади есть текущий цвет (при этом сверху какой-то другой). Пусть это числа a и b. соответственно. Пусть m = (n + 1) / 2 — минимальное количество одинаковых карточек необходимых для того, что-бы сделать набор веселым. Тогда текущий цвет может сделать набор веселым только если a + b ≥ m. Если a ≥ m, то ничего переворачивать не надо, то есть ответ 0, иначе ответ равен m - a.

205E - Маленький Слоник и Фурик и Рубик

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

Пусть у нас текущий символ в первой строки с номером i (всюду 1-нумерация). Сначала решим задачу за O(N²). Переберем все позиции j левее i (или равные i) такие что B_j = A_i. Тогда для какой-то позиции нужно найти количество возможных пар строк таких, что в них именно эти два символы A_i и B_j совпали. Это количество будет равно j(n - i + 1) (j возможных символов слева и (n - i + 1) справа, поэтому общее количество это их произведение). Это будет O(N²). Так как все это — сумма, то ответ будет равен S_i(n - i + 1), где S_i — сумма всех позиций j таких, что B_j = A_i. Массив S можно несложно посчитать за линейное время. Аналогичным образом нужно обработать все индексы что правее i.

После того как количество пар подстрок в которых i-й символ первой строки имеет совпадение найдено (пусть это count), к ответу нужно добавить count / total, где total — полное количество возможных исходов, его можно найти циклом или несложной формулой.

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

204D - Маленький Слоник и ретро строки

Для начала нам нужно решить следующую подзадачу: для каждого префикса найти количество его заполнений таких, что он не содержит подстроки длиной k состоящую только из букв B. Пусть это будет F(x), где x это номер последнего символа префикса. Давайте присвоим F(x) = F(x - 1) * cnt, где cnt = 2, если S_x = 'X', 1 иначе. После такого присвоения в результат могли быть включены некоторые способы такие, что блок из k есть в конце префикса (они могли быть включены только если в подстроке S_{x - k + 1..x} нет букв W, а символ S_x - k не есть B), а это плохо. Поэтому (если такое могло произойти) нужно от F(x) отнять F(x - k - 1), это уберет все плохие варианты.

Аналогичное ДП нужно посчитать для для суффиксов (или, иначе говоря, для реверсовной строки S), только здесь нужно избегать блоков из W.

Теперь подумаем как организовать все что-бы не появилось повторов. Давайте переберем позицию, в которой будет заканчиваться первый слева блок из k подряд идущих букв B. При этом будем перебирать эту позицию справа налево. Используя ранее подсчитано ДП мы можем найти количество вариантов заполнить все буквы левее так, что-бы там не образовался блок. Если писать решение за O(N²), то мы можем перебрать позицию, в которой будет начинаться первый справа блок из k букв W, аналогичным образом найти количество способов заполнить все правее что-бы там не образовался блок, а символы между левым и правым блоками мы, очевидно, можем заполнять как-угодно. Но, так как мы идем справа налево, мы можем по ходу поддерживать сумму этих количеств. Это обеспечит нам линейность решения.

204E - Маленький Слоник и строки

Для решения данной задачи воспользуемся свойствами суффиксного массива. Болле подробно о суффиксном массиве можно почитать здесь:

http://e-maxx.ru/algo/suffix_array

Для начала нужно конкатенировать все строки в одну, при этом разделяя их какими-то символами которые не встречаются в строках. Например, три строки abc, a, ab можно склеить в одну следующего вида: abc#a@ab. Теперь нам нужно построить суффиксный массив по новой строке, это позволит нам отсортировать все циклические сдвиги строки. При этом первый символ каждого циклического сдвига это либо вспомогательный символ, либо символ какой-то входной строки.

Заметим теперь что для того что-бы найти результат нам нужно для каждого циклического сдвига, начало которого принадлежит какой-то входной строке, найти максимальную длину его префикса такую, что этот префикс является подстрокой как минимум k входных строк. Это число можно искать бинарным поиском, но для этого нужно какую-то функцию которая бы отвечала на вопрос: а сколько есть различных входных строк которые содержат префикс длины len циклического сдвига номер x (Пусть это функция F(x, len)).

Как же сделать функцию F(x, len)? Рассмотрим все циклические сдвиги, префикс длины len которых ровен префиксу длины len x-го сдвига. Заметим что, так как все сдвиги отсортированы лексикографически, набор таких сдвигов будет представлен каким-то промежутком [l;r] (1 ≤ l ≤ x ≤ r). Как же найти этот промежуток? Для каждой пары соседних сдвигов можно найти их наибольший общий префикс. Тогда l, например, можно найти используя RMQ — для этого нужно найти самую правую пару соседних сдвигов (левее x) таких, что их наибольший общий префикс меньше len. Аналогично можно найти r. После этого у нас есть промежуток [l;r] и нужно найти количество различных строк которые соответствуют этим сдвигам (иными словами, найти количество различных чисел в подмассиве). Но, заметим, что самое количество различных нас не интересует, а интересует только не меньше ли оно за k или нет. Тогда пусть L[i] равно максимальному j (j ≤ i) такому, что количество различных чисел в помассиве [j;i] ровно k. Тогда если L[r] ≥ l то, логично, что и в промежутке [l;r] также будет не меньше k различных чисел.

Осталось заполнить массив L. Это довольно просто сделать используя структуру set (можно также использовать RMQ). Будем идти слева направо и в сете поддерживать индексы самых правых k различных чисел. Тогда если поступает какое-то число, то (если оно встречалось раньше) его прежнее вхождение нужно удалить из сета (если оно еще осталось) и вставить текущее. При этом если размер сета превышает k нужно извлекать минимальный элемент. Тогда если в какой-то позиции i размер сета есть k (после описанных выше изменений), это означает, что L[i] ровно минимальному элементу сета.

Так как мы O(N) раз используем бинарный поиск, а функция F(x, len) работает за O(logN), финальная асимптотика решения равна O(Nlog²N).