Кажется, подобного поста ещё не было, поэтому... Здесь вы можете обсуждать всё об Открытке 2021-2022 :)
Также, вы можете прочитать мои решения некоторых задач (возможно, их число — разобранных — будет постепенно увеличиваться).
Условия задач. Таблица результатов.
Пишем алгоритм за квадрат. Очевидно, если i зафиксировано — мы можем набирать нашу последовательность b жадно. Теперь перейдём от i к i+1. Если i было нашим b1, посмотрим на ближайшее число справа равное b1. Если оно дальше, чем b2, посмотрим на ближайшее от этого b1 справа, равное b2. И так далее, если сейчас bi, проверяем, что bi+1 левее bi, и если да — ищем новое bi+1 справа.
Можно создать map с позициями чисел в a для каждого значения — тогда искать ближайшее справа можно за log(n) бинпоиском.
А теперь поймём, что это не квадрат, а линия. Заметим, что после каждого шага у нас двигается вправо указатель на bi+1. А суммарный размер всех массивов с ними ⩽. Значит, работает за O(n\log(n)).
Делаем центроидную декомпозицию на 1 дереве. Перебираем центроид, а внутри вершину. Теперь для этой вершины в центроидной декомпозиции 2 дерева есть всего логарифм предков-центроидов. Переберём их — получаем (вершина; 2 центроида, через которые идут пути). И таких пар у нас n\log(n)^2. И при этом мы знаем расстояние от вершины до двух этих центроидов. Тогда длина пути (который проходит через эти 2 центроида) — просто сумма расстояний для 2 вершин-концов этого пути.
Ну и всё, просто для каждой полученной так пары центроидов сохраняем 2 вершины с минимальным расстоянием до них. И, взяв минимум сумм по всем, получаем ответ. Сложность O(n\log(n)^2), но достаточно чистый (если аккуратно написать) — я загнал на 99 баллов.
Сделаем центроидную декомпозицию в 1 дереве, переберём центроид. Теперь хотим узнать минимум из всех попарных расстояний его детей. Зафигачим сжатое дерево из них во 2 графе. У каждой вершины есть вес — её высота до центроида в 1 дереве, у каждого ребра есть длина. Надо найти минимальную пару по (вес в вершинах+вес пути) в нашем сжатом дереве. Это делается переподвешиваниями стандартно. И было бы O(n\log(n)), если бы не построение сжатого дерева.
В ней у нас лишний \log(n) от поисков LCA — но мы зафигачим спарсы, и он уйдёт. И ещё лишний \log(n) от сортировки вершин по tin/tout. Но если сохранять отсортированность при переходе в сыновей во время центроидной декомпозиции (тоже стандартно делается) — можно добиться желаемого O(n\log(n)). Но, кстати, с сортировкой за O(n\log(n)^2) всё равно быстрее :)
Ну, точнее, комбинация этих подходов — 2 массива мы пересчитываем и сохраняем отсортированными при переходе в сыновей, а 1 массив (c LCA) сортируем заново. Так у меня получалось быстрее всего — и зашло, в итоге, на 99 баллов.
Нам нужно посчитать (суммарное счастье событий, достижимых в дереве из корня, если разрешено перемещаться только по радостным событиям) по всем расстановкам значений.
То есть, сумму по всем расстановкам по всем достижимым вершинам значений в них.
То есть, сумму по всем вершинам по всем расстановкам, где они достижимы, значений в них.
Хорошо, зафиксируем вершину, узнаем сумму в ней, потом просуммируем по всем вершинам и узнаём ответ.
Заранее насчитаем значения cnt — количество радостных событий, sum — сумму значений по всем радостным событиям. А также расстояние (кол-во вершин на пути, включая саму эту вершину) от каждой вершины до корня — h_v.
Теперь, пусть мы находимся в вершине v. Чтобы она была достижима, нужно, чтобы все вершины на пути до корня (включая саму v) имели радостные события. Кол-во способов сделать это cnt\cdot(cnt-1)\cdot\ldots\cdot(cnt-h_v+1)) = \frac{cnt!}{(cnt-h_v)!} (так как порядок нам важен). В частности, если cnt < h_v — способов 0 :) Все остальные значения мы можем расставлять, как хотим, поэтому всего расстановок, где эта вершина будет достижима, есть \frac{cnt!}{(cnt-h_v)!}\cdot(n-h_v)!
И, очевидно, у a_i \geqslant 0 нет никакого преимущества над a_j \geqslant 0, поэтому, в силу симметрии можно сказать, все радостные события будут суммарно на месте v одинаковые количества раз по всем расстановкам, где она достижима. То есть, все по \frac{(cnt-1)!(n-h_v)!}{(cnt-h_v)!} раз. И итоговая нужная нам сумма в вершине v — это \frac{(cnt-1)!(n-h_v)!}{(cnt-h_v)!}\cdot sum.
Сделаем ДО c массовыми операциями. Будем хранить or, and и xor на отрезке. И, соответственно, проталкивать модификаторы or=, and= и xor=.
Будем писать ДО с дополнением до степени двойки. Тогда каждый отрезок, кроме конечного, имеет чётную длину.
Нам нужно понять, как всё пересчитывать, когда мы приходим в очередную вершину. Если это лист — как-нибудь да пересчитаем :) Хорошо, значит, не лист — отвечает за отрезок с чётной длиной.
Сначала смотрим, как пересчитывать, когда нам сверху спустили модификатор or= на x. Заметим, что or и and на отрезке сделают or= с x, а вот xor наоборот сделает and= с (не x) (потому что теперь все биты чисел, где у x есть единицы стали единицами, всего чисел чётно — xor обратится в этих битах в 0). Модификаторы пересчитаются так же.
Если спустили модификатор and= на отрезке — в целом, аналогично or=.
Остался модификатор xor= c x. Заметим, что значение xor на отрезке не изменится (ведь в чётном количестве чисел каждый бит либо у всех не изменился, либо у всех инвертировался — чётность кол-ва 1 не изменилась).
А если мы пересчитываем or — для битов, которые в x единицы надо понять, было ли число с 0 в этом бите — если да, в or после xor= этот бит 1, если нет — 0). А это узнаётся просто из and на отрезке (который у нас посчитан). В итоге, некоторой битовой магией получается пересчитать :) И с and на отрезке при xor= всё аналогично.
Формулы приводить не буду, можете сами на досуге повыводить — но общая идея ясна :)
Обозначим за row_i — сумму в i-ом столбце, и col_j — в j-ой строке.
Обозначим за M — максимальное число элементов в ответе в одной строке/столбце (очевидно, M \leqslant k).
Обозначим за изолированный тот элемент ответа, у которого нет соседних с ним по строке/столбцу других элементов ответа. В частности, значение в нём будет просто row_i+col_j-3a_{ij}.
Сначала я опишу основные идеи, которые мы будем применять в решении, а потом предложу свой вариант их склейки в 100 баллов — тут уже всё может быть сильно вариативно :)
(Правда, из-за плохих претестов моё решение, в итоге, за-WA-шилось, так что проверить оптимальность не получится — набирает только 78 баллов :(
1. Возьмём оптимальный ответ. Посмотрим на любую строчку i в нём, пусть в ней взято t > 0 клеток.
Заметим, что каждая взятая клетка вычитает из остальных (t+2)a_{ij} и прибавляет к себе (\leqslant row_i+col_j). (Если мы взяли какие-то ещё числа из того же столбца — col_j будет только уменьшаться).
Хорошо, row_i у всех одинаковое, значит, возьмём эту строчку i и заранее отсортируем все элементы в ней по col_j-(t+2)a_{ij}.
Пусть какой-то элемент не входит в первые k из них. Тогда оставшиеся k-1 элемент могут занять максимум k-1 столбец, то есть, минимум 1 элемент из этих первых k будет одинок в своём столбце.
Заменим наш элемент (не входящий в первые k) на этот. Заметим, что col_j-(t+2)a_{ij} стало, а было (\leqslant col_x-(t+2)a_{ix}), и по условию отсортированности col_x-(t+2)a_{ix} \leqslant col_j-(t+2)a_{ij}. Значит, сумма не уменьшилась, ведь всё остальное не изменилось (или увеличилось: если какие-то элементы ответа стояли в столбце x — к ним дополнительно прибавилось a_{ix}).
2. Теперь будем повторять наш алгоритм (делать замену элемента в ответе), пока можем. И, в итоге, получаем, что, если в строке ровно t элементов, для этих элементов у нас только k вариантов. Ну, то есть, существует ответ, который состоит только из этих k вариантов.
При этом t у нас от 1 до M. Значит, в строке могут подходить в качестве элементов ответа не больше Mk вариантов (первые в порядке сортировке по col_j-(t+2)a_{ij} по всем 1 \leqslant t \leqslant M).
И абсолютно аналогично в столбце. Итого, у нас уже не nm вариантов для элементов ответа, а \leqslant Mk\cdot\min(n, m) \leqslant k^2\cdot\min(n, m).
Назовём эти элементы множеством кандидатов.
3. Пусть C = (2Mk-1)(k-1)+1. Смысл поймём чуть позже.
Посмотрим на элемент из кандидатов. У каждого такого элемента по не больше Mk соседей кандидатов в строке и в столбце. Значит, если мы его возьмём, у нас обретут соседа не больше 2Mk-1 элементов-кандидатов (включая его самого).
Теперь посмотрим на первые C элементов в порядке сортировки кандидатов по row_i+col_j-3a_{ij}. Пусть в ответе есть элемент, не входящий в них. Тогда каждый из k-1 остальных элементов ответа имеет соседями по не больше 2Mk-1 элементов. И остаётся хотя бы 1 изолированный из этих C первых.
Заменим наш (не входящий в первые C) элемент на этот изолированный. Заметим, что сумма не уменьшилась, так как наш элемент давал в сумму \leqslant row_x+row_y-3a_{xy} (с дополнительными вычитаниями, если был с кем-то в одной строке/столбце), что из отсортированности \leqslant row_i+row_j-3a_{ij} (без вычетаний по определению изолированности).
4. Отлично, будем повторять это, пока можем. В итоге, аналогично 2 пункту, получим, что существует ответ, где все элементы его принадлежат этим C первым элементам, базово просто (2k^2-1)(k-1)+1 элементам.
Это теперь наше новое множество кандидатов.
5. Пусть мы уже перебрали t вершин, которые мы считаем, что входят в ответ. Поставим в эти клетки 0 и будем поддерживать актуальные row_i и col_j. Также для каждой строки/столбца будем считать кол-во уже взятых элементов в них — numrow_i и numcol_j.
Теперь, если мы взяли в ответ ещё и элемент a_{ij}, мы должны дополнительно вычесть (numrow_i+numcol_j)a_{ij}, потому что он вычитается из значения всех уже взятых элементов, находящихся с ним в 1 строке/столбце.
6. Учитывая всё выше сказанное, мы можем, например, перебрать какие-то t элементов, какие мы уже взяли — и у нас останется взять k-t элементов — пересчитаем множество кандидатов, и их станет уже C = (2M(k-t)-1)(k-t-1)+1. И дальше мы можем запускаться рекурсивно :)
Чтобы достаточно быстро пересчитывать кандидатов, заметим, что это, очевидно, подмножество кандидатов, которые были у нас на прошлом шаге.
7. Заметим, что, когда мы перебрали какой-то элемент, будто он входит в ответ, и перешли к следующему — можно считать, что предыдущий элемент уже не входит в ответ (иначе мы перебрали бы этот вариант раньше). Поставим соответствующую метку.
А дальше, когда мы уже насчитали следующее множество кандидатов, мы можем просто удалить из него все помеченные элементы. Это делит наше решение на t!, если верить, что элементы переходят в следующее множество кандидатов достаточно равномерно (где t — число уже взятых элементов), так как из всех их перестановок мы учтём только 1. В любом случае, ускоряет :)
Теперь пошла уже моя склейка этих идей, по идее, приводящая нас к успеху (если нигде не набагать :)
Будем перебирать по убыванию, начиная с k, максимальное кол-во элементов в 1 строке/столбце. Обозначим его на текущем шаге за M (собственно, это и есть M по определению). И число кандидатов C будет уменьшаться с уменьшением M.
Заметим, что тогда соответствующих кандидатов-строк (на линию с M элементами) будет не больше, чем \min(n, \frac CM) — ведь в кандидате-строке, очевидно, должно быть минимум M кандидатов-элементов. И аналогично со столбцами.
Теперь переберём строку/столбец из кандидатов. По нашему предположению в ней ровно M элементов взято, но тогда из 1 пункта для них у нас есть только k вариантов (а не Mk, как может показаться изначально). Для каждой линии-кандидата, если в ней всего t \leqslant k элементов кандидатов, мы можем выбрать M из них C_t^M способами.
Оставшиеся k-M элементов выберем в тупую рекурсивно (каждый раз пересчитываем кандидатов и выбираем элемент из них — и с помощью меток оно ещё делится на (k-M)! примерно).
Если аккуратно посчитать число операций (или потестить решение) — можно понять, что для M \geqslant 3 мы выбираем из остальных \leqslant 3 элемента, и это работает достаточно быстро. Остался случай, когда M \leqslant 2.
Пусть мы уже взяли некоторое множество элементов в ответ. Теперь есть 2 варианта — все оставшиеся a_{ij} в ответе изолированные, или есть хотя бы 1 пара в 1 строке/столбце.
Если все вершины изолированные — понимаем, что M = 1. То есть, при текущем k кандидатов C = (2k-1)(k-1)+1 (у нас сейчас k — кол-во элементов, которые ещё нужно взять в ответ). Также используем метки времени.
Если аккуратно всё посчитать (или опять-таки потестить) — понимаем, что наше рекурсивное решение выше снова работает вполне быстро (даже если изначально все a_{ij} в ответе изолированные).
Хорошо, а если у нас есть пара вершин в 1 строке/столбце — просто запустим наше решение с перебором максимальной по кол-ву элементов в ответе строки рекурсивно :)
Как мы помним, строк-кандидатов \min(n, C/2) — так как M = 2. И аналогично C = (4k-1)(k-1)+1. Мы выбираем из каждой C_k^2 варианта максимум. Со столбцами аналогично. А затем из k вычитается 2 — глубина не больше 3 будет. Короче, в целом, и если посчитать, и если запустить — тоже срабатывает :)
Только важно понимать, что если мы не взяли элемент в кандидаты на пару — он всё ещё может войти в изолированные вершины. Поэтому метки для них должны быть раздельные.
И да, понятное дело, что я опустил ещё некоторые оптимизации, какие-то левые идеи — думаю, из данного базиса фактов можно собрать под сотню разных работающих решений. Хотя на самой олимпиаде, как мы видим, получилось только 1 :) Так что, дерзайте!
Попробуем найти критерий того, что наш отрезок является полезным.
Во-первых, разделим его на блоки одинаковых символов — например, s = abbcbbbxx перейдёт в abcbx, состоящую из 5 блоков. Дальше, если в нашем отрезке чётное число блоков — он, очевидно, является полезным (просто разделим его на пары соседних).
Хорошо, иначе (при нечётном числе блоков) докажем, что отрезок является хорошим \Longleftrightarrow в нём есть либо блок на чётном месте из >1 символа, либо последовательная тройка блоков вида aba, также начинающаяся с чётного места (нумерацию будем вести с 1). В частности, отрезки abbxyz и abcdcag являются полезными, а вот bcaatc или bbcdca — нет.
По индукции. Если весь отрезок состоит из 1 блока — не интересно :)
Иначе заметим, что мы обязаны взять весь 1 блок в 1 гармоничный кусок целиком. Теперь, если длина 2-го блока >1 — возьмём из него в 1 гармоничный кусок только 1 символ: условие на гармоничность соблюдается и кол-во блоков в оставшемся куске будет чётно — мы победили, отрезок был полезный :)
Если же длина 2-го блока 1 — нам также придётся взять его в 1 гармоничный кусок целиком. Теперь, если 3 блок совпадает с 1 — возьмём его в этот кусок тоже. И условие на гармоничность опять-таки соблюдается, а кол-во блоков в оставшемся куске опять-таки чётно (возможно, 0) — и мы снова победили :)
А если 3 блок не совпадает с 1 — взяв первые 2 блока в 1 гармоничный кусок мы обязаны на этом его закончить. И остался кусок ткани с кол-вом блоков на 2 меньше — но для него уже работает предположение индукции. И \Longleftrightarrow доказали (для отрезков с нечётным числом блоков :)
Ок, а поэтому давайте идти по блокам справа налево и считать кол-во полезных отрезков, начинающихся в текущем. И сделаем отдельно для отрезков, начинающихся в чётных с начала массива блоках, и для отдельно отрезков, начинающихся в нечётных.
Будем поддерживать самое левое из (стоящих на чётных местах с начала) вхождений блоков с >1 элементами и троек блоков вида aba. Тогда до этого вхождения подходят только подотрезки с чётным числом блоков, а после — вообще все (мы смотрим на местоположение конца подотрезка). Ну и будем поддерживать суммарное число элементов в подотрезках с чётным числом блоков до вхождения.
Пересчёт делается несложно — у нас добавляются 2 блока в начало, если у 2-го >1 элемента, или первые 3 теперь имеют вид aba — у нас новое самое левое вхождение. И присвоим счётчику суммарного числа элементов размер 2-го из этих блоков (а после него будут подходить уже все).
Иначе же просто к счётчику опять-таки прибавляется размер 2-го из этих блоков (то есть, 1), и процесс продолжается :)
Итого — сложность решения O(n), но писать не слишком приятно.
Делаем бинпоиск по ответу. Если мы ищем 2 касающиеся окружности радиуса r без ёлок внутри — это то же самое, что искать отрезок длины 2r, с концами не внутри окружностей радиуса r, надутых из каждой ёлки (ну, и не вне прямоугольника со сторонами, урезанными на r).
Ниже идёт лирическое отступление, можно сказать так: Заметим, что для заданного радиуса r можно проверять только отрезки вида (точка на пересечении 2 объектов — точка на объекте (сторона/окружность)). Но тогда это будет кукарек :)
Пусть отрезок такой есть. Будем его двигать влево, пока он не коснётся вершиной окружности/стороны. Теперь начнём поднимать его вверх (двигая по этой стороне/окружности), пока можем. Если он на верхней точке — убираем с объекта, продолжая двигать влево. Иначе он либо встал 1 вершиной на пересечении 2 объектов, либо стал каждой вершиной на какой-то объект (возможно, совпадающие).
Если он каждой вершиной на каком-то объекте — продолжим двигать отрезок. Можно представлять, что мы двигаем окружность радиуса 2r по объекту. И вторая точка находится на пересечении её объекта и этой окружности. Если пересечения нет — отлично, мы "снялись" с того объекта, продолжаем алгоритм.
Хорошо, значит, когда наш мысленный алгоритм завершится, у нас будет вершина на пересечении 2 объектов. Окей, начнём двигать 2 вершину по окружности радиуса 2r, с центром в нашей точке. Она остановится, когда попадёт на какой-то объект (сторону/окружность). Заметим, что диаметральная точка нашей окружности 1 точки (или точка нашей стороны на расстоянии 2r), в частности подходят (если не принадлежат другим объектам, на которые мы натолкнёмся раньше.
Отлично, мы доказали мысленным алгоритмом, что, если существует такой отрезок длины 2r, то существует отрезок, у которого 1 точка на пересечении 2 объектов (окружностей/прямых), а вторая ещё на каком-то. Причём, если мы зафиксируем объекты, 1 точка получается с точностью до 2 и 2 точка тоже — пересечение окружности радиуса 2r с центром в 1 точке и того объекта.
Продолжение решения.
Теперь переберём все варианты, проверка, что отрезок подходит втупую за O(n) — проверяем все окружности, что точка не лежит в них. Есть решение за O(n^4\log(C)) — заходит на 52 балла.
Теперь единственный кукарек. Заметим, что точек вида (пересечение 2 объектов), которые не лежат внутри другого объекта (а нам подходят в качестве центра НЛО только такие) порядка O(n). Сразу получаем сложность O(n^3\log(C)), которая набирает 66 баллов.
Теперь хотим за быстро проверять, что точка не принадлежит окружностям. Тогда получим решение за O(n^2\log(C)\cdot check) — так как сначала перебираем пересечение, проверяем, что оно хорошее — и уже для O(n) оставшихся вариантов перебираем объект, на котором второй центр.
Хорошо, точки для проверки лежат хотя бы на 1 из окружностей, которые у нас есть (с центрами в ёлках радиуса r) или сторон прямоугольника. Надо для каждой окружности насчитать, какие точки хорошие, а какие — нет.
Просто переберём другие объекты, посчитаем пересечениями, какие отрезки плохие (лежат внутри второго объекта), теперь отсортируем, и оставим отрезки, которых тут нет. Можно сделать сканлайном легко. (Для окружностей удобно разделить всё на верхние точки и нижние, и делать всё независимо — тогда нужна только x-координата для проверки, что точка хорошая).
И теперь просто бинпоиском для точки проверяем, принадлежит ли она хорошему отрезку. Получаем сложность решения O(n^2\log(C)\log(n)), если верить в кукарек. И я смог загнать это на 100 баллов :)