Попробуйте посмотреть в сторону крайних элементов (с индексами $$$0$$$ и $$$n-1$$$) и в сторону экстремальных (очень больших или очень маленьких

Давайте посмотрим на последний элемент. Что будет, если он очень большой по сравнению с остальными? Наверняка мы могли бы его "протащить" операциями усреднения до начала массива. Что я имею в виду:

Пусть $$$a_{n-1} = INF$$$ — очень большое число, невероятно более большое, чем $$$a_i$$$. Тогда давайте усредним $$$a_{n-2}$$$ и $$$a_{n-1}$$$, после чего оба этих числа будут порядка $$$\frac{INF}{2}$$$ (я намеренно игнорирую $$$\frac{a_{n-2}}{2}$$$, так как мы договорились, что $$$INF$$$ сильно больше $$$a_i$$$. Дальше усредним $$$a_{n-2}$$$ и $$$a_{n-3}$$$, оба этих числа станут $$$\frac{INF}{4}$$$. Продолжим так делать, пока не дойдём до самого начала, где оба числа станут порядка $$$\frac{INF}{2^{n-1}}$$$. Так как у каждого числа, кроме второго, слагаемое с $$$INF$$$ в 2 раза больше, чем у предшественника, а второе числа равно первому, то этот массив неубывающий, а значит ответ "Да"

В рассуждении выше использовалось то, что $$$INF$$$ бесконечно большой. По скромным оценкам, он должен быть хотя бы $$$2 ^ n \cdot \max\limits_{i=0}^{n-2} a_i$$$, что невероятно много для ограничений задачи.

Вот если бы числа $$$a_0, \ldots, a_{n-2}$$$ были бы равны нулю, нам бы хватило любого положительного числа $$$a_{n-1}$$$.

Теперь вопрос к читателю, а если мы ослабим условие и положим, что числа $$$a_0, \ldots, a_{n-2}$$$ равны между собой, то какого $$$a_{n-1}$$$ достаточно, чтобы упорядочить массив?

Несложно увидеть, что "все числа равны" и "все числа равны нулю" — это по своей сути одинаковые утверждения, потому что если мы вычтем из всех чисел некоторый $$$x$$$ до начала операций, то в итоге получится тот же массив, уменьшенный на $$$x$$$, потому что операция усреднения линейна относительно увеличения обоих аргументов на одно и то же число. Иными словами, операции с массивом $$$x, x, \ldots, x, a_{n-1}$$$ эквивалентны операциям с $$$0, 0, \ldots, 0, a_{n-1} - x$$$ и коль скоро $$$a_{n-1} - x \gt 0$$$, наш метод "протаcкивания" большего числа упорядочит массив

К сожалению, не во всех входных массивах так много одинаковых чисел. Можно ли решить эту проблему операциями усреднения?

К сожалению, не во всех входных массивах так много одинаковых чисел. Можно ли решить эту проблему операциями усреднения?

Оказывается, что да! Мы можем все числа сделать почти равными друг другу на любом отрезке операциями усреднения. Это означает, что если $$$mean$$$ — то среднее чисел на отрезке $$$[l, r)$$$, то для любого заранее выбранного $$$eps$$$ мы можем совершить такие операции усреднения, чтобы $$$\forall i \in [l, r) |a_i - mean| \lt eps$$$, то есть чтобы они все одновременно были близки к своему среднему с любой заранее заданной точностью

Полное и строгое доказательство этого факта я не буду приводить, но можно в этом убедиться, поняв, что для отрезка из 3 элементов это верно, а дальше применитьм етод математической индукции, чтобы доказать для отрезка любой длины

Утверждение выше даёт нам возможность утверждать более сильное условие на $$$a_{n-1}$$$, вне зависимости от конкретной структуры чисел перед ним. Сформулируйте его

Пускай $$$mean$$$ — среднее среди чисел $$$a_0, a_1, \ldots, a_{n-2}$$$, тогда если $$$a_{n-1} \gt mean$$$, то ответ "Да".

Замечание: Критически важно, чтобы знак был строгим

Как же достигать отсортированного массива? Давайте сначала усредним префикс длины $$$n-1$$$ так, чтобы $$$|a_i-mean|$$$ был меньше $$$\frac{a_n-mean}{2^n}$$$. Так как это положительное число, мы можем так сделать. Дальше вычтем $$$mean$$$ из всех чисел и окажется, что последнее число огромное по сравнению со всеми остальными, а такую задачу мы уже умеем решать

Мы рассмотрели выше только последнее число. Теперь попробуйте посмотреть на первое число

Конечно, есть ещё похожий случай, в котором ответ всегда "Да". Это случай, когда первое число очень маленькое, а именно — когда оно строго меньше, чем среднее чисел $$$a_1, a_2, \ldots, a_{n-1}$$$

Действительно, мы умеем упорядочивать массив и в таком случае. Давайте усредним все числа, кроме самого первого, чтобы все они отличались от среднего в $$$2^n$$$ раз меньше, чем разность между средним и $$$a_0$$$. Тогда теперь усреднением $$$a_0, a_1$$$, затем $$$a_1, a_2$$$ и так далее до $$$a_{n-2}, a_{n-1}$$$ мы получим отсортированный массив, похожим "протаскиванием", но только маленького числа

Кажется, что эти два случая — лишь частное какого-то более общего правила, хотя бы потому что крайние числа выделяются. Например, если предпоследнее число очень большое — ответ тоже должен быть "Да". Попробуйте обощить эти два случая и получить ещё больше вариантов, где ответ "Да"

Ранее мы усредняли только первые или последние $$$n-1$$$ чисел. Чтобы обобить этот подход, давайте усредним произвольное количество чисел в начале и в конце

Пускай есть такое $$$t$$$, что среднее на полуинтервале $$$[0, t)$$$ меньше, чем среднее на полуинтервале $$$[t, n)$$$. Тогда мы можем усреднить числа на этих полуинтервалах достаточно точно, чтобы провернуть аналогичное протаскивание:

Сделаем усреднение $$$t-1, t$$$, после чего усредним все пары на левом полуинтервале, справа налево и все пары на правом полуинтервале, слева направо. Для некоторой достаточной точности эти полуинтервалы будут неубывающими. Более того, число $$$a_{t-1}$$$ будет не больше, чем $$$a_{t}$$$, так что в итоге полученный массив будет неубывающим, а значит мы получили следующее:

Если для какого-то $$$t$$$ среднее на полуинтервале $$$[0, t)$$$ строго меньше, чем среднее на $$$[t, n)$$$, то ответ всегда "Да"

Конечно, нет. Если массив изначально состоит из равных чисел, то ответ "Да", хотя все средние равны на любых двух отрезках. Поэтому нужно думать дальше

Давайте попробуем упростить условие для "Да", которое мы вывели

Обозначьте за $$$A_{i}$$$ сумму первых $$$i$$$ чисел и попробуйте его упростить

Условие выглядит так, что левое среднее меньше правого среднего. То есть $$$\frac{A_i}{i} \lt \frac{A_n-A_i}{n - i}$$$. Давайте домножим на знаменатель и раскроем скобки

$$$A_i \cdot n - A_i \cdot i \lt A_n \cdot i - A_i \cdot i$$$ и после упрощений $$$A_i \cdot n \lt A_n \cdot i$$$ то есть $$$\frac{A_i}{i} \lt \frac{A_n}{n}$$$. Простым языком — среднее на префиксе меньше среднего во всём массиве. Даже логично, что это эквивалентно первому условию

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

Подумайте теперь вот о чём: изначально все средние на префиксах не меньше глобального среднего. Может ли тогда хотя бы одно из них стать больше в результате усреднений?

Предположим, что могут. Тогда рассмотрите усреднение, после которого впервые одно из средних стало меньше

Пускай это было усреднение между $$$i$$$ и $$$i+1$$$, тогда все средние до $$$i-1$$$ и после $$$i+1$$$ не изменились, ведь сумма на этих префиксах осталась та же. То есть, что-то могло произойти только с средним на префиксе длины $$$i$$$

Поймём что именно — раньше сумма была $$$A_i$$$, а теперь $$$A_{i-1} + \frac{a_i + a_{i + 1}}{2}$$$. Если присмотреться, она равна $$$\frac{A_{i-1} + A_{i+1}}{2}$$$, то есть сумма на префиксе стала средним между двумя соседними суммами. А среднее стало средне взвешенным между ними, то есть

$$$\frac{A_{i-1} + A_{i+1}}{2 \cdot i} = \frac{i - 1}{2 \cdot i} \cdot \frac{A_{i-1}}{i-1} + \frac{i + 1}{2 \cdot i} \cdot \frac{A_{i+1}}{i+1}$$$

Но до этого момента все средние на префиксах были не меньше среднего во всём массиве. Тогда и новое среднее не меньше. А значит, нового меньшего среднего появиться не могло

Теперь нужно сделать последний шаг — связать среднее на префиксах с ответом на задачу

Какой вид имеют средние на префиксах для отсортированного по неубыванию массива?

Ответ прост — средние тоже не убывают. А значит, если мы достигли требуемой сортировки, то все средние на префиксах меньше либо равны глобальному среднему (что в то же время равно среднему на последнем префиксе, $$$\frac{A_n}{n}$$$). Но, если изначально они все были больше либо равны, то меньшими уже не станут. Значит они должны быть все равны

Но также дело в том, что среднее на префиксе будет равно $$$\frac{A_n}{n}$$$ только если оно изначально равно, либо оба соседа были равны (иначе в оценке выше будет строгий знак неравенства)

Замечание: В данном случае положим нулевое среднее $$$\frac{A_0}{0}$$$ равное $$$\frac{A_n}{n}$$$ из-за того, что операция усреднения для чисел $$$a_0, a_1$$$ ведёт себя согласованно с этим определением

Итого, мы можем получить нужное равенство на позиции $$$i$$$, если оно выполнено на обеих позициях $$$i-1$$$ и $$$i+1$$$. Нам нужно проверить, можно ли получить равенства на всех позициях

Это задача уровня В Div 2

Давайте выпишем $$$n + 1$$$ число, 0 или 1, где 0 означает равенство среднего на префиксе общему среднему, а 1 — неравенство. Первое и последнее числа — нули. Мы можем выбрать два нуля через одну позицию и сделать среднее между ними число нулём. Можно ли получить все нули?

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