Div. 2 A — Драконы

Заметим, что если Кирито сражается с драконом, сила которого меньше силы Кирито, то Кирито ничего не теряет — наоборот, его сила увеличивается на целое неотрицательное число. Поэтому будем всё время выбирать какого-либо дракона с меньшей силой, чем у Кирито в данный момент, и сражаться с ним. Так будем продолжать до тех пор, пока не победим всех драконов (тогда ответ — «YES»), или пока не останутся только драконы, которых Кирито не может победить (тогда ответ — «NO»). Дракона на каждом шаге можно искать по-разному — как проходиться по всем драконам, так и сначала отсортировать драконов по возрастанию силы.

Сложность решения — O(n²) или . Пример решения: http://pastie.org/4897164 (сохранённая копия)  

Div. 2 B — Т-простые числа

Можно показать, что Т-простыми являются только квадраты простых чисел, и их не так и много — столько, сколько есть простых чисел, не больших . Вычислим все эти числа (например, с помощью решета Эратосфена) и запишем в массив или std::set, тогда на каждый запрос можно отвечать, просто проверяя (двоичным поиском для версии с массивом), есть ли данное число среди заранее вычисленных.

Сложность решения линейная от n — или , где d = 10¹² (можно вывести и более точную оценку). Пример решения: http://pastie.org/4897166 (сохранённая копия)

Div. 1 A — Сдвиги

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

Сложность решения — O(nm). Пример решения: http://pastie.org/4897169 (сохранённая копия)

Div. 1 B — Планеты

Можно заметить, что если мы посещаем конкретную планету, то выгоднее всего как можно раньше прибыть на неё, а потом подождать ближайшего свободного момента, и тогда отправиться дальше. Поэтому задачу можно решать с помощью алгоритма Дейкстры, немного поменяв определение кратчайшего пути. Когда мы рассматриваем очередную планету (то есть, мы уже знаем минимальное расстояние до неё), надо пройтись по соответственному списку моментов времени и найти первый момент, когда из этой планеты можно отправляться снова — этот момент и будет расстоянием, которое мы будем добавлять к путям, исходящим из этой планеты. Понятно, что по каждому списку мы пройдёмся не более одного раза. Ещё надо обратить внимание на случаи, когда путешественник прибывает на планету 1 в момент времени 0 (тогда Джек должен ждать), и когда путешественник прибывает на планету n одновременно с Джеком (тогда Джек не должен ждать).

Сложность решения — . Пример решения: http://pastie.org/4897171 (сохранённая копия)

Div. 1 C — Треугольники

Назовём рёбра Боба антирёбрами. Для каждой пары рёбер полного графа, которые проходят через одну вершину, присвоим вес: каждой паре рёбер значение +2, каждой паре ребро и антиребро — значение −1, и каждой паре антирёбер +2. Посчитаем сумму всех значений. Можно заметить, что каждый треугольник даёт в сумме вес +6, а все остальные комбинации из трёх вершин дают вес 0. Саму сумму считаем, для каждой вершины считая вес каждой пары рёбер, которые проходят через эту вершину. Если степень вершины d, то к сумме нужно прибавить d(d - 1) - d(n - d - 1) + (n - d - 1)(n - d - 2). В конце остаётся разделить сумму на 6, и получаем ответ.

Сложность решения — O(m + n). Пример решения: http://pastie.org/4897512 (сохранённая копия)

Div. 1 D — Башни

Посчитаем динамику d[i][k] — минимальная высота последней башни, которую мы можем получить, соединив первые слева i башен в не менее чем k башен. Допустим, посчитали динамику для первых i башен. Переберём отрезки башен [i + 1;j], пусть сумма высот на этом отрезке s. Найдём наибольшее k такое, что d[i][k] не больше s. Тогда обновим ответ для d[j][k+1]. Заметим, что при увеличении k увеличиваются и значения d[i][k]. Поэтому сами отрезки можно перебирать по уменьшению j, а подходящее k находить указателем по порядку.

Когда приходим на позицию j, какие-то значения d[j][k] обновлены, а какие-то — нет. Используя то же наблюдение, что при возрастании k возрастает и d[j][k], пройдём по этим значениям в порядке уменьшения k, и будем обновлять минимум для d[j][k]. Это делаем в начале итерации динамики.

В конце найдём максимальный k, для которого существует ответ среди значений d[n][k]. Ответом на задачу является n - k.

Сложность решения — O(n²). Пример решения: http://pastie.org/4897515 (сохранённая копия)

Div. 1 E — Дары

Сперва установим пару фактов, которые будем использовать в решении. Узнаем, с какой вероятностью мы можем получить одно множество из даров, среди которых i-того названия ровно a_i даров. Всего таких множеств , т.к. множеств элементов i-того названия счётом a_i есть ровно , а два разных названия при выборе ответа независимы. Одно конкретное множество мы тогда можем получить с вероятностью , попросив i-того названия ровно a_i штук.

Теперь мы знаем вероятность p получения одного множества элементов A. Заметим, что за константное время мы можем из p узнать вероятность p' получения множества A, к которому добавлен другой элемент x-того названия. Допустим, что в A есть ровно a_x даров x-того названия. Используя ранее полученную формулу, можно вывести:

То есть, p' мы можем вычислить за константное время, зная p.

Используя это, решим собственно задачу. Отсортируем все дары в порядке убывания ценностей. Ясно, что названия всех тех даров, ценности которых не равны n-той ценности в этом массиве (обозначим эту ценность как d), нам однозначно надо назвать, чтобы получить n самых ценных даров. Назовём это множество даров базой и посчитаем с помощью формулы вероятность получения базы p. Неопределёнными остаются только те дары, ценность которых равняется d. Потому что, если всего таких даров s, а количество недостающих даров (кроме базы) l, то всего возможно вариантов, как мы можем вместе с названиями даров базы назвать множество остальных l названий, у которого будет шанс получить n самых ценных даров.

Теперь у нас есть s «неопределённых» даров с ценностью d, пронумеруем их в каком-то порядке, и назовём их спорными. Будем считать динамику f(x, y) — суммарная вероятность получить n самых ценных даров, если взяли x спорных из первых y спорных. Ясно, что f(0, 0) = p, а f(l, s) — ответ на задачу. Используя ранее найденные коэффициенты, получаем в самой динамике два перехода:

1. , если к комплекту из x спорных среди первых y спорных добавим y + 1-ое спорное;
2. , если, наоборот, не добавляем.

Данную динамику можно посчитать за время O(t²), где t — суммарное количество даров.

Сложность решения — . Пример решения: http://pastie.org/4897519 (сохранённая копия)