Формулы генерируются со скрипом, надо обновлять страницу, чтобы они появлялись.

155A - I_love_\%username\%

Надо сделать, что написано: считать массив и посчитать количество элементов, больших или меньших всех предыдущих. Массив для этого можно даже не хранить, а поддерживать текущий минимум и максимум. Сложность — O(N), хотя проходил и квадрат.

155B - Комбинация

Заметим, что мы всегда можем сперва сыграть все карты с b_i > 0, т.к. каждая из них дает хотя бы один дополнительный ход. Количество оставшихся дополнительных ходов после этого не зависит от порядка их отыгрыша. После этого у всех оставшихся карт b_i = 0, и из них надо играть те, у которых максимально a_i. Простой вариант того же решения: отсортировать все карты по убыванию b_i, а при равенстве — по убыванию a_i, а затем идти от начала к концу, моделировать счетчик оставшихся ходов и суммировать очки. При этом надо не вылететь за границу массива, если дополнительных ходов больше, чем карт. Сложность — (или O(n²), если сортировать пузырьком, что тоже проходило).

155C - Домашнее задание

154A - Домашнее задание

Без ограничения на то, что каждая буква входит не более, чем в одну запрещенную пару, задача становится гораздо сложнее, а в таком варианте работает жадность.

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

Все это можно посчитать за O(kN) k проходами по строке.

155D - Коллайдеры

154B - Коллайдеры

Здесь тупое решение <<поддерживать список/массив включенных коллайдеров и каждый раз пробегаться и считать все НОДы>> не пройдет по времени, т.к. можно включить в список все простые числа, которых, как известно, .

Заметим, что для каждого числа k, большего единицы, в каждый момент времени включено не более одного коллайдера с номером, который делится на k. Будем хранить массив, i-ый элемент которого содержит 0, если нет включенного коллайдера, номер которого делится на i, либо номер такого коллайдера. При запросе на включение k-ого коллайдера мы можем за перебрать все делители k, большие единицы, и проверить, что во всех элементах, соответствующих делителям, записаны нули. Тогда конфликтов нет, и можно включить коллайдер, а заодно записать во все рассмотренные ячейки число k. Если же хоть один элемент ненулевой, то в нем записан номер коллайдера, с которым мы конфликтуем, и мы можем его вывести (в этом случае включать ничего не нужно). При запросах на выключение надо просто проставить все нули в ячейках, соответствующих делителям.

Все это работает за . Можно решать и быстрее, если для каждого числа сохранить список его простых делителей и поддерживать описанный выше массив только для простых чисел. Суммарный размер списков для чисел от 1 до N — (это следует из оценки на сумму ряда по всем простым, не большим n). Значит, есть решение со сложностью , т.к. количество простых делителей k не превосходит (точная верхняя оценка — ).

155E - Профили-двойники

154C - Профили-двойники

Судя по комментариям, самая нестандартная задача. =)

Нужно в графе посчитать количество пар вершин, у которых совпадают множества соседей с точностью до самих этих вершин. Посчитать количество пар вершин, у которых множества совпадают в точности, можно, захешировав эти множества и посортировав хэши (да, хеши — это авторское решение). Как приспособить этот способ для случая, когда между вершинами есть ребро?

Заметим, что таких пар не больше, чем количество ребер, поэтому если мы знаем, как изменяется хэш при добавлении/удалении одной вершины в множество (например, используя полиномиальный хэш строки матрицы смежности графа), мы можем перебрать все ребра и проверить каждую пару напрямую. Можно и по-другому: посчитаем второй вариант хэша для каждой вершины, считая, что в каждой вершине есть петля. Тогда пара множеств будут совпадать как раз тогда, когда вершины — двойники и между ними есть ребро. После этого считаем количество пар аналогично первому случаю.

Можно было сортировать не хэши, а отсортированные списки смежности для каждой вершины. Из-за того, что их суммарный размер — 2M, это тоже могло проходить, но требовало аккуратной реализации, т.к. ограничения были большие. Сложность решения с хэшами — .

154D - Флатландское фехтование

Заметим, что если первый игрок может <<убить>> второго за один ход, то и второй из того же расположения (если бы был его ход) может убить первого, т.к. варианты ходов симметричны. Тогда, если нам разрешено стоять на месте, можно применить такую тактику: стоять и ждать, пока противник подойдет. Если он захочет нас убить, ему придется перед этим подойти на расстояние своего хода, после чего мы сразу сможем выиграть. Поэтому, если первый игрок не может выиграть в один ход (т.е. игроки изначально находятся вне зоны досягаемости друг друга), то никто не может обеспечить себе победу, т.к. противник может следовать описанной выше тактике, и в этом случае результат — ничья. Мы полностью проанализировали случай, когда a ≤ 0 ≤ b: если первый игрок может выиграть в один ход, то он выигрывает, во всех остальных случаях — ничья.

Пусть a и b одного знака. Тогда, обозначим d = x₂ - x₁. Если a ≤ b < 0, мы можем перейти к ситуации (d, a, b) = ( - d,  - b,  - a), которая аналогична текущей. Поэтому в дальнейшем 0 < a.

Итак, имеем такую игру: есть целые числа d и 0 < a ≤ b. За ход каждый из игроков может отнять от d произвольное целое число из диапазона [a;b]. Тот игрок, после хода которого d = 0, выигрывает. Если в какой-либо момент d < 0, объявляется ничья (т.к. никто уже не сможет выиграть).

Разбираем случай d > 0. Заметим, что если d mod (a + b) = 0, то у второго игрока есть симметричная стратегия: на любой ход x первого игрока он может сделать ход a + b - x, и вернуться в состояние d mod (a + b) = 0. Поскольку d уменьшается, рано или поздно второй игрок выиграет (ситуация аналогична такой же в игре, где можно брать от 1 до k спичек). Итак, если d mod (a + b) = 0, выигрывает второй игрок. Отсюда же, если d mod (a + b) , выигрывает первый игрок, т.к. он может свести игру к предыдущему случаю, предоставив второму игроку ход в проигрышной для него ситуации.

Что можно сказать про все остальные ходы? Оказывается, во всех остальных случаях получается ничья. Докажем это по индукции: пускай d = k(a + b) + l, где . Ситуация l = 0, как мы уже доказали, проигрышная, ситуации — выигрышные. Если , мы не можем сходить в проигрышную ситуацию (пользуемся предположением индукции для меньших k), но совершая ход a, попадаем в ничейную позицию (если k = 0, мы попадаем в отрицательное число, иначе в отрезок [(k - 1)(a + b) + b + 1;k(a + b) - 1], который по предположению ничейный). Аналогично для l = [b + 1;a + b - 1], ничейный ход — b.

154E - Колония на Марсе

Опять последнюю задачу никто не сдал, хотя некоторые участники подходили к этому очень близко.

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

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

Есть более простое решение, основанное на совсем другой идее. Сперва положим R очень большим, так что все точки выпуклой оболочки являются граничными. Когда мы начнем уменьшать R, точки начнут постепенно пропадать из границы фигуры. Как понять, какая точка пропадет первой? Для точки u из выпуклой оболочки обозначим ее соседей справа и слева l(u) и r(u). Из физического смысла процесса ясно, что первой пропадет та точка u, у которой радиус окружности, проходящей через u, l(u) и r(u) максимален (когда R станет равным этому радиусу, в точке u две дуги сольются в одну, а во всех остальных точках еще будут изломы; такой радиус назовем <<критическим>> для u). После этого удалим точку u из оболочки и будем считать вершины соседними, уже не учитывая ее. Процедуру будем повторять, пока максимальный радиус больше R. Оставшиеся точки как раз и будут точками границы.

Осталось придумать, как делать все это быстро. Заметим, что при удалении точки <<критические>> радиусы окружностей изменяются только для двух соседних с удаляемой. Заведем теперь очередь с приоритетом и будем хранить в ней критические радиусы вместе с номерами точек. На каждой итерации мы извлекаем точку с максимальным радиусом, удаляем ее из оболочки, обновляя информацию о соседях, пересчитываем радиусы для бывших соседей удаленной точки и изменяем информацию о них в очереди. Повторять, пока максимальный радиус не станет меньше R. Опять-таки, поскольку мы фактически моделируем происходящие при уменьшении R процессы, все будет работать корректно. Сложность всего процесса — O(n log n), т.к. итераций не более n и на каждой выполняется константное число операций с очередью размера не более n.

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