### 1. Optimization of $f(n)$↵
↵
Let the boundary sequence be defined as:↵
↵
↵
$$f'(k) = \sum_{i=0}^k 2^i = 2^{k+1} - 1$$↵
↵
For any given $n$, let $b$ be the maximum integer such that $l \le n \le r$, where $l = f'(b)$ and $r = f'(b+1)$. The state transition is given by:↵
↵
↵
$$f(n) = \min(b + f(n - l + 1) + 1,\; b + 1 + r - n)$$↵
↵
### 2. Prefix Sums $f''(x, y)$ and Pivot $k'$↵
↵
Define the prefix sum function:↵
↵
↵
$$f''(x, y) = \sum_{i=x}^y f(i)$$↵
↵
Let $S$ be the ordered set of boundary values such that $f(S_i) = i$:↵
↵
↵
$$S = \{ 2^k - 1 \mid k \in \mathbb{Z}^+ \} = \{1, 3, 7, 15, 31, \dots\}$$↵
↵
For an interval $(l, r)$ where $l = S_i$ and $r = S_{i+1}$, the size of the range is $l$. Within $(l, r)$, there exists a pivot $k'$ that splits the piecewise evaluation of $f(n)$:↵
↵
↵
$$f(n) = \begin{cases} b + f(n - l + 1) + 1 & \text{if } n \le k' \\ b + 1 + r - n & \text{if } n > k' \end{cases}$$↵
↵
### 3. Block Sum Expansions↵
↵
Using $k'$, the sum over the open interval $(l, r)$ expands to:↵
↵
↵
$$f''(l, r) = 2b + 1 + f''(l + 1, k') + f''(k' + 1, r - 1)$$↵
↵
↵
Alternatively:↵
↵
↵
$$f''(l, r) = f''(l, k') + f''(k' + 1, r) - 2$$↵
↵
The sub-segment sums can be evaluated as:↵
↵
↵
$$f''(k' + 1, r - 1) = (r - k' - 1) \left( b + 1 - \frac{k' - r}{2} \right)$$↵
↵
$$f''(l + 1, k') = (k' - l)(b + 1) + f''(1, k' - l)$$↵
↵
We recursively evaluate $f''(1, k' - l)$ by finding the largest boundary $m \in S$ such that $m \le k' - l$:↵
↵
↵
$$f''(1, k' - l) = f''(1, m) + f''(m + 1, k' - l)$$↵
↵
### 4. Memoization and Precomputation↵
↵
We precompute the prefix sums for the first 60 boundaries:↵
↵
↵
$$\text{memo}[i] = f''(1, S_i) \quad \text{for } 0 \le i \le 60$$↵
↵
An arbitrary query $f''(L, R)$ is resolved by decomposing it into $S$-bounded blocks:↵
↵
↵
$$f''(L, R) = f''(L, S_i) + \sum_{j=i}^{i+\beta-1} f''(S_j + 1, S_{j+1}) + f''(S_{i+\beta} + 1, R)$$↵
↵
**Pivot Searching ($k'$):**↵
Let $h = r - k'$. The block size grows at a rate of $2\times$, and $h$ grows at a rate of $\sim \mathcal{O}(\log^2(\text{block size}))$. Because $h$ strictly increases per block (i.e., for block $b$ and block $b-1$, $h_b > h_{b-1}$), we can find the new pivot $k'$ by scanning starting from $r - h_{b-1}$. We memoize these pivots:↵
↵
↵
$$\text{kmemo}[i] = k'_i \quad \text{for } 0 \le i \le 60$$↵
↵
### 5. Complexity Analysis↵
↵
**Cost to compute `memo`:**↵
↵
↵
$$\approx \sum_{i=0}^{60} \log_2(2^i - 1) \approx \sum_{i=0}^{60} i = \frac{60 \times 61}{2} = 1830$$↵
↵
**Cost to compute `kmemo`:**↵
↵
↵
$$\approx \log_2^2(2^{59} - 1) \times \log_2(10^{18})$$↵
↵
$$\approx \log_2^2(2^{59}) \times 18 \log_2(10)$$↵
↵
$$\approx (59)^2 \times 60 = 3481 \times 60 = 208860$$↵
↵
**Total Precomputation Cost:**↵
↵
↵
$$\le 1830 + 208860 = 210690 \text{ operations}$$↵
↵
↵
↵
↵
↵
<spoiler summary="Click here to see my original raw notes/math">↵
f(n) optimization:↵
↵
f'(k) = ∑ᵢ₌₀ᵏ 2 ^ k↵
↵
if n is such that ↵
max(l) <= n <= min(r)↵
and l = f'(b) and r = f'(b + 1)↵
We choose b such that, b is a k in which f'(k) is the greatest k due to which, f'(k) is still lesser than n.↵
↵
f(n) = min(b + f(n — l + 1) + 1, b + 1 + r — n)↵
↵
↵
f''(x, y) optimization:↵
↵
f''(x, y) = ∑ᵢ₌ₓʸ f(i)↵
↵
S = {⍵ᵢ ∈ ⍵ ∩ ℤ | f(f'(⍵ᵢ)) = ⍵ᵢ}↵
i.e {1, 3, 7, 15, 31} ⊂ S | 2ᵏ — 1 ∈ S↵
f(2ᵏ — 1) = k↵
↵
Assuming S is an ordered set.↵
↵
l = Sᵢ, r = Sᵢ₊₁ ↵
↵
The no. of numbers in the range (l, r) is l.↵
↵
Pick a number k' in the range of (l, r) such that ↵
↵
┌ n ≤ k' : b + f(n - l + 1) + 1↵
f(n) = ┤↵
└ n > k' : b + 1 + r — n↵
↵
for n ∈ (l, r)↵
↵
f''(l, r) = 2b + 1 + f''(l + 1, k') + f''(k' + 1, r — 1) ↵
or ↵
f''(l, r) = f''(l, k') + f''(k' + 1, r) — 2↵
↵
∴ f''(k' + 1, r — 1) = (r — k' — 1) (b + 1 — (k' — r)/2)↵
f''(l + 1, k') = (k' — l) (b + 1) + f''(1, k' — l)↵
↵
f''(1, k' — l) = f''(1, m) + f''(m + 1, k' — l)↵
↵
We pick m such that m ∈ S and m = f'(c), m is the greatest Sᵢ; m <= k' — l.↵
↵
We can further memo ↵
↵
⨁ᵢ₌₀⁶⁰ memo[f'(i)] = f''(1, f'(i))↵
↵
f''(left, right) = f''(left, Sᵢ) + f''(Sᵢ₊₁ + 1, Sᵢ₊₂) + ... + f''(Sᵢ₊ᵦ + 1, right)↵
↵
Growth rate of k' for each block, block size grows at the rate of 2x, r — k' grows at the rate ~log²(block size). Also r — k' for each block strictly increases, therefore the if for block b — 1, r — k' = h, for block b, r — k' = h'↵
↵
h' > h↵
↵
We can scan from r — h till we get the k' for new block b, total cost for compute is the r — h of the largest block.↵
↵
⨁ᵢ₌₀⁶⁰ kmemo[i] = k'↵
↵
All of this is precomputed.↵
↵
Cost of computing memo ~= ∑ᵢ₌₀⁶⁰ log(2ⁱ — 1)↵
= ∑ᵢ₌₀⁶⁰ log(2ⁱ)↵
= ∑ᵢ₌₀⁶⁰ i * log(2)↵
= ∑ᵢ₌₀⁶⁰ i↵
= (60 * 61) / 2↵
= 1830↵
↵
Cost of compute of kmemo ~= log²(2⁵⁹ — 1) * log(10¹⁸)↵
= log²(2⁵⁹) * 18 * log(10)↵
= ((59)(log²(2)))² * 60↵
= 3481 * 60↵
= 208860↵
↵
Total Precompute Cost <= 1830 + 208860↵
= 210690↵
</spoiler>↵
↵
↵
Let the boundary sequence be defined as:↵
↵
↵
$$f'(k) = \sum_{i=0}^k 2^i = 2^{k+1} - 1$$↵
↵
For any given $n$, let $b$ be the maximum integer such that $l \le n \le r$, where $l = f'(b)$ and $r = f'(b+1)$. The state transition is given by:↵
↵
↵
$$f(n) = \min(b + f(n - l + 1) + 1,\; b + 1 + r - n)$$↵
↵
### 2. Prefix Sums $f''(x, y)$ and Pivot $k'$↵
↵
Define the prefix sum function:↵
↵
↵
$$f''(x, y) = \sum_{i=x}^y f(i)$$↵
↵
Let $S$ be the ordered set of boundary values such that $f(S_i) = i$:↵
↵
↵
$$S = \{ 2^k - 1 \mid k \in \mathbb{Z}^+ \} = \{1, 3, 7, 15, 31, \dots\}$$↵
↵
For an interval $(l, r)$ where $l = S_i$ and $r = S_{i+1}$, the size of the range is $l$. Within $(l, r)$, there exists a pivot $k'$ that splits the piecewise evaluation of $f(n)$:↵
↵
↵
$$f(n) = \begin{cases} b + f(n - l + 1) + 1 & \text{if } n \le k' \\ b + 1 + r - n & \text{if } n > k' \end{cases}$$↵
↵
### 3. Block Sum Expansions↵
↵
Using $k'$, the sum over the open interval $(l, r)$ expands to:↵
↵
↵
$$f''(l, r) = 2b + 1 + f''(l + 1, k') + f''(k' + 1, r - 1)$$↵
↵
↵
Alternatively:↵
↵
↵
$$f''(l, r) = f''(l, k') + f''(k' + 1, r) - 2$$↵
↵
The sub-segment sums can be evaluated as:↵
↵
↵
$$f''(k' + 1, r - 1) = (r - k' - 1) \left( b + 1 - \frac{k' - r}{2} \right)$$↵
↵
$$f''(l + 1, k') = (k' - l)(b + 1) + f''(1, k' - l)$$↵
↵
We recursively evaluate $f''(1, k' - l)$ by finding the largest boundary $m \in S$ such that $m \le k' - l$:↵
↵
↵
$$f''(1, k' - l) = f''(1, m) + f''(m + 1, k' - l)$$↵
↵
### 4. Memoization and Precomputation↵
↵
We precompute the prefix sums for the first 60 boundaries:↵
↵
↵
$$\text{memo}[i] = f''(1, S_i) \quad \text{for } 0 \le i \le 60$$↵
↵
An arbitrary query $f''(L, R)$ is resolved by decomposing it into $S$-bounded blocks:↵
↵
↵
$$f''(L, R) = f''(L, S_i) + \sum_{j=i}^{i+\beta-1} f''(S_j + 1, S_{j+1}) + f''(S_{i+\beta} + 1, R)$$↵
↵
**Pivot Searching ($k'$):**↵
Let $h = r - k'$. The block size grows at a rate of $2\times$, and $h$ grows at a rate of $\sim \mathcal{O}(\log^2(\text{block size}))$. Because $h$ strictly increases per block (i.e., for block $b$ and block $b-1$, $h_b > h_{b-1}$), we can find the new pivot $k'$ by scanning starting from $r - h_{b-1}$. We memoize these pivots:↵
↵
↵
$$\text{kmemo}[i] = k'_i \quad \text{for } 0 \le i \le 60$$↵
↵
### 5. Complexity Analysis↵
↵
**Cost to compute `memo`:**↵
↵
↵
$$\approx \sum_{i=0}^{60} \log_2(2^i - 1) \approx \sum_{i=0}^{60} i = \frac{60 \times 61}{2} = 1830$$↵
↵
**Cost to compute `kmemo`:**↵
↵
↵
$$\approx \log_2^2(2^{59} - 1) \times \log_2(10^{18})$$↵
↵
$$\approx \log_2^2(2^{59}) \times 18 \log_2(10)$$↵
↵
$$\approx (59)^2 \times 60 = 3481 \times 60 = 208860$$↵
↵
**Total Precomputation Cost:**↵
↵
↵
$$\le 1830 + 208860 = 210690 \text{ operations}$$↵
↵
↵
↵
↵
↵
<spoiler summary="Click here to see my original raw notes/math">↵
f(n) optimization:↵
↵
f'(k) = ∑ᵢ₌₀ᵏ 2 ^ k↵
↵
if n is such that ↵
max(l) <= n <= min(r)↵
and l = f'(b) and r = f'(b + 1)↵
We choose b such that, b is a k in which f'(k) is the greatest k due to which, f'(k) is still lesser than n.↵
↵
f(n) = min(b + f(n — l + 1) + 1, b + 1 + r — n)↵
↵
↵
f''(x, y) optimization:↵
↵
f''(x, y) = ∑ᵢ₌ₓʸ f(i)↵
↵
S = {⍵ᵢ ∈ ⍵ ∩ ℤ | f(f'(⍵ᵢ)) = ⍵ᵢ}↵
i.e {1, 3, 7, 15, 31} ⊂ S | 2ᵏ — 1 ∈ S↵
f(2ᵏ — 1) = k↵
↵
Assuming S is an ordered set.↵
↵
l = Sᵢ, r = Sᵢ₊₁ ↵
↵
The no. of numbers in the range (l, r) is l.↵
↵
Pick a number k' in the range of (l, r) such that ↵
↵
┌ n ≤ k' : b + f(n - l + 1) + 1↵
f(n) = ┤↵
└ n > k' : b + 1 + r — n↵
↵
for n ∈ (l, r)↵
↵
f''(l, r) = 2b + 1 + f''(l + 1, k') + f''(k' + 1, r — 1) ↵
or ↵
f''(l, r) = f''(l, k') + f''(k' + 1, r) — 2↵
↵
∴ f''(k' + 1, r — 1) = (r — k' — 1) (b + 1 — (k' — r)/2)↵
f''(l + 1, k') = (k' — l) (b + 1) + f''(1, k' — l)↵
↵
f''(1, k' — l) = f''(1, m) + f''(m + 1, k' — l)↵
↵
We pick m such that m ∈ S and m = f'(c), m is the greatest Sᵢ; m <= k' — l.↵
↵
We can further memo ↵
↵
⨁ᵢ₌₀⁶⁰ memo[f'(i)] = f''(1, f'(i))↵
↵
f''(left, right) = f''(left, Sᵢ) + f''(Sᵢ₊₁ + 1, Sᵢ₊₂) + ... + f''(Sᵢ₊ᵦ + 1, right)↵
↵
Growth rate of k' for each block, block size grows at the rate of 2x, r — k' grows at the rate ~log²(block size). Also r — k' for each block strictly increases, therefore the if for block b — 1, r — k' = h, for block b, r — k' = h'↵
↵
h' > h↵
↵
We can scan from r — h till we get the k' for new block b, total cost for compute is the r — h of the largest block.↵
↵
⨁ᵢ₌₀⁶⁰ kmemo[i] = k'↵
↵
All of this is precomputed.↵
↵
Cost of computing memo ~= ∑ᵢ₌₀⁶⁰ log(2ⁱ — 1)↵
= ∑ᵢ₌₀⁶⁰ log(2ⁱ)↵
= ∑ᵢ₌₀⁶⁰ i * log(2)↵
= ∑ᵢ₌₀⁶⁰ i↵
= (60 * 61) / 2↵
= 1830↵
↵
Cost of compute of kmemo ~= log²(2⁵⁹ — 1) * log(10¹⁸)↵
= log²(2⁵⁹) * 18 * log(10)↵
= ((59)(log²(2)))² * 60↵
= 3481 * 60↵
= 208860↵
↵
Total Precompute Cost <= 1830 + 208860↵
= 210690↵
</spoiler>↵
↵
