UPD. Появился разбор задачи Е. Мы просим прощения за задержку, он получился действительно трудоемким, и, чтобы как-то загладить свою вину, мы публикуем несколько интерпретаций решения.

A. Определение лиц

Автор: Monyura

Для решения этой задачи следует перебрать все квадраты 2х2 и проверить, что переставив буквы можно получить слово "face". Это можно удобно сделать, например, отсортировав буквы квадрата в алфавитном порядке и проверив, что отсортированное множество равно "acef"(Отсортированный порядок букв слова "face").

B. Вечеринка в Looksery

Автор: Igor_Kudryashov

При любом раскладе существует такое множество людей, что, если они придут и разошлют сообщения своим контактам, то каждый сотрудник получит количество сообщений отличное от того, что указал Игорь. Покажем как построить это множество. Рассмотрим 2 случая.

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

Хотя бы одно из чисел Игоря равно нулю. Пусть он предполагает, что i-ому сотруднику достанется 0 сообщений. В этом случае добавим i-ого сотрудника в искомое множество. Он разошлет сообщения всем своим контактам и у него самого количество пришедших сообщений станет равно 1. При добавлении других сотрудников в искомое множество, количество сообщений, пришедших i-ому не уменьшится, а, значит, его можно удалить из рассмотрения. Для людей из списка контактов i-го сотрудника Игорь предсказал некоторые количества сообщений, и т.к. по одному сообщению этим людям уже пришло, из желаемых Игорем чисел нужно вычесть единицу. После этого можно перейти к той же задаче, считая что у нас имеется n - 1 сотрудников. Если оставшееся количество сотрудников равно 0, то искомое множество построено.

C. Игра чётности

Автор: olpetOdessaONU

Если n = k, то ни один ход не может быть совершен. Победитель определяется изначальной суммарной четностью количества жителей. Иначе заметим, что игрок, который делает ход последним, может гарантировать себе победу, если на момент его последнего хода остаются как четные, так и нечетные города — он просто выберет, город с какой четностью сжечь, чтобы получить нужную итоговую четность. Поэтому задача его противника — уничтожить все города какого-то одного типа. Иногда все равно какого, а иногда — нет, это зависит от имени игрока и четности k. Поэтому дальнейшее решение задачи заключается в сравнении количества ходов (n - k) / 2 «непоследнего» игрока с количествами четных и нечетных городов — хватит ли ходов, чтобы их уничтожить. Если последним ходит Станнис, то, в случае четного k, Дейнерис должна сжечь все четные либо все нечетные города. В случае нечетного k, Дейнерис следует сжечь все нечетные города. Если последней ходит Дейнерис, то, в случае четного k ее противник не имеет шансов на победу, а, в случае нечетного k, Станнис должен сжечь все четные города.

D. Признаки Хаара

Автор: Monyura

Эта задача имела сложное условие, но максимально близкое к реальности.

Один из вариантов решения задачи состоит в изучении структуры ответа. Предположим, что у нас есть ответ, т.е последовательность операций: взятие сумм на префикс-прямоугольнике и коэффициентов, на который умножается сумма. Мы можем менять порядок операций, значение признака при этом меняться не будет. Тогда отсортируем операции по правому нижнему углу прямоугольника. Будем применять операции начиная от последний к первой. Решение состоит в том, что бы не применять операции, которые не нужны и применить все те, которые мы обязаны применить. Для этого для каждого пикселя будем поддерживать коэффициент с которым он сейчас входит в значение признака. Изначально этот коэффициент равен 0. Пройдем по каждому пикселю начиная с нижнего правого угла. Если текущий коэффициент не равен  + 1 для пикселя покрытого W и  - 1 для пикселя покрытого B, то пиксель входит в значение признака с неправильным коэффициентом и нам надо его поменять, для этого используем одну операцию. Единственный способ поменять значение этого пикселя теперь, после того как все большие и по ряду и по столбцу просмотрены — это взять сумму на префикс-прямоугольнике с правым нижним углом в этом пикселе. Предположим значение коэффициента должно быть X ( + 1 или  - 1 в зависимости от цвета), а сейчас равно C. Тогда мы должны прибавить сумму на прямоугольнике с коэффициентом X - C к значению признака. Но сделав это, мы так же прибавим X - C к коэффициентам всех пикселей на префикс-прямоугольнике. Это решение может быть реализовано так, как описано за O(n²m²) или за O(nm).

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

E. Саша Круг

Авторы: Krasnokutskiy, 2222

Сложность авторского решения составляет O((n + m) * h + n * logn + m * logm), где h — максимальное(среди двух множеств) число точек выпуклой оболочки. Ниже будет доказано, что для данных ограничений имеет место более точная оценка O((n + m) * С^2 / 3 + n * logn + m * logm), где С — максимальная координата.

Существует две интерпретации решения, мы приведем обе. Для начала докажем независимую оценку на число точек выпуклой оболочки:

Пусть есть множество точек на плоскости с целочисленными неотрицательными координатами. Докажем, что количество точек в выпуклой оболочке, в которой никакие три точки не лежат на одной прямой, равно O(C^2 / 3), где C — максимальная координата.

Пусть выпуклая оболочка в порядке обхода против часовой стрелке образуется последовательностью точек P₀, P₁, …, P_n - 1. Рассмотрим последовательность векторов P₁ - P₀, P₂ - P₁, .., P_n - 1 - P_n - 2, P₀ - P_n - 1 Обозначим элемент этой последовательности V_i = P_{(i + 1)modn} - P_i. Рассмотрим такие V_i = (x_i, y_i), что 0 ≤ x_i, y_i ≤ C. т.е. вектора, лежащие в первой координатной четверти. Заметим, что эти вектора будут идти подряд в последовательности векторов всех четвертей из-за свойств выпуклой оболочки. Докажем, что их количество равно O(C^2 / 3), а доказательство для других четвертей будут аналогичны.

Ключевой факт — любая частичная сумма векторов, дает точку из выпуклой оболочки, включая сумму всех векторов. Тогда сумма по каждой координате всех векторов первой четверти не превышает C. Так же, напоминаю, что никакие три точки не лежали на одной прямой в выпуклой оболочке, а значит не существует одинаковых векторов(даже коллинеарных). Посчитаем сколько максимум можно набрать векторов из первой четверти, что бы сумма по каждой координате не превосходила C:0 ≤ sumX, sumY ≤ C. Ослабим ограничения до 0 ≤ sumX + sumY ≤ C, от этого максимальное количество векторов, очевидно, не уменьшится. Будем набирать наше множество жадно, очевидно, что сначала имеет смысл брать вектора с как можно меньшей суммой координат. Возьмем максимальное количество векторов, сумма координат которых 1 , таких векторов всего два: (0, 1), (1, 0). Добавим вектора с суммой 2: (0, 2), (1, 1), (2, 0), их всего три. В общем случаи, если сумма координат равна k, то с такой суммой существует (k + 1) различных векторов. Нам надо набирать вектора до тех пор, пока сумма координат не превзойдет C. Т.е. 1 * 2 + 2 * 3 + 3 * 4 + … + k * (k + 1) = O(C). Можно честно посчитать эту сумму, но её порядок будет O(k³). Отсюда следует, что k = O(C^1 / 3). Теперь посчитаем количество векторов, которые мы взяли: 2 + 3 + … + (k + 1) = O(k²). Таким образом максимум можно взять O(C^2 / 3) векторов в первой четверти. Во всех других четвертях оценка такая же, из-за соображений симметрии.

Теперь можно переходить к разбору решения.

Первый вариант интерпретации решения, автор Sklyack:

Назовём множества точек A и B разделимыми, если существует окружность, содержащая внутри или на границе все точки одного множества, и не содержащая ни внутри, ни на границе точек другого множества, такую окружность назовём разделяющей. Пусть для определённости точки множества A находятся внутри или на границе окружности, а B -- снаружи. Точки из A на границе разделяющей окружности допускаются, так как немного увеличив радиус, получим A строго внутри, B -- строго снаружи окружности.

Пусть A содержит хотя бы две точки. Разделяющую окружность можно сжать так, что она пройдёт через хотя бы две точки из A. Можно перебрать все пары точек и через каждую такую пару попытаться провести разделяющую окружность. Центр искомой окружности лежит на серединном перпендикуляре отрезка pq. Обозначим точки серединного перпендикуляра как l(t), где -- параметр. Все точки, не лежащие на прямой pq, ограничивают параметр t сверху или снизу, точки на прямой pq должны лежать за пределами отрезка pq. Например, на следующем рисунке синяя точка ограничивает центр разделяющей окружности слева, а красные точки -- справа, поэтому центр должен лежать внутри отрезка cd.

Переберём все точки и проверим, что найдётся значение t, которое удовлетворяет всем ограничениям. Это даёт нам решение задачи за O((|A|² + |B|²)(|A| + |B|)).

Рассмотрим параболоид z = x² + y² и проведём произвольную не вертикальную плоскость ax + by + z = c. Пересечение параболоида и плоскости удовлетворяет уравнению ax + by + x² + y² = c, или . Если проецировать точки параболоида (x, y, x² + y²) на плоскость, , то сечение параболоида плоскостью проецируется в окружность, точки параболоида ниже плоскости проецируются во внутренние точки круга, выше плоскости -- в точки снаружи круга. Так как соответствие взаимно-однозначно, то верно и обратное: при проекции точек плоскости на парабалоид окружность проецируются в сечение параболоида плоскостью, внутренние точки -- в часть параболоида ниже секущей плоскости, внешние -- выше плоскости.

Таким образом, проекция точек на параболоид задаёт взаимно-однозначное соответствие между окружностями и плоскостями (не вертикальными), а для разделения множеств A и B точек плоскости окружностью достаточно разделить их трёхмерные проекции на параболоид A′ и B′ не вертикальной плоскостью. Такую плоскость назовём разделяющей (при этом по аналогии с разделяющей окружностью, разделяющая плоскость может содержать точки из A′).

По аналогии с разделяющей окружностью, разделяющую плоскость можно провести через две точки множества A′. При этом остальные точки A′ будут лежать ниже или на плоскости. Другими словами, разделяющая плоскость пройдёт через ребро верхней выпуклой оболочки множества A′. При проекции рёбер верхней выпуклой оболочки A′ на плоскость xOy получится некоторое разбиение плоской выпуклой оболочки множества A непересекающимися рёбрами, а разделяющей плоскости соответствует разделяющая окружность, проходящая через ребро разбиения. Обозначим выпуклую оболочку A как coA. В случае, когда никакие 4 вершины coA не лежат на одной окружности, все грани верхней выпуклой оболочки -- треугольники, а полученное разбиение -- триангуляция. В противном случае, достроим полученное разбиение до триангуляции.

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

Полученная триангуляция характеризуется следующим свойством: окружность, описанная около любого треугольника, содержит весь многоугольник coA, так как соответствующая грань трёхмерной выпуклой оболочки проходит выше, чем все трёхмерные точки A′. Эта триангуляция "противоположна" триангуляции Делоне, в которой окружность, описанная около любого треугольника, не содержит внутри других точек исходного множества. Её можно назвать триангуляцией Анти-Делоне, вроде бы такой термин где-то используется.

Используя характеризующее свойство, триангуляцию Анти-Делоне можно построить методом "разделяй и властвуй" без перехода в трёхмерное пространство, работая только с точками плоскости и окружностями. Пусть мы триангулируем многоугольник, образованный вершинами coA при обходе против часовой стрелки с i-й по j-ю. Найдём третью точку треугольника, в который войдет ребро (i, j), то есть такую точку k, что окружность, описанная около треугольника (i, j, k), содержит текущий многоугольник. Для этого переберём вершины текущего многоугольника и выберем ту, которая даёт крайнее положение центра описанной окружности на серединном перпендикуляре ребра (i, j). Окружность будет содержать весь многоугольник coA, так как ребро (i, j) входит в триангуляцию Анти-Делоне. Рекурсивно триангулируем многоугольники с вершинами с i-й по k-ю и с k-й по j-ю. База рекурсии -- отрезок, его триангулировать не нужно.

Для решения исходной задачи следуют поменять множества A и B ролями и ещё раз применить описанный алгоритм. Вычислительная сложность решения составляет O(|A|log|A| + |coA|(|coA| + |B|) + |B|log|B| + |coB|(|coB| + |A|)=, где C — максимальное абсолютное значение координат заданных точек.

Вторая интерпретация, автор 2222:

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

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

Обозначим множество вершин выпуклой оболочки множества A как CH(A), тогда один из вариантов решения задачи — перебрать пары точек из CH(A) и попытаться провести через них окружность, которая содержит все точки CH(A) (а следовательно, и все точки A), а все точки из B лежат снаружи, или на границе окружности. Обозначим пару точек из CH(A) как p и q. Так как все точки из CH(A) должны лежать внутри окружности, а все точки из B — снаружи, то каждая из этих точек задаёт некие ограничения на радиус окружности и на расположение центра окружности относительно прямой, проходящей через точки p и q. Например, на следующем рисунке, точки c, d и e — центры синей и красных окружностей. Заметим, что любая окружность с центром на отрезке cd будет содержать все синие точки, а все красные точки будут снаружи или на границе окружности.

Таким образом, мы можем проверить существует ли разделяющая окружность, проходящая через точки p и q, просто проверив вступают ли ограничения на разделяющую окружность в противоречие или нет, это можно сделать за . Cложность всего алгоритма составит . Для того, чтобы понять быстро это или нет, воспользуемся следующим фактом: , где C — максимальная по модулю координата точек из A, тогда сложность алгоритма составит O(C² + C^4 / 3|B|). Очевидно, что этот алгоритм слишком медленный, чтобы уложиться в лимит по времени.

Назовём пару точек A_i, A_j хорошей, если существует окружность, проходящая через эти точки, которая содержит в себе все точки CH(A).

\textbf{Лемма 1}. Если каждую хорошую пару точек соединить отрезком, то никакие 2 отрезка, соответствующие 4-ем различным точкам, не пересекаются.

Допустим, что это не так, тогда существуют 2 разные окружности с хордами ab и cd соответственно, такие что точки a, b, c и d лежат внутри или на границе этих окружностей.

Так как точки c и d лежат внутри окружности с хордой ab, то α + β < π, аналогично точки a и b лежат внутри другой окружности, поэтому γ + δ < π, где α, β, γ и δ углы при a, b, c и d соответственно в четырёхугольнике с вершинами в этих точках. Но так сумма углов четырёхугольника равна 2π, то получили противоречие, значит лемма 1 верна.

Пронумеруем вершины CH(A) по часовой стрелке от 1 до h, обозначим i-ую вершину CH(A) как ch_i. Построим рекурсивную процедуру нахождения всех хороших пар точек на промежутке [i..j], при условии, что пара точек (ch_i, ch_j) хорошая. Выберем на промежутке [i + 1..j - 1] такое k, что окружность проходящая через ch_i, ch_j и ch_k содержит CH(A), а следовательно пары точек (ch_i, ch_k) и (ch_j, ch_k) являются хорошими. Заметим, что такая окружность всегда существует, так как пара (ch_i, ch_j) является хорошей. Такое k можно найти за O(j - i) по аналогии с алгоритмом нахождения разделяющей окружности проходящей через 2 точки. Теперь решим задачу для [i..k] и [k..j]. Заметим, что пара точек (ch₁, ch_h) является хорошей, так как соответствующий отрезок является ребром выпуклой оболочки, поэтому для решения всей задачи, выполним данную процедуру для промежутка [1..h]. Данная рекурсивная процедура имеет сложность O(h²) и будет вызвана h - 1 раз, а значит количество хороших пар — O(h).

Финальный алгоритм выглядит следующим образом. Переберём все хорошие пары точек, для каждой пары, найдём разделяющую окружность, которая проходит через эту пару точек. Если разделяющая окружность не была найдена, то поменяем множества A и B местами и повторим процедуру. Сложность данного алгоритма составляет .

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

F. Юра и разработчики

Автор: Rubanenko

Посмотрим на следующее решение:

Пусть f(l, r) — это решения для подмассива [l, r]. Легко заметить, что f(1, n) — это ответ на поставленную задачу. Как считать f(l, r)? Пусть m — это индекс максимального элемента подмассива [l, r]. Все хорошие подмассивы могут быть разбиты на два непересекающихся множества: те, которые содержат m, и те которые его не содержат. Чтобы посчитать последние можно просто вызвать f(l, m - 1) и f(m + 1, r). Осталось посчитать количество "хороших" подмассивов, которые содержат m, другими словами, количество пар (i, j), что l ≤ i < m < j ≤ r и g(i, m - 1) + g(m + 1, j)%k = 0 (g(s, t) означает a_s + a_s + 1 + ... + a_t). Пусть s — это последовательность частичных сумм массива из условия, то есть s_i = a₁ + a₂ + ... + a_i. Для всех j нам интересно количество i, что s_j - s_i - a_m%k = 0, так что если мы переберем все возможны j, то нам интересно количество таких i, что s_i = s_j - a_m(modk) и l ≤ i < m. Имеем ряд запросов на отрезке вида "сколько есть чисел на отрезке (l, r), что они равны x". Это можно сделать за O(q + k) времени и памяти, где q — количество запросов, которые сгенерировались в ходе рекурсивного вычисления f(1, n). Авторское решение обрабатывает эти запросы в режиме оффлайн, с помощью массива подсчета.

Можно заметить, что в худшем случае мы получим O(n²) запросов, которые очевидно не дадут уложиться в ограничения. Тем не менее, мы можем выбрать, что быстрее: перебрать все возможные j или i. В обоих случаях мы получаем простую сравнимость и запрос на отрезке, описанный выше. Если идти только по меньшему отрезку, то каждый раз, как мы "проходим" по элементу w, он переходит в отрезок, который, как минимум, в два раза меньше, чем тот, которому он принадлежал до этого. Таким образом, каждый элемент окажется в отрезке единичной длины(база рекурсии) за O(log(n)) "проходов" по нему.

Сложность алгоритма O(n × log(n) + k).

G. Счастливая очередь

Авторы: 2222, MrDindows

Давайте переформулируем условие в терминах башен определенной высоты, которые будут находиться на лестнице. Тогда количество денег соответствующего человека в очереди будет равно высоте башни вместе с высотой ступеньки, на которой башня стоит. А процесс продвижения в очереди будет эквивалентен подъему одной башни на ступеньку вверх, а та, на чье место она взошла — вниз, как показано на иллюстрации. Тогда, становится очевидно, что чтобы все башни на ступеньках были отсортированы, достаточно отсортировать башни без учета высот ступенек. Итого сложность сортировки O(nlog(n)).

H. Вырожденная матрица

Автор: Igor_Kudryashov

У вырожденной матрицы строки линейно зависимы, а значит можно представить матрицу B в следующем виде:

Пусть

Положим, что элементы первой строки матрицы A являются координатами точки a₀ на двухмерной плоскости, а элементы второй строки — координатами точки a₁. Представим, что строки матрицы B также являются координатами точек b₀ и b₁. Заметим, что в этом случае прямая, проходящая через точки b₀ и b₁, также проходит через точку (0, 0).

Будем искать ответ на задачу — число d — бинарным поиском. Предположим мы зафиксировали некоторое число d₀ и хотим проверить, существует ли такая матрица B, что

В геометрической интерпретации это означает, что точка b₀ находится в квадрате, с центром в точке a₀ и длиной стороны 2·d₀, а точка b₁, соответственно, в квадрате с такой же длиной стороны и центром в a₁. Таким образом, нам нужно проверить, существует ли прямая, проходящая через точку (0, 0) и пересекающая эти квадраты. Чтобы это сделать, достаточно перебрать вершины одного квадрата, построить прямую, проходящую через выбранную вершину и центр координат и проверить, что она пересекает какую-нибудь из сторон второго квадрата. Затем нужно сделать то же самое, обменяв квадраты. В итоге, если прямая нашлась, то нужно уменьшить границу поиска, иначе расширить.