### dfsof's blog

By dfsof, 3 months ago, Let $f(x), x \in \mathbb{Z}$ be the expected times starting from $x$. There are three basic facts:

(1)$f(x) = 1 + 1/2f(x+1) + 1/2f(2x)$.

(2)$f(x) = 0$ if and only if $x \geq n$.

(3)The final answer is $f(1)$, and $f(1)$ could be found in $O(n)$ time naively.

This blog is an extension of CristianoPenaldo's blog. CristianoPenaldo, also known as CP, is one of my best friends besides bfsof. First, similar to CP's idea, I process $f$ in a reversed and coarse-to-fine manner. I calculate $f$ from $n$ to $1$, and divide the interval $[1,n]$ into scales as what CP did. When $scale$ is small, $S(scale)$ is a "coarse" scale. Otherwise, $S(scale)$ is a "fine" scale, that is why we call it "coarse-to-fine". Formally, let $S(scale)$ be $\{x \in \mathbb{Z}| x \times scale \geq n, x \times scale/2 < n\}$. For example, if $n=7$, scale $1$ is $[7, 7]$, scale $2$ is $[4, 6]$, scale $4$ is $[2, 3]$, scale $8$ is $[1, 1]$. It is guaranteed that the scale is a power of $2$ in my algorithm.

$S(scale)= \begin{cases} \\{n\\}, \text{scale==1} \\ [\lceil \frac{n}{scale} \rceil, \lceil \frac{n}{scale/2} \rceil - 1] \cap \mathbb{Z},\text{Otherwise} \end{cases}$

After some brute force computation, I find that the closed-form formula for scale $1$ is $f(x) = 0$ (because there is only one element $n$ on scale $1$, and $f(n) = 0$). The closed-form formula for scale $2$ is $2 - 2(1/2)^{(n-x)}$, by the fact that $f(2x) = 0$ for $x$ on scale $2$. The closed-form formula for scale $4$ is $4 - ?(1/2)^{(n-x)} - ?(1/2)^{(n-2x)}$, I failed to compute it due to my poor computation ability.

The key obstacle lies in the difficulty handling $f(2x)$. For $x \in S(scale), scale \neq 1$, $2x$ belongs to $S(scale/2)$. The key idea is to determine the closed-form solutions for each scale recursively. When we determine the closed-form solutions for $S(scale)$, we can utilize the closed-form solution from $S(scale/2)$ by simply expanding $f(2x)$. CP considered using the Berlekamp-Massey algorithm, but it involves matrix binary exponentiation. We will handle the closed-form solution in a more explicit manner.

Theorem: The closed form solution for $S(scale)$ is

$f(x) = C_0+\sum\limits_{i=1}^{\log_2{scale}}C_i (1/2)^{(n-2^{(i-1)}x)}$. $C_i$ are undetermined coefficients.

We can prove via induction. Suppose $scale > 1$, then $f(x) = 1 + 1/2f(x+1) + 1/2f(2x) = 1 + 1/2f(x+1) + 1/2(C_0+\sum\limits_{i=1}^{\log_2{scale}-1}C_i (1/2)^{(n-2^{i}x)})$

$f(x)-C_0-2 = 1/2(f(x+1)-C_0-2) + \sum\limits_{i=2}^{\log_2{scale}}C_i (1/2)^{(n-2^{i-1}x)}$

Suppose $f(x) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}D_i (1/2)^{(n-2^{i-1}x)} = 1/2(f(x+1) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}D_i (1/2)^{(n-2^{i-1}(x+1))})$.

for each $D_i$, $(2^{(2^{i-1}-1)}-1)D_i = 1/2C_i$, and $D_i = \frac{1}{2^{(2^{i-1})} - 2}C_i$.

Let $mx$ (short for maximum) be the maximum element from this scale. For example, when $n=7$, the $mx$ for scale $1, 2, 4, 8$ are $7, 6, 3, 1$ respectively.

$f(x) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}D_i (1/2)^{(n-2^{i-1}x)} = (1/2)^{(mx - x)}(f(mx) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}D_i (1/2)^{(n-2^{i-1}mx)})$. And if we calculate $f(mx)$ in advance, $f(mx) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}D_i (1/2)^{(n-2^{i-1}mx)}$ would be a constant, and $(1/2)^{(mx-x)}$ could be transformed into $Constant*(1/2)^{(n-x)}$, where $Constant$ is $(1/2)^{(mx-n)}$.

By the proof of the above theorem, we can almost get the closed-form solution of $S(scale)$ from $S(scale/2)$ except one term $(1/2)^{m-x}$. To handle this issue, we just fetch the $mx$ element from that scale and use the method of undeterminated coefficients to calculate $C_1$, i.e., the coefficient of $(1/2)^{m-x}$. The closed-form solution of each scale has length $O(log scale)$, and calculate $f(mx)$ takes $O(log scale \times log n)$ time (because the length of closed-form is $O(log scale)$, and calculate each item, for example, $(1/2)^{(n-x)}$, involves binary exponentiation, therefore the overall time is $\sum\limits_{log scale=1}^{log n} O(log scale \times log n) = O((log n)^3)$ per test case.  Comments (4)
 » xiao fake xia orz!!!
•  » » Orz!
 » Oh bro! I forgot to expand the closed-form explicitly.
 » I hope I can understand your idea correctly.Assume the closed-form on scale $8$ is $f(x) = C_0 + C_1(\frac{1}{2})^{n-x} + C_2(\frac{1}{2})^{n-2x} + C_3(\frac{1}{2})^{n-4x}$. Now I want to get the closed-form solution on scale $16$. If $x \in S(16)$, then $2x \in S(8)$, and when I substitute $2x$ into the closed-form on the scale $8$, $C_0$ becomes unchanged, $C_1(\frac{1}{2})^{n-x}$ becomes $C_1(\frac{1}{2})^{n-2x}$, $C_2(\frac{1}{2})^{n-2x}$ becomes $C_2(\frac{1}{2})^{n-4x}$, $C_3(\frac{1}{2})^{n-4x}$ becomes $C_3(\frac{1}{2})^{n-8x}$. And the new term $(\frac{1}{2})^{n-x}$ comes from such a recurrence $f(x) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}\frac{C_i}{2^{2^{i-1}}-2} (\frac{1}{2})^{n-2^{i-1}x} = newC_1(\frac{1}{2})^{n-x}$. Then $f(x) = C_0 + 2 + newC_1 (\frac{1}{2})^{n-x} - \sum\limits_{i=2}^{\log_2{scale}}\frac{C_i}{2^{2^{i-1}}-2}(\frac{1}{2})^{n-2^{i-1}x}$ and $newC_1$ is a coefficient to be determined?In fact the $newC1 = (\frac{1}{2})^{mx-n}(f(mx) - C_0 - 2 + \sum\limits_{i=2}^{\log_2{scale}}\frac{C_i}{2^{2^{i-1}}-2} (\frac{1}{2})^{n-2^{i-1}mx})$ could be explicitly calculated.Hope my understanding is correct.