Проверьте число лжецов независимо.

Как проверить, что лжецов ровно $$$x$$$?

Как решать задачу для $$$n = 2$$$?

Как решать задачу для $$$n = 4$$$?

Каким свойством обладает число опций, присутствующее в бесконечном числе раундов?

Выберете самое маленькое такое число.

Как это число и число $$$m$$$ относятся к ответу?

Что мы можем сказать про позиции максимумов, относительно отрезка $$$[l, r]$$$?

Мы можем использовать ДП или:
Проитерируемся по среднему максимум и выберем отрезок $$$[l, r]$$$ жадно.

Что можно сказать про двух моделей, которые выходят друг за другом во время шоу?

Если вы смогли посчитать отношение "модель $$$i$$$ может выходить перед моделью $$$j$$$" каким-то образом, как посчитать ответ?

Как посчитать это отношение достаточно быстро?

Что происходит в общем случае после двух запросов?

Можем ли мы решить задачу за 3 запроса?

Как выбрать третий запрос, чтобы два кандидата не были слишком близко в проекции?

I've compiled 10000 best participations in a Div. 2 contest into a CSV file
It's funny, that I myself am mentioned 4 times and all of those are Educational Div. 2 contests
This is the python script I used to fetch this information

Первое сообщение от MikeMirzayanov я получил более года назад! Также antontrygubO_o отклонил почти 30 (29 если быть точным) задач, так что я действительно старался, чтобы предоставить этот раунд. Это было отличным опытом, я надеюсь вернуться с Div. 1 или даже Global раундом в будущем.

Какое наименьшее количество блоков необходимо, чтобы ответ был $$$\texttt{YES}$$$?

Проверьте предикат на каждом префиксе.

Давайте рассмотрим минимальное количество блоков, которое необходимо, чтобы первые $$$i$$$ высот были возрастающими. Так как высоты неотрицательные и возрастающие они должны выглядеть как $$$0, 1, 2, 3, ..., i - 1$$$, так что минимальная сумма будет $$$\frac{(i - 1) \cdot i}{2}$$$. Оказывается, что это условие достаточное. Если это не так для какого-то префикса $$$i$$$, то мы не можем сделать этот префикс возрастающим (так как суммарное число блоков на префиксе никогда не увеличивается) соответственно ответ $$$\texttt{NO}$$$, иначе ответ $$$\texttt{YES}$$$, так как мы можем двигать блоки с $$$i$$$-й позиции, пока в ней хотя бы $$$i$$$ блоков и получим возрастающие высоты.

Действительно ли задача двумерная?

Как решить задачу, если все $$$y = 0$$$?

Для начала заметим, что задача не двумерная. Если мы меняем $$$x$$$ координату точки, то сумма дистанций по $$$y$$$ не меняется совсем. Так что нам нужно посчитать количество хороших точек на линии сначала с координатами $$$x$$$, потом с $$$y$$$ и перемножить ответы.

Теперь, чтобы посчитать ответ на линии мы можем воспользоваться известным фактом: все точки с минимальным расстоянием лежат между левой и правой медианой. Так что теперь мы можем отсортировать массив и взять элементы на позициях $$$\lfloor \frac{n + 1}{2} \rfloor$$$ и $$$\lfloor \frac{n + 2}{2} \rfloor$$$ и вернуть их разность плюс один.

Бинарный поиск?

Как проверить, находится максимум в правой или левой половине массива за два запроса?

Давайте решать для какого-то подотрезка $$$[l, r)$$$ и $$$mid = (l + r) / 2$$$. Теперь давайте проверим лежит ли максимальный ответ в $$$[l, mid)$$$ или $$$[mid, r)$$$. Давайте найдем второй максимум в $$$[l, r)$$$ и назовем его $$$smax$$$. Теперь представим, что $$$smax$$$ меньше $$$mid$$$ (из соображений симметрии). Теперь если мы спросим $$$[l, mid)$$$ и ответ все еще $$$smax$$$, то максимальный элемент лежит в $$$[l, mid)$$$, иначе он лежит в $$$[mid, r)$$$. Так мы уменьшили отрезок поиска в два раза. Так что результирующее число запросов будет $$$2 \cdot \lceil log_2 10^5 \rceil = 34$$$.

Опять бинарный поиск?

Как решать задачу, если второй максимум находится на первой позиции?

Как узнать находится максимум справа или слева от второго максимума за два запроса?

Найдем второй максимум $$$smax$$$. Теперь проверим лежит ли максимум слева, или справа от $$$smax$$$. Для этого просто спросим $$$[1, smax]$$$ и посмотрим, равен ли ответ $$$smax$$$. Теперь предположим, что максимум оказался справа от $$$smax$$$ (по соображениям симметрии). Тогда нам всего лишь нужно найти минимальный $$$m$$$, такой что на запросе $$$[smax, m]$$$ ответ равен $$$smax$$$. Наименьшее такое $$$m$$$ и будет позицией максимального элемента. Соответственно, мы можем использовать бинпоиск, чтобы найти эту позицию. Суммарное количество запросов получается $$$2 + \lceil log_2 10^5 \rceil = 19$$$.

Как решать задачу, если все значения $$$-1$$$ и $$$1$$$?

ОПЯТЬ бинарный поиск?

Как проверить, что ответ хотя бы $$$x$$$?

Давайте сделаем бинарный поиск по ответу. Теперь проверим, что ответ хотя бы $$$x$$$. Заменим все элементы большие или равные $$$x$$$ на $$$1$$$, а элементы меньшие $$$x$$$ на $$$-1$$$. Теперь если для какого-то подотрезка медиана хотя бы $$$x$$$, то сумма на этом подотрезке положительна! Теперь нам нужно лишь проверить, что существует подотрезок в массиве состоящем из $$$-1$$$ и $$$1$$$ длины хотя бы $$$k$$$ с положительной суммой. Для этого просто посчитаем префиксные суммы и для каждого префикса $$$i$$$ выберем префикс с минимальной суммой из позиций $$$0, 1, ..., i - k$$$, что можно сделать при помощи префиксного минимума за линейное время.

Получаем асимптотику $$$O(nlogn)$$$.

Вы же прочитали, что $$$w$$$ не больше $$$50$$$?

Как нужно изменить граф, чтобы алгоритм дейкстры работал по данному правилу?

Добавьте в граф фейковых вершин и ребер, чтобы все заработало.

Давайте думать о задаче в таком ключе. Для центральной вершины нам важны лишь веса ребер, через которые мы проходим. Так что давайте для каждой вершины $$$v$$$ создадим фейковые вершины $$$(v, w)$$$, где $$$w$$$ — вес последнего ребра по которому мы прошли. Это добавит не более $$$O(M)$$$ вершин в наш граф. Теперь для каждого ребра $$$(u, v, w)$$$ в изначальном графе создадим ребро $$$u \rightarrow (v, w)$$$ веса $$$0$$$. Также для каждой вершины $$$(u, was)$$$ и ребра $$$(u, v, w)$$$ создадим ребро $$$(u, was) \rightarrow v$$$ весом $$$(was + w)^2$$$. Теперь, если запустить алгоритм Дейкстры от вершины $$$1$$$, то мы получим корректные ответы для всех вершин, так как мы просимулировали новое правило при помощи фейковых вершин и ребер. Также мы создадим не более $$$O(M \cdot maxW)$$$ ребер, так как для вершины степени $$$t$$$ мы создадим не более $$$t \cdot maxW$$$ ребер, а сумма всех $$$t$$$ равна $$$2 \cdot M$$$.

Аккуратно реализовав данный алгоритм мы получим $$$O(M \cdot maxW \cdot logM)$$$ или $$$O(M \cdot maxW + MlogM)$$$ по времени и $$$O(M \cdot maxW)$$$ или $$$O(M)$$$ памяти. Любая реализация должна была получать AC.

Подвесьте дерево за какую-нибудь вершину.

После подвешивания дерева, как выглядит вершина пересечения?

После подвешивания дерева, какие два типа пересечения существуют?

Давайте подвесим дерево за какую-нибудь вершин. Теперь вершина пересечения двух путей будет lca для хотя бы одного пути.

Теперь есть два типа пересечений: с одинаковым lca и разным lca. Давайте посчитаем их по отдельности.

Для каждого пути и его lca найдем поддеревья, в которые этот путь спускается от lca. Получим тройку $$$(lca, subtree1, subtree2)$$$ (если путь не спускается от lca, то заменим на $$$-1$$$), такую что $$$subtree1 < subtree2$$$ или они оба равны $$$-1$$$.

Теперь чтобы посчитать пересечения первого типа мы можем использовать принцип включений-исключений. Запомним все пути, которые имеют одинаковый lca. Теперь нам нужно посчитать число пар путей, таких что у них не совпадает $$$subtree1$$$ и $$$subtree2$$$ (или равен $$$-1$$$). Формула будет $$$cntpath \cdot (cntpath - 1) / 2 - \sum \left(cnt(subtree1, x) + cnt(x, subtree2) - (cnt(subtree1, subtree2) + 1) \right) / 2$$$ (по принципу включений исключений), для всех возможных $$$subtree1$$$ и $$$subtree2$$$, где $$$cntpath$$$ — число путей с данным lca, и $$$cnt(x, y)$$$ — число путей с тройкой $$$(lca, x, y)$$$. Ситуация с $$$-1$$$ примерно такая же, оставляю как упражнение читателю.

Находить пересечения второго типа заметно проще. Нам нужно лишь посчитать число пересечений путей с фиксированным lca и вертикальными путями, которые проходят через это lca (пути необязательно вертикальные, он они содержат и lca и его предка) и после этого вычесть $$$cnt(subtree1)$$$ и $$$cnt(subtree2)$$$, где $$$cnt(x)$$$ — число вертикальных путей, которые спускаются в поддерево $$$x$$$.

После этого мы должны всего-лишь вывести сумму этих чисел. Чтобы посчитать все необходимые функции можно использовать какую-нибудь структуру данных (например переливания) или динамическое программирование по поддеревьям.

Финимальная асимптотика получается $$$O(Mlog^2M)$$$ или $$$O(MlogM)$$$ или даже $$$O(M)$$$, если вы достаточно сильны.

Сегодня я мирно писал виртуальное соревнование Codeforces Round 381 (Div. 1). После решения AB у меня было примерное 30 минут на остальные задачи (не много, учитывая, что сложность C 2500). Но после прочтения C я сразу понял, что это стандартная задача на дерево отрезков, вся суть в реализации. После около полутора часов я написал рабочее решение, которое проходило претесты и валилось на тесте 4. После запуска программы на примерно 20000 случайных тестов я начал заподозривать неладное.