An approach to 1129 D2

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	heuristica	3322
10	maroonrk	3312

#	User	Contrib.
1	Qingyu	157
2	nik_exists	151
3	maspy	149
4	AmShZ	144
5	Um_nik	143
6	Errichto	139
7	adamant	136
8	BledDest	133
9	maroonrk	132
10	Proof_by_QED	131

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 \gt 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 \gt 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}$$$

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

Comments (2)

Write comment?

k.shivaram252

48 minutes ago, hide # |

Auto comment: topic has been updated by k.shivaram252 (previous revision, new revision, compare).

→ Reply

28 minutes ago, hide # |

← Rev. 2 →

I will code this monstrosity tomorrow, do let me know if there are any mistakes in my math/logic and if my proof wasn't sufficient to make the assumptions I made.