E - 1D Reversi Builder Editorial by evima


How to find the number of black stones in the end from the colors of squares and \(s\)

If the squares at both ends have the same color, all \(n\) stones will be of that color. Otherwise, let \(S_B\) and \(S_W\) be the connected components of black and white squares at the ends, respectively. Then,

  • If the distance from \(s\) to \(S_W\) is less than the distance to \(S_B\), there will be \(|S_B|\) black stones;
  • otherwise, there will be \(n - |S_W|\) black stones.

Why?

We can prove that the white stones always form a connected component, and so do the black stones. Additionally, once a stone is placed at either end, the color of that stone never changes. Thus, if the squares at both ends have the same color, all stones will be of that color.

Let us move on to the case the squares at the ends have different colors. We will consider two cases: the case \(S_W\) gets a stone first, and the case \(S_B\) gets a stone first. If \(S_B\) gets a stone first, at the moment just before \(S_W\) gets a stone later, the leftmost and rightmost stones already placed are both black, so all the stones placed are black, similarly to the argument above. The colors of stones never change from then on, so there will be \(n-|S_W|\) black stones in the end. In the same way, if \(S_W\) gets a stone first, there will be \(|S_B|\) black stones in the end. Therefore, Kuro will put stones trying to reach \(S_B\) as fast as possible, and Shiro will try to reach \(S_W\) as fast as possible, so the result depends on the distance from \(s\) to \(S_B\) and \(S_W\), in the way stated above.

The counting

Let \(W\) and \(B\) be the expected number of white and black stones, respectively. Then, \(W+B=n\), so we can find \(W\) if we can find \(W-B\).

Now, consider the effect of inverting the colors of squares on the result. In almost all cases, inverting a game that ends with \(x\) black stones results in a game that ends with \(x\) white stones. Thus, those cases do not contribute to \(W-B\), so we will ignore them.

The only other cases are the cases the distances from \(s\) to \(S_B\) and \(S_W\) are equal.

Consider when \(S_B\) is to the left, and \(s\) is to the left of the middle. The difference between the final numbers of black and white stones is \(4s-2|S_B|-n+2\) with probability \(2^{-n+2s-2|S_B|-1}\). Thus, we need to efficiently compute the sum of \((4s-2|S_B|-n+2)2^{-n+2s-2|S_B|-1}\) over \(|S_B| = 1,2,\dots,s-1\). This sum has the form \(\Sigma_{i=0}^k (a+bi) 4^i\).

Now, consider when \(S_B\) is to the left, and \(s\) is to the right of the middle. The difference between the final numbers of black and white stones is \(n-2|S_W|\) with probability \(2^{n-2s-2|S_W|-3}\). Thus, we need to efficiently compute the sum of \((n-2|S_W|)2^{n-2s-2|S_W|-3}\) over \(|S_W| = 1,2,\dots,n-c-2\). This sum also has the form \(\Sigma_{i=0}^k (a+bi) 4^i\).

The other cases also go similarly, so we just need to compute these sums efficiently.

We can do so by precomputing \(\Sigma_{i=0}^k 4^i\) and \(\Sigma_{i=0}^k i4^i\) for each \(k=0,\dots,n\) in a total of \(O(n)\) time, and then summing them up after multiplying them by some coefficients. The other option is to transform \(\Sigma_{i=0}^k i4^i\) into \(\Sigma_{i=1}^k 4^i \Sigma_{j=0}^{k-i} d^j\), and then transform it again using the formula to find the sum of geometric series to compute it in \(O(\log k)\) time.

Sample Implementation in C++ (We directly dealt with expected values in this article, but this implementation finds the count of stones and then divides it.)

posted:
last update: