Задача А:

Заметим, что в конец копируется элемент, который был k-тым. Затем копируется элемент, который был (k+1)-м в исходном массиве, затем (k+2)-й, ... , n-й, k-тый, (k+1)-й etc. Значит, все числа станут одинаковыми тогда и только тогда, когда в исходной последовательности все числа с k-го по n-й были одинаковы. Теперь очевидно и то, что количество операций, требуемое для этого, равно номеру последнего не равного n-му элемента последовательности, так как ровно столько удалений понадобится для того, чтобы убрать не равные ему элементы. Если этот номер больше, чем k, то ответа нет. Асимтотика — O(N).

Задача B:

Давайте на каждом шаге будем хранить текущий порядок строк и порядок столбцов в таблице, относительно начального. То есть, row[x] — номер строки x в начальной таблице, а column[x] — номер столбца x в начальной таблице. Тогда значение элемента в строке x и столбце y текущей таблицы будет равно t[row[x], column[y]], где t — начальная таблица. В запросах обновления нужно просто поменять местами ячейки соответствующего массива с номерами x и y. Асимптотика O(n * m + k).

Задача C:

Для начала факторизуем числитель и знаменатель. Теперь для каждого простого числа x мы знаем степень этого числа в факторизации числителя(a[x]) и в факторизации знаменателя(b[x]). Для любого простого числа x мы можем вычислить его степень в факторизации числителя числа после сокращения(newa[x]) и в факторизации знаменателя этого числа(newb[x]): newa[x] = a[x] — min(a[x], b[x]), newb[x] = b[x] — min(a[x], b[x]). У нас есть числитель и знаменатель ответа(в факторизованном виде), осталось только привести их в вид, требуемый в условии. Один из способов — заметить, что дробь из условия подходила под все требования. Поэтому можно факторизовать ее еще раз и вывести такую же дробь, но так, чтобы ни одно простое число не имело большую степень, чем в посчитанных нами newa и newb. Получившиеся числа будут подходить под ограничения и их частное будет равно искомому числу. Если пробовать строить ответ жадно (набирать множители, пока их произведение <= 10^7), то количество чисел в ответе выходит за рамки 10^5. Асимптотика решения O(max + n * log max). Факторизация за O(sqrt(max)) получала TL, поэтому нужно было воспользоваться более быстрыми способами. Например — посчитать для каждого числа его наименьший простой делитель с помощью линейного решета эратосфена.

Задача D:

Во-первых, заметим, что наилучшее место, которое мог занять Вася — это первое, ведь ограничений сверху на его балл нет. Теперь нужно найти самое худшее место из тех, что он мог занять. Переформулируем. Нужно максимизировать количество таких участников, что если участник в первом туре набрал a[i] баллов, во втором — b[j], то a[i]+b[j] >= x. То есть, нам нужно найти максимальное паросочетание в двудольном графе, в котором ребро между вершинами i первой доли, j второй доли есть тогда, когда a[i] + b[j] >= x. Для решения этой подзадачи достаточно было отсортировать вершины в обоих долях по весу, и пройтись двумя указателями. Допустим, мы отсортировали по убыванию веса. Возьмем два указателя L = 1 в левой доле и R = N в правой доле. Пока a[L] + b[R] < x (то есть нет ребра L->R) нам стоит уменьшить R — взять вершину во второй доле с большим весом. Как только мы нашли R такое, что a[L] + b[R] >= x, мы берем ребро L->R и добавляем в ответ. Все — переходим к следующим L и R. Несложно показать, почему этот алгоритм найдет оптимальное решение. Я нашел поистине удивительное доказательство этому, но поля этого разбора слишком узки для него. Асимптотика — O(N log N) на сортировку и O(N) на два указателя.

Задача Е:

1) Решение за O(n*m*m): Простая динамика. Состояние — d[n][m] — сколько возможных цепочек длины n могут заканчиваться на символ m. Переход — перебираем все возможные символы, и смотрим, можно ли поставить символ k после символа m.

2) Решение за O(m*m*m*log n): Заметим, что в нашей динамике переход всегда одинаковый. Можно составить матрицу перехода A размером MxM. Если jый символ может идти за iым, то A[i][j]=1, иначе A[i][j]=0. Пусть есть вектор размером 1хМ b={1,1,...,1}. Тогда можно заметить, что b * a^(n-1) = ans. Воспользуемся бинарным возведением в степень для того, чтобы посчитать a^(n-1). Отдельно следует рассмотреть случай n==1. Ответом будет сумма элементов в векторе ans. Асимптотика — m^3 на перемножение матриц и log n на бинарное возведение в степень.