337A - Пазлы

В первую очередь, упорядочим числа f[i] по возрастанию. Теперь допустим, что самый маленький пазл, который приобретет учительница, состоит из f[k] фрагментов. Понятно, что в таком случае для минимизации разницы она должна приобрести наименьшие n пазлов, равных или превосходящих f[k] по размеру, то есть пазлы размеров f[k], f[k+1], ..., f[k+n-1] (это не совсем правильно, если среди f[i] встречаются повторяющиеся числа и выполняется f[k]=f[k-1], но такие случаи можно не рассматривать). Разница между наибольшим и наименьшим количествами фрагментов в таком наборе равняется f[k+n-1]-f[k].

Чтобы выбрать оптимальное f[k], переберем значение k от 1 до m-n и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом:

read(n, m, f[1..m])
sort(f[1..m])
best = INFINITY
for k = 1 to m-n
  best = min(best, f[k+n-1] - f[k])
print best

337B - Бытовая задача

Допустим, что ширина и высота монитора равны W и H соответственно. Так как W:H = a:b, мы имеем H=W*b/a. Аналогично, ширина и высота картинки фильма w и h удовлетворяют соотношению h=w*d/c. Представим себе, что Манао растягивает (или, наоборот, сужает) картинку фильма до тех пор, пока она не упрется в стенки экрана по горизонтали или вертикали. Рассмотрим три случая: соотношение горизонтали и вертикали монитора меньше, больше и равно соответствующему соотношению картинки фильма.

В первом случае (a/b < c/d) картинка заполнит всю горизонталь экрана, и процесс растяжения остановится. Таким образом, новая ширина картинки будет равняться W, то есть картинка увеличилась в W/w раз. Соответственно, её новая высота равна h*W/w = w*c/d * W/w = W*d/c. Нас интересует, какая часть вертикали экрана осталась незанятой, то есть (высота экрана - новая высота картинки) / (высота экрана) = (W*b/a - W*d/c) / (W*b/a) = (bc-ad)/bc.

Во втором случае (a/b > c/d) картинка первой заполнит вертикаль. В этом случае, её высота будет равна H, а ширина — w*H/h = w * W*b/a / (w*d/c) = W*b/a * c/d. Часть горизонтали, оставшася незанятой, равна (W - W*b/a * c/d)/W = (ad-bc)/ad.

В третьем случае картинка заполнит экран полностью, поэтому ответом задачи будет 0.

Для того, чтобы вывести ответ в виде несократимой дроби, нужно найти наибольший общий делитель его числителя и знаменателя. Сделать это можно с помощью алгоритма Евклида, или просто циклом перебрать все числа от 1 до q и выбрать наибольшее, делящее их обоих. Так как q не превосходит произведения двух чисел из входных данных, а значения этих чисел ограничены 1000-ей, в худшем случае придется рассмотреть лишь миллион чисел.

337C - Викторина

Допустим, что Манао в процессе игры удвоил свой счет (за счёт ответа на k последовательных вопросов) ровно X раз. Тогда меньше всего очков Манао наберет, если эти удвоения произойдут в самом начале игры — то есть он ответит подряд на первые X*k вопросов, а потом ни разу не сможет ответить на k последовательных вопросов. Правильность этого утверждения основывается на том, что в любом другом сценарии с X удвоениями можно сдвинуть все удвоения в начало и этим не увеличить счет. Таким образом, для X=1 Манао наберет как минимум k*2+m-k очков: ответит на k последовательных вопросов, затем счет удвоится, а затем Манао ответит ещё на m-k вопросов. Для X=2 минимальный возможный счет равен (k*2+k)*2+m-2*k, для X=3 — ((k*2+k)*2+k)*2+m-3*k. В общем случае мы получаем формулу (2^1+2^2+...+2^X)*k + m-X*k = (2^(X+1)-2)*k + m-X*k.

Из сделанного выше наблюдения становится понятно, что счет монотонно растет с увеличением X, поэтому нужно лишь найти наименьшее подходящее значение X. Оно должно удовлетворять неравенствам X*k <= n и X + (n - n mod k) / k * (k-1) + n mod k >= m. Поподробнее о втором неравенстве: на первые X*k вопросов Манао ответил, таким образом осталось ещё n-X*k. Теперь он может отвечать максимум на k-1 вопрос из каждых k. Если бы n-X*k делилось на k (что есть то же самое, что n делится на k), неравенство имело бы вид X*k + (n-X*k) / k * (k-1) >= m, но из-за остатка формула получается более сложной: X*k + (n - X*k - (n - X*k) mod k) / k * (k-1) + (n - X*k) mod k >= m. Упрощая все что можно, получаем из неё формулу, приведенную выше. Таким образом, минимальный X равен max(0, m - (n - n mod k) / k * (k-1) - n mod k). Для вычисления счета, соответствующего найденному значению X, нужно использовать бинарное возведение в степень. Таким образом, итоговая сложность решения — O(log(n)).

337D - Книга Зла

Очевидно, что на языке теории графов перед нами стоит следующая задача — дано дерево из n вершин, m из которых помечены; найти количество вершин, расстояние от которых до каждой из помеченных вершин не превосходит d.

Давайте подвесим дерево за какую-либо вершину r, то есть будем рассматривать его как корневое дерево с корнем в r. Перефразируем условие, налагаемое на искомые вершины: нам нужно посчитать количество таких вершин v, что максимальное расстояние от v до какой-либо помеченной вершины не больше d.

Для любой внутренней вершины v, наиболее отдаленная от неё вершина находится или в поддереве v, или за его пределами — во втором случае путь от v до наиболее отдаленной помеченной вершины проходит через родителя вершины v. Используя данное наблюдение, можно быстро пересчитывать расстояния до наиболее отдаленных помеченных вершин при переходе от некоторой вершины к её ребенку.

Для начала давайте посчитаем расстояние от каждой вершины v до самой далекой от неё помеченной вершины в поддереве v. Будем называть это расстояние distDown[v]. Посчитать значения distDown[] можно с помощью поиска в глубину: для листьев дерева это расстояние или равно 0 (когда сам лист является помеченной вершиной), или условно минус бесконечности (когда лист не является помеченной вершиной), а для каждой внутренней вершины v distDown[v]=max(distDown[child1], distDown[child2], ..., distDown[childK])+1, где childi — дети вершины v.

Теперь будем считать расстояния от каждой вершины до наиболее отдаленной от неё помеченной вершины вне её поддерева. Будем называть это расстояние distUp[v]. Для вычисления значений distUp[] мы опять-таки используем поиск в глубину. Для корня дерева distUp[r] условно равно минус бесконечности, а для любой другой вершины v есть два случая — или наиболее отдаленная от неё помеченная вершина находится в поддереве родителя p вершины v, или ещё "дальше", то есть путь к ней проходит через родителя p. В первом случае расстояние от v до такой вершины равно max(distDown[sibling1], ..., distDown[siblingK])+2, где siblingi — это братья (другие дети родителя) вершины v. Во втором случае оно равно distUp[p]+1. Таким образом, distUp[v] равен максимуму из этих двух величин. Надо заметить, что для обеспечения линейной работы этого поиска в глубину в первом случае нужно найти максимальное max1 и второе максимальное max2 среди значений distDown[sibling1], ..., distDown[siblingK]. Затем, если distDown[v] < max1, тогда max(distDown[sibling1], ..., distDown[siblingK])=max1, в противном же случае, при distDown[v] = max1, мы имеем max(distDown[sibling1], ..., distDown[siblingK])=max2.

Имея значения distDown[] и distUp[], ответ найти просто: это количество таких v, что distDown[v] <= d && distUp[v] <= d.

Для иллюстрации этой идеи можете посмотреть 4302127.

337E - Дерево делителей

Для начала покажем, что единственные вершины в оптимальном дереве делителей, которые могут не содержать одного из значений a[i], это листья и корень. Допустим, у нас есть некоторая внутренняя вершина, не являющася корнем, в которой записано число X, не равное ни одному из a[i]. Тогда можно исключить эту вершину из дерева, а её сыновей "прицепить" к её родителю без нарушения какого-либо из свойств дерева.

Таким образом, наше дерево состоит из корня, прицепленных к нему или друг к другу в некотором порядке вершин с числами a[i] и идущих из них листьев, содержащих числа из их разложений на простые множители. Исключениями из этого наблюдения является ситуация, когда в корне записано одно из чисел a[i], и ситуация когда среди a[i] встречаются простые числа. Также заметим, что в общем случае количество листьев в дереве будет равнятся сумме показателей степеней простых чисел в разложении на простые множители тех a[i], которые являются детьми корня.

Так как N <= 8, можно попытаться перебрать все возможные деревья, удовлетворяющие сделанным наблюдениям. Упорядочим числа a[i] по убыванию и рекурсивно будем выбирать для каждого из них, к какой из уже имеющихся вершин добавить сына с соответствующим числом. Понятно, что чтобы добавить число X к некоторой вершине v, произведение X и чисел в сыновьях v должно делить число в самой вершине v. Для первого из чисел a[i] у нас есть выбор — сделать его корнем дерева, или сделать сыном корня (в котором будет записана условная бесконечность, делящаяся на любые числа). Для каждого следующего числа выбор заключается в том, сделать его сыном корня (если таковой присутствует как отдельная от вершина) или вершины, содержащей одно из предыдущих чисел. В сумме мы рассматриваем O(N!) вариантов.

Для иллюстрации этой идеи можете посмотреть 4302171.

338D - Таблица НОД

Наблюдение 1. Если последовательность a встречается в таблице G, то она обязательно должна встречаться в строке i = LCM(a[1], ..., a[k]). Докажем это утверждение. Понятно, что теоретически она может встречаться только в строках, номера которых кратны i, так как номер строки должен делиться на каждое из чисел a[index]. Рассмотрим некоторую строку с номером i*x, где x>1. Строки i и i*x отличаются только в таких элементах j, что i*x и j делятся на степень p^q некоторого простого числа, на которое не делится i (соответственно G(i*x, j) делится на p^q). Но ни один из a[index] на такое p^q делиться не может, потому что тогда бы и i делилось на p^q. Соответственно, если искомая подстрока находится в i*x-ой строке, то она не может содержать индекса j. Раз она может содержать только те индексы, где элементы в строках i и i*x совпадают, достаточно проверять лишь i-ую строку. Отсюда ясно, что если i > n, ответ задачи "NO".

Наблюдение 2. Искомый индекс j должен удовлетворять следующую систему линейных уравнений по модулю:

j = 0 (mod a[1])
j + 1 = 0 (mod a[2])
...
j + l = 0 (mod a[l + 1])
...
j + k - 1 = 0 (mod a[k])

<=>

{j = -l (mod a[l + 1])}

Иными словами, j + l должно делиться на a[l+1] для каждого l=0..k-1.

Согласно Китайской теореме об остатках, у такой системы есть решение тогда и только тогда, когда для каждой пары индексов x, y (0 <= x, y <= k-1) мы имеем -x = -y (mod GCD(a[x+1], a[y+1])). Положим L = LCM(a[1], ..., a[k]). Если у системы есть решение, тогда оно единственно в интервале [0, L), а все остальные решения конгруэнтны ему по модулю L. Допустим, мы вычислили минимальное неотрицательное j, удовлетворяющее данной системе. Тогда, если последовательность a встречается в таблице G, она обязательно будет начинаться с j-ого элемента строки i. Понятно, что теоретически она может начинаться с любого индекса вида j+x*L, x>=0, но i = L, поэтому G(i, j+X*L) = GCD(i, j+X*i) = GCD(i, j). Поэтому достаточно проверить, совпадают ли k последовательных элементов, начинающихся с j-ой позиции i-ой строки, с последовательностью a. Также понятно, что если j > m-k+1, то ответ задачи "NO".

Наконец, рассмотрим как можно найти решение системы линейных уравнений по модулю (и заодно проверить её решаемость, так как предложенная ранее проверка в лоб будет работать слишком долго). Для этого можно использовать следующий вспомогательный метод, которой для данных значений r1, m1, r2, m2 находит минимальное число X такое, что X = r1 (mod m1) и X = r2 (mod m2), или определяет что его не существует. Пусть X = m1*x + r1, тогда мы имеем m1*x + r1 = r2 (mod m2). Это можно представить в виде Диофантового уравнения m1*x + m2*y = r2-r1, решение которого является делом техники. Наименьший неотрицательный x, если таковой существует, даёт нам искомое X = m1*x + r1. Теперь этот метод можно использовать, чтобы найти минимальное решение X1, удовлетворяющее первые два уравнения. Теперь можно считать, что у нас уже k-1 уравнение, в котором вместо двух первых есть новое уравнение j = X1 (mod LCM(a[1], a[2])), и повторить эту же процедуру снова. Используя этот метод k-1 раз, мы получим итоговое решение для всей системы.

Заметим также, что предложенное решение не требует имплементации длинной арифметики:

— Процесс подсчета LCM(a[1], ..., a[k]) можно реализовать так, чтобы при каждом умножении проверять, не станет ли результат больше n, а в таком случае сразу выводить "NO";

— К моменту решения системы уравнений, нам уже известно что L <= n <= 10^12, поэтому все промежуточные модули также будут в этих пределах;

— Расширенный алгоритм Эвклида находит решения в тех же пределах, что и входные числа, поэтому также будет оперировать числами до 10^12.

Итоговая сложность алгоритма — O(k logn).

338E - Оптимизировать!

Оформление задачи представляет собой небольшой эксперимент, хотя я и не буду претендовать на абсолютную новизну такой идеи. Условие нужно понять из псевдокода очень медленного решения. Заключается оно в следующем: даны массивы A[1..N] и B[1..L] и число H. Нужно посчитать, сколько (непрерывных) подмассивов S массива A длины L имеют свойство — можно так перемешать элементы массива B, что каждая из сумм S[i]+B[i] (1<=i<=L) будет не меньше H.

Понятно, что задачу для каждого отдельного подмассива можно решать за время O(NlogN), если упорядочить массив B, а для каждого подмассива S упорядочить его в обратном направлении и проверить что требуемое условие выполняется. Более общая идея решения, которую можно имплементировать с такой же асимптотической сложностью — для каждого из чисел B[i], нам нужно сопоставить ему наименьшее из чисел S[j] такое, что B[i]+S[j]>=H. Заметим, что числа B[i] можно обрабатывать в любом порядке. Также заметим, что S и B можно поменять местами, то есть искать наименьшую пару для каждого S[i] в массиве B. И последнее — если S и B упорядочены заранее, то обработка сегмента производится за O(N).

При рассмотрении каждого подмассива по отдельности лучшей асимптотики не достичь, поэтому попробуем решать задачу для нескольких подмассивов одновременно. Допустим, что массив B уже упорядочен по возрастанию. Возьмем некоторое число X < L и рассмотрим некоторый подмассив A[i..i+X-1]. Давайте обработаем все числа из этого подмассива — то есть для каждого из них найдём наименьшее B[j], которое в сумме с ним не меньше H, и уберём элемент B[j] из массива B. Эту обработку можно выполнить за время O(N), если изначально иметь упорядоченный массив элементов A и соответствующих индексов: из такого массива мы можем получить элементы сегмента A[i..i+X-1] в порядке возрастания, а мы уже знаем, что имея их в таком виде и имея упорядоченный массив B, задачу можно решить за линейное время.

Теперь мы можем найти ответ для каждого подмассива S длины L, левый край которого находится в интервале [i-Y, i], за время O(YlogY), где Y=L-X. Для этого просто возьмём те Y элементов, которые входят в S и не входят в A[i..i+X-1], и обработаем их на остатке чисел из массива B. Если для каждого из этих элементов нашлась пара, то подмассив S имеет нужное свойство, в противном случае нет. Более того, хотя для каждого отдельного сегмента нам обязательно нужно O(YlogY) времени, здесь также можно воспользоваться тем, что сегменты пересекаются и получить амортизированную сложность O(Y) на сегмент. Заметим, что для обработки остатка сегмента за время O(Y) нам нужно лишь иметь его элементы в упорядоченном состоянии. Для самого левого сегмента, который мы будем обрабатывать, честно упорядочим его элементы, а для каждого следующего (который отличается от предыдущего ровно в двух элементах) нужно лишь O(Y) операций, чтобы обновить упорядоченный массив элементов. Таким образом, мы получаем сложность O(YlogY + Y^2) для обработки всех Y сегментов в сумме, что даёт O(Y) на один сегмент в среднем.

Вернемся к общей картине. Чтобы рассмотреть все подмассивы длины L, нам нужно использовать вышеуказанный алгоритм для каждого из сегментов A[Y..Y+X-1], A[2Y+1..2Y+X], A[3Y+2..3Y+X-1], .... Таким образом, мы O(N/Y) раз запускаем алгоритм со сложностью O(N+Y^2). Получается, что нам надо выбрать Y, минимизирующий N*N/Y + N*Y, откуда мы имеем Y=~sqrt(N). Итоговая сложность алгоритма получается O(Nsqrt(N)). Тем не менее, отдельно надо рассмотреть случай L < sqrt(N), потому что Y = L - X < L. Здесь задачу можно решать за время O(NL) подобной прошлому подходу идеей: упорядочив самый левый подмассив длины L, для получения упорядоченной версии каждого следующего требуется лишь O(L) операций.

Имплементацию этой идеи вы можете увидеть в 4302344.

P.S. Условие "задачи", которую решает Манао, на самом деле содержит текст одной грузинской сказки. Вы можете скопировать (почти) его отсюда и попробовать понять смысл переведенного текста :)