Editorial - AtCoder Beginner Contest 272

Contest Duration: 2022-10-08 21:00:00+0900 - 2022-10-08 22:40:00+0900 (local time) (100 minutes) Back to Home

Official

Ex - Flipping Coins 2 Editorial by en_translator

Contents of Editorial

Multipoint evaluation explained
Rephrasing the problem
Using inclusion-exclusion principle
$\mathrm{O}(N^2)$ solution
$\mathrm{O}(N\log^2 N)$ solution

[1] Multipoint evaluation

We first explain the outline of the technique called multipoint evaluation required to solve this problem.

What is multipoint evaluation?

Given $N$-degree polynomial $f(x)$ and an integer sequence $x=(x_1,x_2,\ldots,x_M)$ of length $M$, the technique enables us to find $f(x_1),f(x_2),\ldots,f(x_M)$ in a total of $\mathrm{O}(M\log^2M + N\log N)$ time.

We use the polynomial remainder theorem. Since $f(a)=f(x)\bmod(x-a)$, it is sufficient to find $f(x) \bmod(x-x_1),f(x)\bmod(x-x_2),\ldots,f(x)\bmod(x-x_M)$.

We can use the divide-and-conquer trick. First, we construct a binary tree called a subproduct tree from the leaves. The leaves contain $(x-x_1),(x-x_2),\ldots,(x-x_M)$, and their parents contain the product of two children, i.e. $(x-x_1)(x-x_2),(x-x_3)(x-x_4),\ldots$, and so on.

Next, we calculate the answer using the subproduct tree using the fact that for polynomials $f,g$, and $h$ we have $f\bmod g = (f\bmod gh) \bmod g$.

We first evaluate $f \bmod\big((x-x_1)(x-x_2)\ldots(x-x_M)\big)$ using the root of the subproduct tree. Then, we use the result and the children of the tree’s root to evaluate $\big(f \bmod\big((x-x_1)(x-x_2)\ldots(x-x_M)\big)\big) \bmod \big((x-x_1)(x-x_2)\ldots(x-x_\frac{M}{2})\big)$. (For simplicity, we assume that $M$ is a power of two.)

Such computation on the subproduct tree enables us to find all of $f(x) \bmod(x-x_1),f(x)\bmod(x-x_2),\ldots,f(x)\bmod(x-x_M)$. The complexity, whose analysis we omit, is $\mathrm{O}(M\log^2M + N\log N)$.

For more details, see the following references (in Japanese).

[2] Rephrasing the problem

We will now explain the problem.

We may assume that $A$ is given in ascending order.

First of all, by symmetry any coin is face up after the $N$ operations at equal probability, so it is sufficient to find the probability that coin $(N-1)$ is finally face up.

Proof

It holds because rotating $p$ rotates the numbers of flips on the coins too.

It is sufficient to find $F(K)$ for $K=0,1,\ldots,N$, where $F(K)$ is the number of permutations that flips coin $(N-1)$ $K$ times.

$F(K)$ equals the number of permutations such that the number of $i$’s such that $P_i \geq N-1-A_i$ is exactly $K$. For convenience, let $B_i = N-1-A_i$, then $B$ is monotonically decreasing.

[3] Using inclusion-exclusion principle

It is difficult to directly find $F(K)$ described in [2]. Let us find the number of permutations $P$ such that

$i \in S \Rightarrow P_i \geq B_i$

for all subsets of $S$ of $\lbrace 1,2,\ldots,N\rbrace$ such that $|S|=L$, and let $G(L)$ be their sum.

Then we have the following relation between $F$ and $G$:

$\displaystyle G(L)=\sum_{L \leq K} \binom{K}{L}F(K).$

By the relation above, we can reconstruct $F$ from $G$. The reconstruction appears in ARC140-F, so see also the editorial for that problem.

Let $a_i = (n-i)!G(n-i), b_i = (n-i)!F(n-i)$, and $a(x)$ and $b(x)$ be their generating function.

Then $a_{i} = \sum_{j =0} ^ {i} b_j\frac{1}{(i-j)!} $. Thus, $a(x)=b(x)e^{x}$, so we can find $F$ from $b(x)=a(x)e^{-x}$ in a total of $\mathrm{O}(N\log N)$ time.

Now let us find $G$.

[4] $\mathrm{O}(N^2)$ solution

$G$ can be found with the following Dynamic Programming (DP):

$\mathrm{dp}[i][j]:$ The number of ways determine the first $i$ terms of the permutation $P$ such that there are $j$ indices $i$ which we explicitly let $P_i \geq B_i$.

We consider the transitions of this DP.

If we explicitly let $P_i \geq B_i$ for $i$:
- $(N-B_i-(j-1))\mathrm{dp}[i-1][j-1]$ ways
If we do not explicitly let $P_i \geq B_i$ for $i$:
- $\mathrm{dp}[i-1][j]$ ways

Therefore, the transitions are expressed by:

$\mathrm{dp}[i][j] = (N-B_i-(j-1))\mathrm{dp}[i-1][j-1]+ \mathrm{dp}[i-1][j]$

Finally, we can find as $G(K) = \mathrm{dp}[N][K] (N-K)!$.

The complexity is $\mathrm{O}(N^2)$, so it is hopeless that it finishes in the time limit.

This DP is commonly called “Hakone Ekiden DP” in Japan, named after the former of the following problem:

** Exercises of Hakone Ekiden DP **

AOJ2439 箱根駅伝 (Hakone)
- $n$ people ran in a marathon. Their ranks at the midpoint and the goal were recorded (where no one is in the same place). We know that the rank of each runner at the goal was higher than (U), lower than (D), or same as (-) the runner’s rank at the midpoint. Find the number, modulo $1000000007$, of the possible ranks of the runners at the midpoint.
ABC134-F Permutation Oddness

[5] $\mathrm{O}(N\log^2N)$ solution

Let us consider the DP in [4] in terms of formal power series.

Initially, let $\mathrm{dp2}[i][i-j] \coloneqq \mathrm{dp}[i][j]$. (The motivation is revealed later.)

Then we have

$\mathrm{dp2}[i][j] = (N-B_i-(i-j-1))\mathrm{dp2}[i][j]+ \mathrm{dp2}[i-1][j-1] = (N-B_i + 1 -i+ j)\mathrm{dp2}[i][j]+ \mathrm{dp2}[i-1][j-1].$

Moreover, let $f_i(x)$ be the generating function of $\mathrm{dp2}[i]$, and for simplicity let $C_i \coloneqq N-B_i +1-i$.

Then we have the following relation between $f_i(x)$:

\[f_i(x) = C_i f_{i-1}(x) +xf'_{i-1}(x) +xf_{i-1}(x)=x(f_{i-1}(x)+f'_{i-1}(x)) + C_i f_{i-1}(x).\]

It is a bit sudden, but what if we multiply the both hand sides by $e^x$?

\[f_i(x)e^x = x(f_{i-1}(x)e^x+f'_{i-1}(x)e^x) + C_i f_{i-1}(x)e^x = x(f_{i-1}(x)e^x)' + C_i f_{i-1}(x)e^x,\]

so if we let $g_i(x) \coloneqq f_i(x)e^x$, we have $g_i(x)=xg'_{i-1}(x)+C_i g_{i-1}(x)$. Denoting $[x^j]g_i(x)$ by $g_{i,j}$, we have $g_{i,j}=jg_{i-1,j}+C_i g_{i-1,j} = (j + C_i) g_{i-1,j}$.

Hence, we can obtain $g_{N,j} = g_{0,j}\prod_{i=1}^N(j + C_i)$, to which we can apply the multipoint evaluation described in [1].

Defining a polynomial $h$ by $h(x)=\prod_{i=1}^N(x+ C_i)$, assigning $j=0,1,\ldots,N$ into $h$ yields $\prod_{i=1}^N(j + C_i)$ for all $j$. By the multipoint evaluation, we can enumerate $g_{N,j}$ in a total of $\mathrm{O}(N\log^2N)$ time, thus obtaining $g_N(x)$. By multiplying $e^{-x}$ to $g_N(x)$, we also have $f_N(x)$, thus finding $G(K)$.

Therefore, the problem has been solved in a total of $\mathrm{O}(N\log^2N)$ time.

posted:
last update: