Official

F - ESPers Editorial by evima


Here, we introduce another solution with formal power series. Similarly to the main solution, let us find the probability that the two options have the same number of votes at some time after \(X\) cast a vote.

Consider the \(xy\)-coordinate plane, and correspond each grid point \((x,y)\) ( \(x, y \geq 0\) ) to a state where one option has \(x\) votes and the other has \(y\) votes. Each progression of voting corresponds to a path of length \(2N+1\) from \((0,0)\) to some grid point on \(x+y=2N+1\). Among the line segments forming that path, choose \(K\) in a direction that increases \(\max\{x,y\}\), and assume that those are cast by ESPers. Then, this progression of votes happens with the following probability:

\(2^s / \left(\binom{2N+1}{K}\times 2^{2N+1}\right)\)

where \(s\) is the number of line segments that do not intersect with \(x=y\) among the \(K\) chosen ones. Thus, we want to find the sum of \(t \times 2^s\), where \(t\) is the number of line segments after which the path intersects with \(x=y\) among the \(K\) chosen ones.

Now, to a line segment of length \(1\) whose endpoints are grid points with \(x, y \geq 0\), let us correspond a polynomial with a variable \(w\) as follows:

  • if the endpoint of the segment that is closer to \((0, 0)\) is on \(x=y\), correspond \(1+w\) to it;
  • if, seen from \((0, 0)\), the segment is in a direction that increases \(\max\{x,y\}\), correspond \(1+2w\) to it;
  • if, seen from \((0, 0)\), the segment is in a direction that does not increase \(\max\{x,y\}\), correspond \(1\) to it.

Let us fix two grid points \(X, Y\). Then, for every path from \(X\) to \(Y\), take the product of the segments along that path, and consider the polynomial that is the sum of those products. Then, the coefficient of \(w^k\) in this polynomial is the sum of \(2^s\) for all transitions from \(X\) to \(Y\) such that \(k\) ESPers voted between these two states, where \(s\) is the number of ESPers who voted from a state that is not on \(x=y\). Using this fact, we can compute the desired sum as follows.

Consider all combinations of non-negative integers \(i, j, k\) such that \(i+j+k=N-1\), and construct polynomials \(P_i(w), Q_j(w), R_k(w)\) as follows:

  • \(P_i(w)\) is the sum over all paths from \((0, 0)\) to \((i, i)\) of the products of the polynomials corresponding to the segments along the path;
  • \(Q_j(w)\) is the similar sum over all paths from \((0, 0)\) to \((j+1, j+1)\) that do not pass \(x = y\) except at the starting and ending points;
  • \(R_k(w)\) is the similar sum over all paths of length \(2k+1\) from \((0, 0)\).

Then, consider all combinations of non-negative integers \(l, m, n\) such that \(l+m+n=K\), and the desired value is the sum of all \(pqr\), where \(p\) is the coefficient of \(w^l\) in \(P_i(w)\), \(q\) is the coefficient of \(w^m\) in \(wQ_j^{'}(w)\), and \(r\) is the coefficient of \(w^n\) in \(R_k(w)\). Note that the coefficient of \(w^m\) in \(wQ_j^{'}(w)\) is the coefficient of \(w^m\) in \(Q_j\) multiplied by \(m\), in the end.

Now, consider power series with two variables: \(P(z,w) = \sum_{i\geq 0} z^iP_i(w)\), \(Q(z,w) = \sum_{j \geq 0} z^j Q_j(w)\), and \(R(z,w) = \sum_{k \geq 0} z^k R_k(w)\). From the observation above, the desired value is the coefficient of \(z^{N-1}w^{K-1}\) in \(P(\partial_w Q)R\). Below, we compute the concrete values of \(P\), \(Q\), and \(R\).

First, let us compute \(R\). Since \(R_k(w)=(2+2w)^{2k+1}\), we have:

\(R(z,w)=\sum_{k \geq 0} 2(1+w)\{4z(1+w)^2\}^k = \frac{2(1+w)}{1-4z(1+w)^2}\).

Next, let us compute \(Q\). Since \(Q_j(w)=2c_j(1+w)(1+2w)^j\) where \(c_j\) is the \(j\)-th Catalan number, we have:

\(g(z)=\sum_{j \geq 0} c_j z^j = \frac{1-\sqrt{1-4z}}{2z}\)

from which we have:

\(Q(z,w)=\sum_{j \geq 0} 2c_j(1+w)\{z(1+2w)\}^j = 2(1+w)g(z(1+2w))\).

Lastly, let us compute \(P\). By classifying the paths from \((0,0)\) to \((i,i)\) according to the number of times they pass \(x = y\), we get:

\(P(z,w)=1+zQ(z,w)+(zQ(z,w))^2+\cdots = \frac{1}{1-zQ(z,w)}\).

By substituting the above value of \(Q\), we have:

\(P(z,w)=\frac{1-2z(1+w)(1+2w)g(z(1+2w))}{1-4z(1+w)^2}\).

By letting \(v=z(1+2w)\) and putting the above together, we have:

\(P(\partial_w Q)R = \frac{2(1+w)(1-2(1+w)vg(v))(2wg(v)+4zw(1+w)g'(v))}{\{1-4z(1+w)^2\}^2}\).

The coefficient of \(z^{N-1}w^{K-1}\) here is the desired value.

By substituting the specific value of \(g(v)\), we can see that, after all, the problem can be solved by a constant number of computations of the coefficient of some term \(z^nw^k\) in \(\frac{(1-4v)^{\pm 1/2}}{\{1-4z(1+w)^2\}^2}\) and \(\frac{1}{\{1-4z(1+w)^2\}^2}\). Below, we show a way to do it in \(O(n)\) time. Here, we focus on finding the coefficient of \(z^nw^k\) in \(\frac{(1-4v)^{1/2}}{\{1-4z(1+w)^2\}^2}\), since the rest is similar to this.

By noticing that \(1-4z(1+w)^2=(1-4v)-4zw^2\), we have:

\(\frac{(1-4v)^{1/2}}{\{1-4z(1+w)^2\}^2} = (1-4v)^{-3/2} \cdot \left(1-\frac{4zw^2}{1-4v}\right)^{-2} = \sum_{k \geq 0} 2^{2k}(k+1)z^kw^{2k}(1-4v)^{-(2k+3)/2}\).

Since \(v=z(1+2w)\), we are done if we can find the coefficient of \(v^{n-k}\) for \(0 \leq k \leq n\) in \((1-4v)^{-(2k+3)/2}\). To do this, we can use the following formulae:

  • the coefficient of \(v^n\) in \((1-4v)^{-(2k+1)/2}\) is \(\frac{(2n+2k-1)!!}{(2n-1)!!(2k-1)!!}\binom{2n}{n}\);
  • the coefficient of \(v^n\) in \((1-4v)^{-k}\) is \(\binom{n+k-1}{k-1} 2^{2n}\).

Thus, by precomputing the factorials and double factorials, we can find each coefficient in \(O(1)\) time. Therefore, by finding the coefficient for each \(k\) in \(O(1)\) time, we can find the coefficient of \(z^nw^k\) in a total of \(O(n)\) time.

In the end, the problem can be solved in \(O(N)\) time.

posted:
last update: