Count Permutations
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3500
Tags: math

You are given a string $$$s$$$ with length $$$n-1$$$ whose characters are either $$$\texttt{<}$$$ or $$$\texttt{>}$$$.

Count the permutations $$$p_1, \, p_2, \, \dots, \, p_n$$$ of $$$1, \, 2, \, \dots, \, n$$$ such that, for all $$$i = 1, \, 2, \, \dots, \, n - 1$$$, if $$$s_i$$$ is $$$\texttt{<}$$$ then $$$p_i < p_{i+1}$$$ and if $$$s_i$$$ is $$$\texttt{>}$$$ then $$$p_i > p_{i+1}$$$.

Since this number can be very large, compute its logarithm in base $$$2$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$).

The second line contains a string $$$s$$$ of length $$$n-1$$$; each character of $$$s$$$ is either $$$\texttt{<}$$$ or $$$\texttt{>}$$$.

Output format:
Print the logarithm in base $$$2$$$ of the number of permutations satisfying the constraints described in the statement.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$x$$$ and let the correct answer be $$$y$$$. Your answer is accepted if and only if $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$.

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

Note:
In the first sample, there is only one valid permutation, that is $$$[2, 1]$$$. Since $$$\log_2(1)=0$$$, the correct output is $$$0$$$.

In the second sample, there are $$$2$$$ valid permutations, that are $$$[3, 1, 2]$$$ and $$$[2, 1, 3]$$$. Since $$$\log_2(2)=1$$$, the correct output is $$$1$$$.

In the third sample, there are $$$4$$$ valid permutations, that are $$$[1, 5, 4, 3, 2]$$$, $$$[2, 5, 4, 3, 1]$$$, $$$[3, 5, 4, 2, 1]$$$, $$$[4, 5, 3, 2, 1]$$$. Since $$$\log_2(4)=2$$$, the correct output is $$$2$$$.

In the fourth sample, there are $$$909$$$ valid permutations. Notice that $$$\log_2(909)=9.828136484194\ldots$$$

Example input:
2
<

Example output:
0.0000000000

Example input:
3
<>

Example output:
1.0000000000

Editorial:
This was meant to be the hardest problem of the mirror. It required advanced knowledge in modern combinatorics, together with some clever ideas to reach the desired precision. The solution splits in two parts: first we obtain a nontrivial (actually, pretty hard) formula for the exact answer, then we explain how to approximate it quickly enough.
Exact formula for the answer via Hook-length formula for skew diagrams
We will give for granted the definition of Young Diagram and Young Tableau.
As a first step, we associate to the string $$$s$$$ a Young diagram as follows.
We construct a path, that will be the border of the Young diagram. Start with a single cell (that will be the bottom left corner of the diagram), then iterate over the characters of $$$s$$$. Each time you read $$$\texttt{>}$$$, go up. Each time you read $$$\texttt{<}$$$, go right. The path we have constructed is the border (apart from the two long sides) of the Young diagram associated to $$$s$$$. See the figure, which refers to the string $$$s='<>{<}<{>}><><{<}{>}><'$$$.
In this Young diagram, we say that a cell is special if it belongs to the path we have constructed.
Notice that each way to fill the special cells according to the usual law of a Young tableaux coincides with a permutation satisfying the constraints given by $$$s$$$. So, counting the permutations is the same as counting the number of Young tableaux restricted to the special cells.
If we were to count the number of Young tableaux on the whole Young diagram, we could apply the hook-length formula. It turns out that there is a new formula, due to Naruse, that is valid also for skew diagrams, that are diagrams obtained as differences of two Young diagrams (notice that the special cells can be seen as the difference of two Young diagrams).
Refer to the original slides by Naruse and to this more recent paper by Morales, Pak, Panova for a presentation of the formula in the general case (with proofs).
In the case we need, i.e., for border strips (this is how the paper by Morales, Pak, Panova call the special cells) the formula simplifies a lot. Instead of stating the general formulas, which would require the definition of excited diagram, let us state here the formula for the special case of border strips.
Summing up these results we get the following formula.
Number of Tableaux on Border Strips (consequence of Naruse's hook length formula): Let $$$\lambda$$$ be a Young diagram and let $$$\lambda'$$$ be its border strip (i.e., its nontrivial border, as described above). A valid path in the $$$\lambda$$$ is a sequence of adjacent cells in $$$\lambda$$$ going from the bottom left corner to the top right corner that goes only up and right. The weight of a valid path is the product of the inverses of the hook-lengths of the cells of the path.
Let $$$W(\lambda)$$$ be the sum of the weights of all valid paths on $$$\lambda$$$. The number of tableaux on $$$\lambda'$$$ is $$$|\lambda'|!W(\lambda)$$$ (here $$$|\lambda'|$$$ denotes the number of cells of $$$\lambda'$$$).
This formula can be used to compute the answer in $$$O(n^2)$$$, which is too slow for this problem (notice that there is also a much simpler solution with complexity $$$O(n^2)$$$).
How to optimize the solution
Notice that the hook-length of a cell is, in general, large for cells that are far from the border. Hence, we may expect that the contribution to the result given by path which are not close to the border at all times is negligible. This claim is highly nontrivial and we, the judges, have no idea of how to prove it. But experimentally it is true; for the precision required in this problem it is sufficient to consider path that stay all the time at a diagonal distance from the border $$$\le D=500$$$.
So, we must compute the sum, over all paths that stay at a distance $$$\le D$$$ from the border of the Young diagram. This can be done with a simple dynamic programming.
It remains to understand how to take care of the huge numbers that we are going to get. There are fundamentally two ways:
• Instead of keeping the numbers, we keep their logarithms. But if we are given $$$\log(x)$$$ and $$$\log(y)$$$, how do we compute the sum without computing explicitly $$$x$$$ and $$$y$$$? Assume that $$$x<y$$$, then we compute $$$$$$ \log(x+y) = \log(y) + \log(1+\exp(\log(x)-\log(y))).$$$$$$
• We keep the numbers as long double. Still, during our dynamic programming, the exponent may become larger then the largest exponent admissible for long doubles. During our dynamic programming we will keep a vector of values, denoting the sum of the weights of paths starting from the bottom left corner and ending at one point on a fixed diagonal. At each step we will keep $$$D$$$ values and if we divide all of them by $$$2$$$, then the final result will change by $$$2$$$. Therefore, we divide all of them by $$$2$$$, until the largest one is $$$\le 1$$$. Doing this, we do not lose too much precision and everything fits in a long double. This solution is much faster than the previous one.