Первое, на что я обратил внимание, что финальная позиция — это одна из позиций в исходном маасиве. Почему? Потому, что если это не так, и финальная позиция оказалась в точке $$$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$$$