Proposed Solution

Task. Little Cyan Fish starts at $a_0$ on a number line; his home is at $0$. He must visit $a_1,a_2,\dots,a_n$ in this order. Walking costs $1$ per unit; teleporting to the home and moving the home to the current position are free. Minimize the total walking distance. Constraints: $n\le 5\cdot 10^5$, $|a_i|\le 10^9$, $\sum n\le 5\cdot 10^5$.

What is proved and what is not. The reduction of the process to a DP over the home position is a model that we validated against an exhaustive shortest-path search (Section 1) but did not prove. Everything from the recurrence in Section 2 down to the structure of the DP function (Lemmas 1–4) is proved. The implementation details of the data structure (treap with lazy tags) and the amortized running time are only tested, not proved. We say this up front so the empirical parts are not mistaken for theorems.

1. The model

Consider the step from $x=a_i$ to $y=a_{i+1}$, and let $h$ be the current home. We use the following model of one step.

• Either walk from $x$ to $y$ directly (cost $|x-y|$), or first teleport to $h$ and walk from $h$ to $y$ (cost $|h-y|$).
• While walking, the home can be moved to any point of the walked segment. So after the step the home is either the old $h$ or any point of the walked segment ($[x,y]$ in the first case, $[h,y]$ in the second).
• At the very beginning the fish may keep the home at $0$ or move it to $a_0$ for free.

Detours (walking past the target to drop the home there and coming back), partial walks followed by a teleport, and several teleports per step are not part of the model: informally, a partial walk before a teleport is wasted, because the home cannot be both kept at $h$ and moved, and a detour to a point outside the walked segment pays for its length twice. We did not prove that these never help. Instead we checked the model against a Dijkstra search over the states (index, position, home) on a small integer grid that does allow arbitrary moves, detours included: they agreed on all of about $400$ random instances (positions in $[-10,10]$, up to $6$ steps).

2. Backward DP

Write $[u,v]$ for the closed segment between two points (in either order). Let $W_i(h)$ be the minimum remaining cost when the fish stands at $a_i$ with the home at $h$. Then $W_n\equiv 0$, and for $i<n$, with $x=a_i$, $y=a_{i+1}$, $d=|x-y|$ and $$M=\min_{p\in[x,y]}W_{i+1}(p),$$ the model gives directly $$W_i(h)=\min\Bigl(\,d+\min\bigl(W_{i+1}(h),M\bigr),\ \ |h-y|+\min_{p\in[h,y]}W_{i+1}(p)\Bigr).$$ The first term is "walk from $x$": the home stays at $h$ or moves anywhere in $[x,y]$. The second is "teleport to $h$, then walk to $y$": the home stays at $h$ or moves anywhere in $[h,y]$ (note that $h\in[h,y]$). The answer is $$\min\bigl(W_0(0),\,W_0(a_0)\bigr).$$ Since the second term contains $h$ itself, both terms are needed in this form. Write $W'=W_{i+1}$, let $G(h)=\min_{p\in[h,y]}W'(p)$ (a running minimum started at $y$), and let $F(h)=|h-y|+G(h)$. Then $$W_i(h)=\min\bigl(W'(h)+d,\ d+M,\ F(h)\bigr).\tag{1}$$

Lemma 1. $W_i$ is $1$-Lipschitz for every $i$.

Proof. By induction; $W_n\equiv0$. Assume $W'$ is $1$-Lipschitz. The function $h\mapsto W'(h)+d$ and the constant $d+M$ are $1$-Lipschitz, and so is their minimum. For $F$: on each side of $y$, moving $h$ away from $y$ by $\delta$ increases $|h-y|$ by exactly $\delta$ and decreases the running minimum $G$ by at most $\delta$ (because $W'$ is $1$-Lipschitz), so $F$ is non-decreasing away from $y$ with slope in $[0,1]$, and $F(y)=W'(y)$. For $h_1<y<h_2$ this gives $F(y)\le F(h_j)\le F(y)+|h_j-y|$, hence $|F(h_1)-F(h_2)|\le\max_j|h_j-y|\le|h_1-h_2|$. A minimum of $1$-Lipschitz functions is $1$-Lipschitz. $\square$

3. Structure of one step

By symmetry ($h\mapsto -h$) assume $x<y$. Let $x_r=y+d$ be the reflection of $x$ in $y$ and let $J=[x,x_r]$ be the window. Put $\mathrm{cap}=d+M$.

Lemma 2 (shape of $W_i$).

• (a) $W_i\le\mathrm{cap}$ everywhere, and $W_i(x)=\mathrm{cap}$; so $\mathrm{cap}$ is the maximum of $W_i$.
• (b) For $h\in J$: $W_i(h)=\min(\mathrm{cap},F(h))$.
• (c) For $h<x$: $W_i(h)=\min(W'(h)+d,\ \mathrm{cap})$.
• (d) For $h>x_r$: $W_i(h)=\min\bigl(W'(h)+d,\ \mathrm{cap},\ C(h)\bigr)$, where $C(h)=F(x_r)+(h-x_r)$.

Proof. (a) is clear from (1); moreover $F(x)=d+M=\mathrm{cap}$ and $W'(x)+d\ge M+d$, so $W_i(x)=\mathrm{cap}$.

(b) For $|h-y|\le d$, taking $p=h$ in $G$ gives $F(h)\le |h-y|+W'(h)\le W'(h)+d$, so the first term of (1) is redundant.

(c) Let $h<x$. Then $y-h=d+(x-h)$ and $G(h)=\min\bigl(\min_{[h,x]}W',\,M\bigr)$. If $G(h)=M$ then $F(h)\ge d+M=\mathrm{cap}$. Otherwise the minimum is $W'(p)$ for some $p\in[h,x]$, and by Lemma 1 $W'(h)\le W'(p)+(x-h)$, so $F(h)=d+(x-h)+W'(p)\ge W'(h)+d$. In both cases $F(h)\ge\min(\mathrm{cap},W'(h)+d)$, which makes $F$ redundant in (1).

(d) Let $h>x_r$. First, $C(h)=(h-y)+G(x_r)\ge(h-y)+G(h)=F(h)$, since the running minimum can only decrease further out. Second, we claim $F(h)\ge\min(W'(h)+d,\ C(h))$. If $G(h)=G(x_r)$ then $F(h)=C(h)$. Otherwise the minimum over $[y,h]$ is attained at some $p^{\ast}\in(x_r,h]$, so $p^{\ast}-y>d$ and, by Lemma 1, $W'(h)+d\le W'(p^{\ast})+(h-p^{\ast})+d< W'(p^{\ast})+(h-y)=F(h)$. The first inequality gives that adding $C$ to the minimum in (1) changes nothing, and the second that removing $F$ does not either. $\square$

So one step does the following to the function: it adds $d$ everywhere, caps it at $d+M$, replaces the window $J$ by the capped funnel $F$, and, beyond the far end $x_r$, overwrites the old function by the line $C$ of slope $+1$ wherever that line is lower. (The case $x>y$ is the mirror image.) Two consequences are used by the implementation.

• The value $M$ is exactly the running minimum $G$ evaluated at the near end $x$ of the window, so it comes for free from scanning the funnel.
• By (a), the next step (backward in time) is centered at $y'=a_i=x$, a point where the current function equals its global maximum.

Lazy form. Store a function $S$ together with two scalars and let $W=\min(S+\mathrm{off},\ \mathrm{cap})$. Because $W'\le\mathrm{cap}'$ we have $M\le\mathrm{cap}'$, hence $\mathrm{cap}=d+M\le\mathrm{cap}'+d$, and therefore outside the window $$\min(W'+d,\mathrm{cap})=\min(S+\mathrm{off}+d,\ \mathrm{cap}'+d,\ \mathrm{cap})=\min(S+(\mathrm{off}+d),\ \mathrm{cap}).$$ So "add $d$ and cap" is just $\mathrm{off}\leftarrow\mathrm{off}+d$, $\mathrm{cap}\leftarrow d+M$, with no work on $S$. Only the window and the cone region beyond it are rewritten.

4. Computing the funnel

Scan outward from $y$ over a radius $d$ with a running minimum $m$ (initially $W'(y)$) and let $t$ be the distance from $y$. Then $F=t+\mathrm{RM}(t)$, where $\mathrm{RM}$ is the running minimum of $W'$. Split the scanned part of $W'$ into maximal monotone runs.

Lemma 3. On a run where $W'$ is non-decreasing (in scan direction) $F=t+m$, a line of slope $+1$, and $m$ does not change. On a run where $W'$ is non-increasing, the part with $W'\ge m$ also gets $F=t+m$, and the part with $W'<m$ (the records) gets $F=t+W'$; afterwards $m$ becomes the value at the end of the run.

Proof. Immediate from $F=t+\mathrm{RM}$ and the definition of the running minimum. $\square$

So on every run we either replace a piece of the function by a single line, or add the ramp $t$ (a linear function) to a whole stretch of segments. The second operation is a range add of a linear function, which a lazy tag handles without visiting the segments. This matters because the function $W_i$ can have $\Theta(n)$ genuine breakpoints, for example a long staircase created by inputs whose values drift linearly; a solution that scans the segments of the window explicitly is quadratic on such inputs.

The part beyond the far end $x_r$ is handled as in Lemma 2(d). Let $F_{\mathrm{end}}=F(x_r)=d+m_{\mathrm{end}}$. If $F_{\mathrm{end}}\ge d+M$ the cone is never below the cap and is ignored. Otherwise the segments right after $x_r$ are removed one by one while they lie above the cone, and the cone segment is inserted. Where the cone matters, the true function $W'+d$ is $1$-Lipschitz and the cone has slope $1$, so once $W'+d$ falls below the cone it stays below; the removal therefore stops at a single crossing point.

5. Implementation

The function $S$ is stored as a sequence of segments $[\mathrm{lo},\mathrm{hi})$ carrying a line $s\cdot h+c$ with slope $s\in\{-1,0,1\}$, in a treap ordered by position. Coordinates and values are doubled, so that the peaks of the function (which can sit at half-integers) are integral.

• Lazy tags. (i) add a linear function: $s\leftarrow s+\alpha$, $c\leftarrow c+\beta$ on a whole subtree; (ii) mirror a subtree ($h\mapsto-h$: reverse the order, $[\mathrm{lo},\mathrm{hi})\mapsto[-\mathrm{hi},-\mathrm{lo})$, $s\mapsto-s$). The mirror lets the left side of $y$ be processed by the same code as the right side.
• Aggregates. Per subtree: minimum and maximum slope, the first and last line, and the largest upward jump between adjacent segments in each direction (jumps exist only in the hidden region above $\mathrm{cap}$, but they must still be respected when delimiting runs). These let us find the end of a monotone run, and the point where a run drops below $m$, by a descent in $O(\log n)$.
• One step. Split the treap at $y-d$, $y$ and $y+d$; process the right and the mirrored left part run by run (Lemma 3), merging adjacent equal lines; take $M$ from the near side; handle the cone on the far side; merge everything back; update $\mathrm{off}$ and $\mathrm{cap}$.
• Answer. After processing $i=n-1,\dots,0$, evaluate the function at $0$ and at $a_0$ and take the minimum (halve the doubled value). All quantities are at most about $2\cdot10^{15}$ in the doubled scale, so $64$-bit integers suffice.

6. Complexity

Each step performs $O(1)$ splits and merges plus one treap operation per scanned run, each $O(\log n)$. An informal amortization argument: after a step, each side of $y$ inside the window is a single funnel that is non-decreasing away from $y$, and the next step is centered at the window end and scans toward $y$, along which this funnel is one non-increasing run; alternating pieces met further out are collapsed into single segments as they are scanned. So the number of runs created per step is $O(1)$ and the work for scanned runs is paid by their destruction, which suggests $O(n\log n)$ in total. We have not proved this bound. What we measured: on a hill-climb that maximized the scanned pieces, the work per step stayed near $5$ pieces independent of $n$ ($n=500$ versus $2000$), and for $n=5\cdot10^5$ the worst of several dozen input families (random, random walks, zig-zags with growing and shrinking amplitude, sawtooth, constants, alternating two values, and sparse alphabets with linear drift) took $1.7$ s, with memory below $75$ MB.

7. Validation performed

• The model of Section 1 against exhaustive Dijkstra search with detours allowed (about $400$ random small instances): no mismatch.
• The backward recurrence (1) in its dense form against the same search (another $500$ random small instances): no mismatch.
• The data-structure solution against a dense $O(n\cdot\text{range})$ implementation of (1): more than $10^4$ random cases (several generators, mostly $n\le300$ and a few with $n$ up to $1500$, coordinates up to $10^5$), no mismatch.
• The data-structure solution against an independent, simpler implementation of the same recurrence based on an ordered map of segments, at $n=2\cdot10^4$–$3\cdot10^4$ and on the families with linear drift: identical outputs.
• Sanitizers (address and undefined behaviour) were clean on inputs with $n=5\cdot10^5$.

The four samples give $0,10,6,8$.