909A - Генерация логина

Самое простое решение — сгенерировать все возможные логины (перебрав все пары непустых префиксов имени и фамилии и скомбинировав их) и выбрать из них первый по алфавиту.

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

Эти свойства дают жадное решение: будем перебирать буквы имени, начиная со второй. Как только найдена буква, большая или равная первой букве фамилии, возвращаем префикс имени до этой буквы (не включая ее) плюс первую букву фамилии. Если таких букв нет, возвращаем все имя плюс первую букву фамилии.

909B - Отрезки

Рассмотрим участок координатной прямой [i, i + 1]. Очевидно, все отрезки, покрывающие этот участок, должны находиться в разных слоях. Для каждого из этих отрезков левый конец находится в одной из точек 0, 1, ..., i (i + 1 вариантов), а правый — в одной из точек i + 1, i + 2, ..., N (N - i вариантов). Итого отрезков, покрывающих участок [i, i + 1], будет M_i = (i + 1)(N - i) штук. Наибольшая из величин M_i для i = 0, ..., N - 1 даст нам оценку снизу для необходимого количества слоев.

Задача не требует разбиения отрезков на слои в явном виде, поэтому можно предположить, что эта оценка снизу — точная. max M_i можно найти за O(N), или можно заметить, что максимум достигается для (для центрального отрезка, если N нечетное, или одного из двух центральных, если N четное).

Ответ — .

Этот же ответ можно получить явным построением. Отсортируем отрезки в порядке неубывания их левых концов и затем в порядке возрастания их правых концов. Будем распределять отрезки по слоям жадно: если i — левый конец текущего отрезка, и участок [i, i + 1] свободен в каком-то слое, добавим текущий отрезок к этому слою; иначе начнем новый слой с этим отрезком.

и да, это наша задача с решением за O(1) :-)

909C - Отступы в Python

Эту задачу можно решить при помощи динамического программирования.

Рассмотрим все возможные программы, которые заканчиваются инструкцией i, записанной с отступом j. Обозначим количество таких программ dp[i][j].

Для первой инструкции dp[0][0] = 1, dp[0][j] = 0 для j > 0 (есть ровно одна программа, состоящая из одной инструкции, и она записана с нулевым отступом).

Рекуррентное соотношение для перехода к следующей инструкции в программе следует из описания инструкций: когда мы добавляем инструкцию i + 1, возможные значения отступа для нее зависят от возможных значений отступа инструкции i и от типа инструкции i. Если инструкция i — цикл, инструкция i + 1 должна иметь отступ на один больше предыдущей, поэтому dp[i + 1][0] = 0 и dp[i + 1][j] = dp[i][j - 1] для j > 0. Если инструкция i — простая инструкция, то команда i + 1 может быть частью тела любого из предшествующих циклов, и иметь любой отступ от 0 до отступа инструкции i. Если мы обозначим отступ инструкции i (простой инструкции) как k, отступ инструкции i + 1 как j, нам нужно просуммировать все случаи, для которых k ≥ j: .

Итоговый ответ будет общим количеством программ, заканчивающихся последней инструкцией с любым отступом: .

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

909D - Разноцветные точки

Непосредственная реализация действий, описанных в задаче, с перебором всех точек для определения того, какие из них удалять, имеет сложность O(N²) и занимает слишком много времени.

Рассмотрим непрерывные группы точек одинаковых цветов. Одно действие удалит только точки на границах группы (за исключением точек на левой границе самой левой группы и правой границе самой правой группы, если в этих группах больше одной точки), остальные точки будут не затронуты. Если текущие размеры групп слева направо N₁, N₂, ..., N_G - 1, N_G, то размеры групп после выполнения первого действия — N₁ - 1, N₂ - 2, ..., N_G - 1 - 2, N_G - 1, после выполнения второго — N₁ - 2, N₂ - 4, ..., N_G - 1 - 4, N_G - 2 и т.д. Этот процесс продолжается до тех пор, пока одна из групп не исчезнет, после этого ее соседние группы могут объединиться, если они одного цвета.

Это наблюдение позволяет симулировать несколько действий за одну итерацию:

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

2. Пересчитать размеры групп после этого количества действий.

3. Удалить пустые группы.

4. Объединить соседние группы одного цвета.

Такая итерация требует O(G) времени и удаляет O(G) точек (не менее одной точки из каждой из G групп). Если начальное количество точек было N, мы можем удалить не более N точек. Таким образом, сложность этого решения — O(N).

909E - Сопроцессор

Действовать следует жадно: пока есть задачи, которые могут быть выполнены на главном процессоре сейчас (т.е. все задачи, от которых они зависят, уже выполнены), их следует выполнять; затем следует переключиться на сопроцессор и выполнять все задачи, которые могут быть выполнены на нем; затем переключиться обратно на главный процессор и т.д. Это можно сделать при помощи аккуратно реализованного поиска в ширину. Один из вариантов реализации — вместо того, чтобы на каждом шаге искать доступные задачи, их следует хранить в двух очередях (задачи, доступные главному процессору и сопроцессору) и добавлять задачу в соответствующую очередь, как только все задачи, от которых она зависит, выполнены.

Существует также более формальное решение. Определим T_i как минимальное количество вызовов сопроцессора, необходимое для выполнения i-ой задачи, и выведем рекуррентное соотношение для T_i. Если u — задачи и v₁, ..., v_k — ее зависимости, очевидно для каждого i T_u ≥ T_vi (потому что u должна выполняться после v_i). Затем, если v_i выполняется на главном процессоре, а u — на сопроцессоре, то выполнение u потребует дополнительного вызова сопроцессора. Таким образом, T_u = max_i(T_vi + s_i), где s_i = 1, если u выполняется на сопроцессоре и v_i — на главном процессоре; иначе, s_i = 0. Теперь все T_i можно вычислить при помощи рекурсивного обхода графа зависимостей (или обхода задач в топологическом порядке). Ответ — max T_i.

909F - И-перестановки

Перестановка p (p_i & i = 0)

Если N нечетно, ответ NO. Действительно, любое число в позиции с нечетным номером i p_i должно быть четно (в противном случае последний бит p_i&i равен 1). Для нечетных N четных чисел меньше, чем позиций с нечетным номером, поэтому в какой-то из позиций окажется нечетное число, следовательно, сконструировать нужную перестановку невозможно.

Если N четно, ответ YES. Чтобы построить нужную перестановку, заметим, что (2^k - i)&(2^k + i - 1) = 0. Например, для k = 5:

100000 = 2⁵

011111 = 2⁵ - 1

100001 = 2⁵ + 1

011110 = 2⁵ - 2

и так далее.

Мы можем использовать это наблюдение, чтобы составлять пары из чисел 2^k - i и 2^k + i - 1, то есть выбирать p_2^k - i = 2^k + i - 1 и p_{2^k + i - 1} = 2^k - i.

Полная процедура построения нужной перестановки следующая. Для заданного четного N, найдем максимальную степень двойки, не превышающую N, 2^k. Составим пары из чисел 2^k - i и 2^k + i - 1 для всех i = 1..N - 2^k + 1. Если после этого остались еще неиспользованные числа, это будут числа от 1 до 2^k - (N - 2^k + 1) - 1 = 2^k + 1 - N - 2. Повторим процесс для N' = 2^k + 1 - N - 2.

Рассмотрим процесс на примере N = 18. На первом шаге мы выбираем 2^k = 16 и составляем пары из чисел 15-16, 14-17 и 13-18. На втором шаге неиспользованными остаются числа от 1 до 12, мы выбираем 2^k = 8 и составляем пары 7-8, 6-9, 5-10, 4-11 и 3-12. На третьем и последнем шаге неиспользованными остаются числа 1 и 2, мы выбираем 2^k = 2 и составляем пару из чисел 1 и 2. После этого все числа использованы, и перестановка построена.

Перестановка q (q_i & i ≠ 0)

Для N = 1..7 мы можем рассмотреть все перестановки вручную и выяснить, что для N = 1..5 ответ NO, для N = 6 возможная перестановка \textbf{3 6 2 5 1 4} (из примера в условии), и для N = 7 возможная перестановка \textbf{7 3 6 5 1 2 4}.

Если N — степень двойки, ее двоичное представление 10..0. По условию q_N ≠ N, поээтому q_N < N, и двоичное представление q_N короче, чем двоичное представление N. Следовательно, q_N&N = 0, и ответ в этом случае NO.

Наконец, если N > 7 и N — не степень двойки, нужная перестановка всегда существует, и ее можно построить следующим образом. Разобьем все числа от 1 до N на следующие группы (k — наибольшая степень двойки, которая все еще меньше N):

1..7

8..15

16..31

\ldots

2^k - 1..2^k - 1

2^k..N

Для первой группы используем перестановку, которую мы нашли вручную для N = 7. Для остальных групп используем произвольную перестановку чисел в этой группе (например, циклическую перестановку). Числа в каждой группе, кроме первой, имеют общий ненулевой бит в одной и той же позиции (соответствующей степени двойки, с которой начинается группа) поэтому q_i&i гарантированно имеет ненулевой бит в этой же позиции.