Packmen Strike Back
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2500
Tags: binary search, dp, math

Game field is represented by a line of n square cells. In some cells there are packmen, in some cells there are asterisks and the rest of the cells are empty. Packmen eat asterisks.

Before the game starts you can choose a movement direction, left or right, for each packman. Once the game begins all the packmen simultaneously start moving according their directions. A packman can't change the given direction.

Once a packman enters a cell containing an asterisk, packman immediately eats the asterisk. Once the packman leaves the cell it becomes empty. Each packman moves at speed 1 cell per second. If a packman enters a border cell, the packman stops. Packmen do not interfere with the movement of other packmen; in one cell there can be any number of packmen moving in any directions.

Your task is to assign a direction to each packman so that they eat the maximal number of asterisks. If there are multiple ways to assign directions to eat the maximal number of asterisks, you should choose the way which minimizes the time to do that.

Input format:
The first line contains integer number n (2 ≤ n ≤ 1 000 000) — the number of cells in the game field.

The second line contains n characters. If the i-th character is '.', the i-th cell is empty. If the i-th character is '*', the i-th cell contains an asterisk. If the i-th character is 'P', the i-th cell contains a packman.

The field contains at least one asterisk and at least one packman.

Output format:
Print two integer numbers — the maximal number of asterisks packmen can eat and the minimal time to do it.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example the leftmost packman should move to the right, the rightmost packman should move to the left. All the asterisks will be eaten, the last asterisk will be eaten after 4 seconds.

Example input:
6
*.P*P*

Example output:
3 4

Example input:
8
*...P..*

Example output:
1 3

Editorial:
Для |P| = 1 решение за O(n) очевидно.
Далее будем рассматривать |P| > 1. Если направить самого левого пакмана вправо, а самого правого — влево, то можно собрать все звезды, поэтому бинпоиском фиксируем время t и решаем задачу принятия решения о съедении всех звезд пакманами за это время.
Для времени t поддерживать в массиве Li следующий инвариант для позиции p:
Если направить и использовать всех пакманов не правее позиции p на протяжении времени t, то можно добиться конфигурации, когда i > p — первая справа звезда, не съеденная пакманом, лежащая правее позиции p, а Li — самая левая звезда, не съеденная пакманом. При этом Li максимально среди всех возможных конфигураций.
Таким образом, лучшей конфигурацией для i является Li = i, что значит, что возможно съесть все звезды, лежащие левее звезды i. Если добавить фиктивную звезду, например, в позиции 2n, то L2n = 2n без потери общности будет говорить о том, что съедение всех звезд возможно.
Если добиться конфигурации, когда i > p является первой звездой, не съеденной пакманом, невозможно, Li следует считать неопределенным. В изначальной конфигурации, когда ни один пакман не использован, определена лишь Li = i для самой левой звезды.
Позиции p будут рассматриваться в порядке возрастания и совпадать с позицией очередного пакмана. Элементы Li для i < p следует считать равными значениям Li в той последней рассмотренной позиции p', в которой p' < i.
Пусть для позиции p' Li были посчитаны, и теперь инвариант нужно поддержать для позиции p > p', в которой точно находится пакман. Рассмотрим позицию ближайшей справа звезды x > p. Lx для позиции p уже не является неопределенным, поскольку можно направить всех пакманов влево и оставить все звезды правее p несъеденными.
Прежде всего, для звезды x нужно определить Lx в случае, если пакман p не используется. Такая конфигурация получается из любой другой для позиции p', поскольку всего лишь смещается позиция разделения. Тогда, если для некого i самой левой звездой являлась Li (возможно, Li = i), то для Lx после смещения позиции она такой и останется. Поэтому выгодно выбрать ту конфигурацию, в которой Li максимально, и обновить Lx значением $$\max_{i < p} L_i$$. (1)
Итак, теперь Li посчитаны с учетом изменения позиции, но не с учетом использования пакмана p. Попробуем направить его влево и покрыть все звезды на отрезке [p - t, p]. Это повлияет на значение только тех звезд i, в которых Li ≥ p - t — они станут равными Li = i, поскольку все звезды левее p в их оптимальных конфигурациях станут съеденными, а первая не съеденная звезда правее p для каждой из них находится в позиции i. (2)
Для учета направления пакмана вправо выделим позицию первой справа звезды y > p + t. Конфигурации Li для звезд i > y определены быть не могут, так как ни один пакман не правее позиции p не может съесть звезду y. Таким образом, при направлении пакмана p вправо обновляться будет только значение Ly, при этом конфигурация для нее будет выбрана из лучшей конфигурации для звезд на отрезке (p, p + t] — $$\max_{p < i \leq p + t} L_i$$. Нетрудно доказать, что это значение равно и максимуму на префиксе $$\max_{i \leq p+t} L_i$$. (3)
Заметим, что обновления (2) и (3) следует производить одновременно после обновления (1).
Обновления (1) и (3) легко поддерживать с помощью переменных, содержащих максимум на соответствующих префиксах, поскольку эти префиксы только увеличиваются при смещении позиции p. Нужно учитывать, что любое обновление Li может изменять эти значения, и после изменения, возможно, изменять соответствующие максимумы на префиксах.
Для выполнения обновления (2) нужно заметить, что p - t возрастают со смещением позиции, и если Li не подвержено изменению обновления (2) на текущей позиции, то, пока значение Li не увеличится, обновление (2) его никак не затронет. Поэтому для выполнения обновления (2) нужно рассматривать только последние позиции, подвергшиеся каким-либо изменениям, а именно Lx на текущем шаге для позиции p (после обновления (1)) и Ly с предыдущего шага для позиции p' (после обновления (3) на предыдущем шаге). Таким образом, обновление (2) затрагивает лишь 2 элемента.
Все обновления выполняются за O(1), и итоговая асимптотика решения задачи для фиксированного t — O(n). Общее решение работает за $$O(n \log n)$$.