Problem Link: https://codeforces.net/contest/1864/problem/H

Submission Link: https://codeforces.net/contest/1864/submission/220919821

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.

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.