Hello Codeforces!
In my blog, I notified that I had written a new editorial for AWTF2019-E, which is well-known as the most difficult problem in AtCoder. The original is written in Japanese, so I translate it into English for international readers here on this site. The original is here.
Problem Summary
There is a long bench divided into $$$M$$$ sections. Initially, the bench is vacant and $$$M$$$ people come one by one. The people perform the following action.
- If there is any section where itself and its adjacent two sections are all vacant, the person randomly chooses one from such sections and sits there.
- Otherwise, the person leaves the bench.
After the all M people come, Snuke chooses an interval of consecutive $$$N$$$ sections and takes a photo. Your task is to calculate the limit of the probability that the taken photo matches a given situation when $$$M$$$ goes infinity.
The probability to compute can be uniquely represented using three rational numbers $$$p,q,r$$$ and $$$e$$$(the base of the natural logarithm) in the following format.
$$$p+\frac{q}{e}+\frac{r}{e^2}$$$
Thus, you should compute the three rational numbers modulo $$$10^9+7$$$.
Important Consideration
From the sample input/output 1, we learn the probability that a section is taken is $$$\frac{1}{2}-\frac{1}{2e^2}$$$. This must not be obvious, so we should prove this first.
We rephrase the problem statement. First, we assign random rational numbers between $$$0$$$ and $$$1$$$ to each section. Let $$$X_i$$$ be the rational numbers assigned to the $$$i$$$-th section. Next, the behavior of the people can also be rephrased as follows:
- For each section in order of the assigned rational numbers, the person checks if the person can sit down in the section or not. If possible, the person sits down there immediately.
- If the person is not yet seated after all sections being checked, the person leaves the bench.
Considering the randomness of the assigned rational numbers, the problem holds under this statement. Then, as a matter of fact, we can compute the probability easily.
We are going to compute the probability of the $$$i$$$-th section. Consider the longest descending runs from the $$$i$$$-th to both directions. Basically, if $$$X_{i-2}>X_{i-1}<X_i$$$, the length of the run to the left is one. Likewise, if $$$X_{i-3}>X_{i-2}<X_{i-1}<X_i$$$, the length of the run to the left is two. Then, the necessary and sufficient condition for a section to be taken is that the lengths of the runs are both even.
Let P( inequality ) be the probability that the inequality holds. Finally, when $$$X_i=x$$$, the probability that the length of the run to either left or right is even can be represented as follows:
$$$1-P(X_{i-1}<X_i)+P(X_{i-2}<X_{i-1}<X_i)-P(X_{i-3}<X_{i-2}<X_{i-1}<X_{i})+\cdots$$$
When $$$X_i=x$$$, with calculating each term, we get the following formula.
$$$1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots$$$
This is, I suspect you to know, the Maclaurin expansion of $$$e^{-x}$$$. The condition has to be met on both sides, so the whole probability is $$$e^{-2x}$$$. Since $$$x$$$ is between $$$0$$$ and $$$1$$$, the expectation value of the probability can be calculated by following integrating.
$$$\int_0^1 e^{-2x}=\frac{1}{2}-\frac{1}{2e^2}$$$
We have proved the sample input/output 1 now!
Solution For The Original
We can prove the sample 1, but more process is required to solve the original problem. We have to compute the probability for any photo. To come to the point, we can calculate the function by DP. Let $$$dp[i][j][k][l]$$$ be a function which returns the probability that the subsegment $$$[0,i]$$$ of the photo matches the situation. Then, $$$j$$$ represents the parity of the longest descending run from $$$i$$$-th to the left. However, the probability depends on the parity of the run to the right, too. Therefore, that has to be represented by the remaining two subscripts, $$$k,l$$$. When $$$k$$$ is true, the length to the right can be even. Similarly, when $$$l$$$ is true, the length to the right can be odd. Here, we can gradually calculate the functions.
DP Detail
First, let's define the initial value.I think this isn't too hard.
When $$$s[0]$$$ is 'X', $$$dp[0][0][1][0]=e^{-x}$$$. That's because the lengths of two runs have to be even and the probability is $$$e^{-x}$$$.
Otherwise, $$$dp[0][0][0][1]=e^{-x}$$$ and $$$dp[0][1][1][1]=1-e^{-x}$$$. When the length to the left is even, that to the right has to be odd. When the length to the left is odd, that to the right can be either even or odd.
To avoid complexity, when a subscript can be either $$$0$$$ or $$$1$$$, we use a slash like $$$[0/1]$$$, thereafter. Let's consider the transition.
When $$$s[i]$$$ is 'X', the destination can be only $$$dp[i][0][1][0]$$$ because the both lengths have to be even. Further, we divide into cases. When $$$X_{i-1}<X_i$$$, the length to the left has to be odd in the previous status because the length to the left has to be even now. In addition, the length to the right is naturally $$$0$$$ (even) in the previous, so the transition source is $$$dp[i-1][1][1][0/1]$$$. The formula is follows:
$$$dp[i][0][1][0]+=\int_0^x dp[i-1][1][1][0/1](y)dy$$$
Similarly, we can compute the remaining four transitions. I don't think it's too hard.
$$$dp[i][0][1][0]+=\int_{x}^{1}dp[i-1][0/1][0/1][1](y)dy$$$
$$$dp[i][0][0][1]+=\int_{0}^{x}dp[i-1][1][1][0/1](y)dy$$$
$$$dp[i][1][1][1]+=\int_{0}^{x}dp[i-1][0][1][0/1](y)dy$$$
$$$dp[i][0][0][1]+=\int_{x}^{1}dp[i-1][0/1][1][0/1](y)dy$$$
These are all, but we have to calculate the answer from the functions.
Calculating The Answer
The answer to the problem depends on the parity of the length of the run from the right end of the photo to the right. We can find the answer $$$A$$$ by the following formula.
$$$A=\int_0^1 dp[N-1][0/1][1][1](x)dx+\int_0^1dp[N-1][0/1][1][0](x)e^{-x}dx+\int_0^1dp[N-1][0/1][0][1](x)(1-e^{-x})dx$$$
We can easily prove this considering the parity of the length to the right. Finally, we found the answer!
The DP Function's Style
We have to think about the style of the DP function and how we should calculate its integral. As a result, the functions always can be written in the following format using two polynomial $$$p,q$$$, which has rational coefficients, and one constant rational number $$$c$$$.
$$$p(x)+\frac{q(x)}{e}+ce^{-x}$$$
The definite integral of this can be calculated easily and we notice that the definite integral(of integration interval $$$[0,x]$$$ or $$$[x,1]$$$) always can be written in the format. Also, the degrees of the polynomials are at most $$$N-1$$$, so we should store the coefficients and $$$c$$$ modulo $$$10^9+7$$$ and then we can completely represent the function.
Integrating To Find The Answer
Finding answers required solving a little difficult(not in the curriculum of high school in Japan) integrating. As I mentioned before, when we calculate the answer for the problem itself, we have to calculate the integral of the products of polynomials and $$$e^{-x}$$$, with an integration interval $$$[0,1]$$$.
The following formula is known:
$$$\int_{0}^{1}x^ie^{-x}dx=i!-e^{-1}i!\sum_{j=0}^{i}\frac{1}{j!}$$$
I abbreviated the details of the proof, so please ask Google or any search engine.
Finally, we can find the answer of the integral with this formula and have solved this problem. The time complexity is $$$O(N^2)$$$.The DP transitions take $$$O(N)$$$, the integrating in DP takes $$$O(N)$$$ and the integrating to calculate the answer for the problem itself takes $$$O(N^2)$$$.
Implementation
my source code is here. Please refer.
Thank you for reading this blog. I hope more and more people solve this problem with this editorial.
I am deeply grateful to butsurizuki, ranse-LFZ and myo-kun, who reviewed this post.
