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

Следующее, на что я обратил внимание -- это ограничения задачи, они позволяют перебрать точку $$$x=a_j$$$ и посчитать для нее ответ.

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

1. $$$a_i=x$$$, пусть их $$$M$$$
2. $$$a_i \lt x$$$, пусть их $$$L$$$
3. $$$a_i \gt x$$$, пусть их $$$R$$$ Тогда как посчитать ответ?

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

Тем парам людей, которые находятся в одной группе. Еще если мы позвоним людям из разных групп, то мы всегда можем назначить точку $$$x$$$. Тогда чему равен ответ?

Ответ равен $$$\max(L, R)$$$

Пусть мы знаем ответ $$$h$$$ для префикса $$$0\ldots i$$$. Как нам проверить, правильный ли он или нет? Какие есть условия?

Самое простое условие -- это $$$a_0 \ge h$$$, тогда мы можем к себе в запас положить $$$a_0-h$$$ лишней глазури. Какое будет условие для $$$a_1$$$?

Условие такое: $$$a_1 + (a_0-h) \ge h$$$. Так как мы можем сложить глазурь $$$a_1$$$ и остатки глазури с прошлого шага $$$a_0-h$$$. Перепишем это условие: (a_0+a_1) \ge 2h. Тогда у нас останется $$$(a_0+a_1)-2h$$$ лишней глазури. Тогда какое условие в общем виде для префикса $$$i$$$?

Такое: $$$a_0+a_1+\ldots+a_i\ge (i+1)h$$$. Тогда получается, что $$$h \le \frac{A_i}{i+1}$$$, где $$$A_i$$$ — префиксная сумма массива $$$a: A_i=A_{i-1}+a_i$$$.

Первое, на что я обратил внимание -- это ограничения задачи, которые позволяют ее решать за, например, $$$O(n^2)$$$. То есть мы можем что-то перебрать, а потом при фиксированном чем-то можем сделать еще что-нибудь за $$$O(n)$$$. Какую простую версию задачи можно решить?

Представим, что у нас нет людей типа A, тогда есть только I и E. Тогда как решить такую подзадачу?

Чтобы решить эту подзадачу, мы должны просто идти слева направо по строке. Если встретили I, то сажаем его за новый столик (если столики остались), а если E — то сажаем его за неполный столик с хотя бы одним человек (если такой есть). Хорошо, теперь вернем A. По сути, A — это либо I, либо E. Пусть мы знаем, сколько из A людей перекрасятся в I, тогда как нам выгодно их красить?

Нам выгодно перекрашивать некоторый префикс людей типа A в тип I, потому что мы хотим, чтобы на момент рассмторения I было как можно больше свободных столов, а на момент рассмотрения E, было как можно больше непустых столов. Тогда как решать всю задачу?

Перебираем, сколько людей типа A мы перекрасим в тип I (остальные будут перекрашены в тип E), перекрашиваем, проверяем за линию. Итого $$$O(n^2)$$$.

Попробуем решить жадно. Основная проблема — как работать с A. Пусть мы встретили A. Что мы можем с ним сделать?

Мы можем посадить его за пустой столик, но тогда мы заблокируем место для одного из будущих I. А если посадим его за непустой столик? Тогда мы займем место для какого-то из E. Можем ли мы как-то исправить ситуацию для I? Непонятно. А для E?

Мы можем попытаться пересадить E, который был посажен за непустой столик за новый столик, а затем посадить E. Отлично, тогда давайте хранить количество пустых столов, количество мест за непустыми столами, а также количество A, которые мы посадили за непустые столы (именно их мы можем пересаживать за пустые столы). Если встретили E или I, то решаем как обычно, а если A, то сначала пытаемся посадить его за непустой стол, а если не получилось, то пытаемся посавдить за пустой стол.

Первое, на что я обратил внимание, что если все $$$a_i=0$$$, то это задача о Ханойских Башнях. Обычно, в подобных задачах, ее решают так: рекурсивно переносят первые $$$(n-1)$$$ слоев из первого места во второе, затем переносят $$$n$$$-й слой из первого слоя в третий, а потом оставшиеся $$$(n-1)$$$ слоев переносят из второго места в третье. Но здесь бывают случаи, когда $$$a_i \gt 0$$$. Какой есть простой случай, когда ответа нет?

Когда есть $$$a_i \gt i$$$ (в 0-индексации), тогда ответа нет, потому что мы не сможем никогда переместить этот слой никуда, потому что максимальное количество слоев над ним не может быть больше $$$i$$$. Хорошо, осталось рассмотреть случай, когда $$$a_i \le i$$$. Можем ли мы по аналогии с Ханойскими башнями решить задачу?

Пусть $$$k=a_{n-1} \lt n$$$, тогда чтобы переместить последний слой, нам надо сделать так, чтобы над ним было ровно $$$k$$$ слоев. Что мы можем сделать?

Мы можем переместить $$$n-1-k$$$ первых слоев с первого места на второе. После этого на первом месте будет ровно $$$(k+1)$$$ слой, тогда мы можем переместить последний слой из первого места в третье. А что теперь?

Если $$$k=0$$$, то по аналогии с Ханойскими башнями осталось переместить оставшиеся $$$(n-1)$$$ слоев из второго места в третье. А если $$$k \gt 0$$$? В таком случае, у нас есть три места, в каждом из которых есть сколько-то слоев. Причем, во втором месте лежат самые маленькие слои.

Мы можем попытаться переместить либо слои из первого места в третье, либо из второго места в первое. Можем ли мы сделать первый вариант? Не всегда. А второй вариант? Да, можем, тогда в конце нам останется опять переместить $$$(n-1)$$$ слой из первого места в третье. Сколько тогда мы сделаем операций?

Если $$$F(n)$$$ — количество операций при перемещении префикса длины $$$n$$$, тогда $$$F(1)=1$$$, а чему равно $$$F(n)$$$?

$$$F(n) = F(n-1-k) + 1 + F(n-1-k) + F(n-1) = 2F(n-1-k)+F(n-1)+1$$$, причем, если $$$k=0$$$, то $$$F(n)=F(n-1)+1+F(n-1)=2F(n-1)+1$$$. Верно ли, что $$$F(n) \lt 2^n$$$?

Да, верно, потому что $$$F(1)=1 \lt 2^1=2$$$. Далее, если $$$k=0$$$, то $$$F(n)=2F(n-1)+1\le 2\cdot(2^{n-1}-1)+1=2^n-2 \lt 2^n$$$. И если $$$k \gt 0$$$, то $$$F(n)=2F(n-1-k)+F(n-1)+1\le 2\cdot (2^{n-1-k}-1)+2^{n-1}-1+1 \le 2\cdot (2^{n-2}-1)+2^{n-1}=2^n-2 \lt 2^n$$$

Посмотрим на самую длинную змею. Как она выглядит? Где начинается и где заканчивается?

Она начинается в самом верхнем левом углу и заканчивается в самом правом нижнем углу. Если это не так, то ее никак не уместить в поле $$$n\times n$$$.

Дальше, я смотрю на антидиагонали:

01234
12345
23456
34567
45678

Здесь каждой цифрой обозначены диагонали. Сколько раз один путь вправо-вниз может проходить по одной диагонали?

По каждой диагонали не более одного раза. Хорошо, раз мы знаем где начинается и где заканчивается самый длинный путь, то пойдем дальше, а именно расмотрим диагональ $$$1$$$. Что мы про нее знаем?

Мы знаем, что одна из клеток принадлежит самой длинной змее длины $$$2n-1$$$, а что мы можем сказать про вторую клетку?

Она принадлежит змее длины $$$2n-3$$$, потому что если нет, то мы не сможет расположить эту змею нигде больше. То есть мы нашли старт змеи $$$(2n-3)$$$, а где ее конец?

Ее конец где-то в предпоследней диагонали. Обозначим $$$X$$$ — змея длины $$$2n-1$$$, а $$$Y$$$ — змея длины $$$2n-3$$$, пусть мы знаем, что например картинка выглядит примерно так:

XX....
Y.....
.....?
....?X

Тогда как может выглядеть правый нижний угол?

Он может выглядеть только так:

XX....
Y.....
.....X
....YX

Потому что иначе две змеи пересекутся.

Продолжим процесс. Допустим, мы знаем про каждую клетку диагонали $$$i$$$, каким змеям они принадлежат. Тогда мы знаем, каким змеям принадлежат клетки симметричной диагонали (они там симметричны). Тогда мы по сути хотим итеративно найти стартовые клетки всех змеи. Они однозначно зададут все пути. Почему?

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

Тогда на каждой диагонали мы хотим найти отрезок клеток, где мы можем начать новую змею исходя из уже нарисованных путей. Пусть на диагонали $$$i$$$ отрезок имеет длину $$$L_i$$$, тогда ответ равен $$$L_0\cdot L_1\cdot \ldots \cdot L_{n-1}$$$.