The ant starts at \(A(0,1)\) and must reach \(B(d,1)\), where \(d\in 2\mathbb{Z}_{>0}\). Every move is a straight segment between lattice points, always going forward in \(x\). If a segment starts at height \(y_0\) and ends at height \(y_1\), then its speed is
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
The objective is to minimize the total travel time; that minimum is denoted by \(F(d)\). The published checkpoints are \(F(4)=2.960516287\), \(F(10)=4.668187834\), and \(F(100)=9.217221972\). The real target is \(F(10000)\), so a brute-force search over all lattice paths is far too large.
The implementations solve the problem on the left half of the picture first and then mirror that half-path. Write
$$w=\frac d2.$$
The task is therefore to understand good paths from \((0,1)\) to the vertical line \(x=w\), and then double the best half-cost.
For one segment from \((x_0,y_0)\) to \((x_1,y_1)\), let
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$$
The travel time is \(L/v\). It is convenient to write it with a reciprocal-speed factor
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
Then every segment contributes
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1).$$
When \(y_1\to y_0\), the second branch tends to \(1/y_0\), so the horizontal and non-horizontal cases fit together continuously. For \(y_0\ne y_1\), the speed is the logarithmic mean of \(y_0\) and \(y_1\), and \(\psi\) is its reciprocal.
The endpoints \(A(0,1)\) and \(B(d,1)\) are symmetric with respect to the line \(x=w\). Reflecting a path in that line preserves Euclidean lengths and also preserves the pair of endpoint heights of every reflected segment, so it preserves travel time as well.
The C++, Python, and Java implementations therefore search for a left half-path from \((0,1)\) to some midpoint \((w,Y)\), then reflect it to obtain a full path from \(A\) to \(B\). Under that model,
$$F(d)=2\min_{1\le Y\le w} D(w,Y),$$
where \(D(x,y)\) denotes the minimum time to reach \((x,y)\) on the left half. The searched half-path is restricted to nondecreasing heights, so the reflected second half automatically supplies the matching descent back to \(y=1\).
Set the base state
$$D(0,1)=0.$$
For every lattice point \((x,y)\) with \(0\le x\le w\) and \(1\le y\le w\), the half-path cost is obtained from an earlier point \((x_0,y_0)\) with \(x_0\le x\) and \(y_0\le y\):
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
This is a shortest-path computation on an acyclic state graph: \(x\) never decreases, and on the searched half-path the height never decreases either. Any state on the boundary \(x=w\) is already a complete half-solution and yields the full candidate time \(2D(w,y)\).
For \(d=4\), we have \(w=2\). A natural half-path is
$$ (0,1)\to(1,2)\to(2,2). $$
The first segment has length \(\sqrt2\) and reciprocal speed
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$$
So its time is \(\sqrt2\ln 2\). The second segment is horizontal at height \(2\), length \(1\), hence time \(1/2\). The half-cost is therefore
$$D(2,2)=\sqrt2\ln 2+\frac12.$$
Reflecting this half-path gives the full path
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1), $$
and thus
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$$
which matches the stated checkpoint \(2.960516287\). This is a useful small-scale example of the general recurrence.
If we allowed every state \((x,y)\) to examine every predecessor \((x_0,y_0)\), then there would be \(O(w^2)\) states and up to \(O(w^2)\) predecessors per state. For \(d=10000\), we have \(w=5000\), so a literal implementation of the full recurrence would be far too slow.
The implementations therefore keep the same segment-cost formula and the same half-path DP idea, but prune the search to a narrow region where near-optimal states are expected to lie.
The reference curve used by the implementations is the quarter-circle
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w,$$
which is the left branch of the circle centered at \((w,0)\) with radius \(w\).
Only source states near that circle are expanded, namely those satisfying
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$$
For each target height \(y\), destination \(x\)-coordinates are restricted to a narrow horizontal band:
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
In the released implementations, the default values are \(W=30\) and \(\varepsilon=0.5\). This is not the unrestricted theoretical DP; it is a numerically guided pruning strategy. However, it reproduces all published checkpoints and is exactly the algorithm used by the C++, Python, and Java implementations.
The C++, Python, and Java implementations allocate a table of best half-path times for all lattice states with \(0\le x\le w\) and \(1\le y\le w\). Every entry starts at infinity except the initial state \((0,1)\), whose cost is \(0\).
They then precompute two geometric ingredients: \(\ln y\) for each height \(y\), and the reference-arc position \(x_{\mathrm{arc}}(y)\). Precomputing logarithms is important because the reciprocal-speed factor is evaluated repeatedly for many pairs of heights.
Next, for each horizontal position \(x_0\), the implementation precomputes the heights \(y_0\) that lie inside the thin annulus around the reference circle. Those lattice points are treated as the expandable source states.
When one source state is expanded, the implementation sweeps through all target heights \(y\ge y_0\). For each such \(y\), it evaluates the reciprocal-speed factor once, computes the admissible horizontal band around the reference arc, and relaxes all destinations \((x,y)\) inside that band.
Whenever a relaxation reaches the boundary \(x=w\), the best half-answer seen so far is updated. After all source states have been processed, the final result returned is exactly twice that best half-cost, formatted to nine decimal places.
Let \(w=d/2\), and let \(W\) be the horizontal band width. The unpruned monotone DP has \(O(w^2)\) states and \(O(w^2)\) predecessor checks per state, so its naive time complexity is \(O(w^4)\), with \(O(w^2)\) memory.
In the implemented version, the annulus around the reference circle has constant thickness, so it contains only \(O(w)\) relevant source states. Each expanded source considers \(O(wW)\) destination cells, because it scans all target heights and only a band of width \(O(W)\) in the horizontal direction. That gives a practical running cost of roughly \(O(w^2W)\), while memory remains \(O(w^2)\).
For the actual target \(d=10000\), we have \(w=5000\) and the default \(W=30\), which is why the pruned method is feasible whereas the unrestricted DP is not.
Die Ameise startet in \(A(0,1)\) und muss \(B(d,1)\) erreichen, wobei \(d\in 2\mathbb{Z}_{>0}\) gilt. Jeder Zug ist ein gerades Streckenstück zwischen Gitterpunkten und bewegt sich nur nach rechts in \(x\)-Richtung. Beginnt ein Segment auf der Höhe \(y_0\) und endet auf der Höhe \(y_1\), dann ist die Geschwindigkeit
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
Gesucht ist die minimale Gesamtzeit \(F(d)\). Als Kontrollwerte sind \(F(4)=2.960516287\), \(F(10)=4.668187834\) und \(F(100)=9.217221972\) gegeben. Für \(F(10000)\) ist vollständiges Durchprobieren aller Gitterwege ausgeschlossen.
Die Implementationen lösen zunächst nur die linke Hälfte der Bahn und spiegeln diese Hälfte anschließend. Wir setzen
$$w=\frac d2.$$
Damit reduziert sich die Aufgabe auf gute Wege von \((0,1)\) bis zur Geraden \(x=w\); die beste Halbkostenfunktion wird am Ende verdoppelt.
Für ein Segment von \((x_0,y_0)\) nach \((x_1,y_1)\) definieren wir
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$$
Die Reisezeit ist \(L/v\). Zweckmäßig ist die Schreibweise über einen Kehrwert-Faktor der Geschwindigkeit:
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
Dann trägt jedes Segment den Betrag
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1)$$
zur Gesamtzeit bei. Für \(y_1\to y_0\) geht der zweite Ast gegen \(1/y_0\), also passen horizontaler und nicht-horizontaler Fall stetig zusammen. Bei \(y_0\ne y_1\) ist die Geschwindigkeit das logarithmische Mittel von \(y_0\) und \(y_1\).
Die Punkte \(A(0,1)\) und \(B(d,1)\) sind spiegelsymmetrisch zur Geraden \(x=w\). Spiegelung an dieser Geraden erhält die euklidischen Längen aller Segmente und auch die zugehörigen Endhöhen; damit bleibt die Reisezeit erhalten.
Die C++, Python- und Java-Implementationen suchen deshalb einen optimalen linken Halbweg von \((0,1)\) zu einem Punkt \((w,Y)\) und spiegeln ihn. In diesem Modell gilt
$$F(d)=2\min_{1\le Y\le w} D(w,Y),$$
wobei \(D(x,y)\) die minimale Zeit bis \((x,y)\) auf der linken Hälfte bezeichnet. In der durchsuchten Halbspur darf die Höhe nur gleich bleiben oder steigen; nach der Spiegelung entsteht der absteigende Rückweg zu \(y=1\) automatisch.
Der Startzustand ist
$$D(0,1)=0.$$
Für jeden Gitterpunkt \((x,y)\) mit \(0\le x\le w\) und \(1\le y\le w\) ergibt sich der beste Halbweg aus einem früheren Punkt \((x_0,y_0)\) mit \(x_0\le x\) und \(y_0\le y\):
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
Das ist ein Kürzeste-Wege-Problem auf einem azyklischen Zustandsgraphen: \(x\) fällt nie, und in der gesuchten Halbspur fällt auch \(y\) nie. Jeder Zustand mit \(x=w\) ist bereits eine vollständige Halblösung und liefert den Kandidaten \(2D(w,y)\) für die Gesamtzeit.
Für \(d=4\) ist \(w=2\). Eine natürliche Halbspur lautet
$$ (0,1)\to(1,2)\to(2,2). $$
Das erste Segment hat Länge \(\sqrt2\) und den Kehrwert-Faktor
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$$
Seine Zeit ist also \(\sqrt2\ln 2\). Das zweite Segment ist horizontal auf Höhe \(2\), hat Länge \(1\) und kostet deshalb \(1/2\). Somit ist die Halbzeit
$$D(2,2)=\sqrt2\ln 2+\frac12.$$
Spiegelt man diese Halbspur, erhält man den ganzen Weg
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1), $$
und damit
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$$
also genau den veröffentlichten Kontrollwert \(2.960516287\).
Wenn jeder Zustand \((x,y)\) alle möglichen Vorgänger \((x_0,y_0)\) prüfen müsste, gäbe es \(O(w^2)\) Zustände und bis zu \(O(w^2)\) Vorgänger je Zustand. Bei \(d=10000\) ist \(w=5000\), daher wäre eine wortwörtliche Umsetzung der vollständigen Rekurrenz zu langsam.
Die Implementationen behalten deshalb dieselbe Kostenformel und dieselbe Halbweg-Idee bei, beschränken die Suche aber auf ein schmales Gebiet, in dem gute Zustände numerisch zu erwarten sind.
Als Referenzkurve dient der Viertelkreis
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w,$$
also der linke Ast des Kreises mit Mittelpunkt \((w,0)\) und Radius \(w\).
Erweitert werden nur Quellzustände nahe an diesem Kreis, nämlich solche mit
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$$
Für jede Zielhöhe \(y\) werden die zulässigen \(x\)-Koordinaten zusätzlich auf ein schmales horizontales Band eingeschränkt:
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
In den ausgelieferten Implementationen sind die Standardwerte \(W=30\) und \(\varepsilon=0.5\). Das ist nicht die unbeschränkte theoretische DP, sondern eine numerisch motivierte Beschneidung. Sie reproduziert jedoch alle veröffentlichten Kontrollwerte und entspricht exakt dem tatsächlich implementierten Verfahren.
Die C++, Python- und Java-Implementationen legen zunächst eine Tabelle der besten Halbzeiten für alle Gitterzustände mit \(0\le x\le w\) und \(1\le y\le w\) an. Alle Einträge werden mit Unendlich initialisiert, außer dem Startzustand \((0,1)\), der den Wert \(0\) erhält.
Anschließend werden zwei geometrische Hilfsreihen vorab berechnet: \(\ln y\) für jede Höhe \(y\) und die Referenzbogen-Position \(x_{\mathrm{arc}}(y)\). Die Vorberechnung der Logarithmen spart Arbeit, weil der Kehrwert-Faktor der Geschwindigkeit für sehr viele Höhenpaare gebraucht wird.
Danach bestimmt die Implementierung für jede horizontale Position \(x_0\) alle Höhen \(y_0\), die in dem dünnen Ring um den Referenzkreis liegen. Nur diese Gitterpunkte werden später als expandierbare Quellen behandelt.
Wird ein solcher Quellzustand verarbeitet, läuft der Code alle Zielhöhen \(y\ge y_0\) durch. Für jede dieser Höhen berechnet er den Kehrwert-Faktor genau einmal, bestimmt das zulässige horizontale Band um den Referenzbogen und entspannt dann alle Zielzellen \((x,y)\) innerhalb dieses Bandes.
Sobald eine Relaxation die Gerade \(x=w\) erreicht, wird die beste bisher gefundene Halbzeit aktualisiert. Nach Abschluss aller Relaxationen gibt die Implementierung genau das Doppelte dieser besten Halbzeit mit neun Nachkommastellen aus.
Sei \(w=d/2\) und \(W\) die Breite des horizontalen Bandes. Die unbeschnittene monotone DP besitzt \(O(w^2)\) Zustände und \(O(w^2)\) mögliche Vorgänger pro Zustand. Daraus folgt naiv \(O(w^4)\) Zeit bei \(O(w^2)\) Speicher.
In der implementierten Version hat der Ring um den Referenzkreis konstante Dicke und enthält daher nur \(O(w)\) relevante Quellzustände. Jede expandierte Quelle betrachtet \(O(wW)\) Zielzellen, weil alle Zielhöhen geprüft werden, horizontal aber nur ein Band der Breite \(O(W)\). Praktisch ergibt das ungefähr \(O(w^2W)\) Laufzeit bei weiterhin \(O(w^2)\) Speicher.
Für das eigentliche Ziel \(d=10000\) ist \(w=5000\), und der Standardwert \(W=30\) macht genau diesen beschnittenen Ansatz praktikabel.
Karınca \(A(0,1)\) noktasından başlar ve \(B(d,1)\) noktasına ulaşmak zorundadır; burada \(d\in 2\mathbb{Z}_{>0}\) bir çift pozitif tamsayıdır. Her hareket, kafes noktaları arasında çizilen doğru parçasıdır ve \(x\) yönünde geri gitmez. Bir parça \(y_0\) yüksekliğinde başlayıp \(y_1\) yüksekliğinde bitiyorsa hızı
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
Toplam süreyi en aza indiren değer \(F(d)\) olarak tanımlanır. Verilen kontrol değerleri \(F(4)=2.960516287\), \(F(10)=4.668187834\) ve \(F(100)=9.217221972\) şeklindedir. Asıl hedef \(F(10000)\) olduğundan, tüm kafes yollarını doğrudan denemek mümkün değildir.
Uygulamalar önce şeklin sol yarısını çözüp sonra bu yarıyı simetrik olarak yansıtır. Şunu yazalım:
$$w=\frac d2.$$
Böylece görev, \((0,1)\) noktasından \(x=w\) doğrusu üzerindeki bir noktaya kadar en iyi yarım yolu bulmaya indirgenir; sonunda en iyi yarım maliyet ikiyle çarpılır.
\((x_0,y_0)\) ile \((x_1,y_1)\) arasındaki bir doğru parçası için
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}$$
tanımlarını yapalım. Geçiş süresi \(L/v\) olur. Bunu karşılıklı hız çarpanı ile yazmak daha elverişlidir:
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
O zaman her parça
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1)$$
süresini ekler. \(y_1\to y_0\) limitinde ikinci ifade \(1/y_0\)'a gider; yani yatay ve yatay olmayan durumlar aynı sürekli modelin iki görünümüdür. \(y_0\ne y_1\) olduğunda hız, \(y_0\) ile \(y_1\)'in logaritmik ortalamasıdır.
\(A(0,1)\) ve \(B(d,1)\) noktaları \(x=w\) doğrusuna göre simetriktir. Bir yolu bu doğruya göre yansıtmak, her parçanın Öklid uzunluğunu ve uç yükseklik çiftini korur; dolayısıyla süre de değişmez.
Bu yüzden C++, Python ve Java uygulamaları \((0,1)\) noktasından \((w,Y)\) biçimindeki bir orta noktaya kadar en iyi sol yarım yolu arar, ardından bunu yansıtır. Bu modelde
$$F(d)=2\min_{1\le Y\le w} D(w,Y)$$
olur; burada \(D(x,y)\), sol yarıda \((x,y)\) noktasına ulaşma süresinin en küçüğüdür. Aranan yarım yolda yükseklik yalnızca sabit kalabilir veya artabilir; yansıtma yapıldığında ikinci yarı, \(y=1\)'e dönüş inişini otomatik olarak üretir.
Başlangıç durumu
$$D(0,1)=0$$
şeklindedir. \(0\le x\le w\) ve \(1\le y\le w\) için her \((x,y)\) durumu, \(x_0\le x\) ve \(y_0\le y\) olan daha eski bir \((x_0,y_0)\) durumundan gelir:
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
Bu, çevrimsiz bir durum grafı üzerindeki en kısa yol hesabıdır: \(x\) hiç azalmaz; aranan yarım yolda \(y\) de azalmaz. \(x=w\) sınırına ulaşan her durum, tam cevabın adayı olan \(2D(w,y)\) değerini üretir.
\(d=4\) olduğunda \(w=2\) elde edilir. Doğal bir yarım yol
$$ (0,1)\to(1,2)\to(2,2) $$
şeklindedir. İlk parçanın uzunluğu \(\sqrt2\) ve karşılıklı hız çarpanı
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2$$
olduğundan bu parçanın süresi \(\sqrt2\ln 2\) olur. İkinci parça yükseklik \(2\)'de yataydır; uzunluğu \(1\) olduğu için süresi \(1/2\)'dir. Demek ki yarım maliyet
$$D(2,2)=\sqrt2\ln 2+\frac12$$
olur. Bu yarım yol yansıtılınca tam yol
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1) $$
haline gelir ve
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots$$
elde edilir. Bu da verilen \(2.960516287\) kontrol değeriyle tam uyumludur.
Eğer her \((x,y)\) durumu bütün olası \((x_0,y_0)\) öncüllerini incelemek zorunda olsaydı, \(O(w^2)\) durum ve durum başına en çok \(O(w^2)\) geçiş olurdu. \(d=10000\) için \(w=5000\) olduğundan, tam bağıntının kelimesi kelimesine uygulanması çok yavaştır.
Bu yüzden uygulamalar aynı maliyet formülünü ve aynı yarım-yol fikrini korur, fakat aramayı en iyi durumların bulunmasının beklendiği dar bir geometrik bölgeyle sınırlar.
Kullanılan referans eğrisi şu çeyrek çemberdir:
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w.$$
Bu eğri, merkezi \((w,0)\) ve yarıçapı \(w\) olan çemberin sol koludur.
Sadece bu çembere yakın kaynak durumlar genişletilir:
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$$
Her hedef yüksekliği \(y\) için, izin verilen \(x\) değerleri ayrıca dar bir yatay banda kısıtlanır:
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
Yayınlanmış uygulamalarda varsayılan değerler \(W=30\) ve \(\varepsilon=0.5\)'tir. Bu, teorik olarak tam DP değildir; sayısal olarak yönlendirilmiş bir budama stratejisidir. Ancak bütün yayımlanmış kontrol değerlerini yeniden üretir ve üç uygulamanın gerçekten yaptığı hesap tam olarak budur.
C++, Python ve Java uygulamaları önce \(0\le x\le w\) ve \(1\le y\le w\) için en iyi yarım-yol sürelerini tutan bir tablo oluşturur. \((0,1)\) başlangıç durumu dışında bütün hücreler sonsuzla başlatılır; başlangıç hücresi \(0\) değerini alır.
Daha sonra iki geometrik yardımcı dizi önceden hesaplanır: her yükseklik için \(\ln y\) değeri ve referans yay üzerindeki \(x_{\mathrm{arc}}(y)\) konumu. Logaritmaların önceden hesaplanması önemlidir, çünkü karşılıklı hız çarpanı çok sayıda yükseklik çifti için tekrar tekrar kullanılır.
Sonraki adımda, her yatay konum \(x_0\) için ince çembersel halka içinde kalan yükseklikler \(y_0\) önceden listelenir. Daha sonra yalnızca bu kafes noktaları genişletilebilir kaynak durumlar olarak ele alınır.
Bir kaynak durum genişletildiğinde uygulama tüm \(y\ge y_0\) hedef yüksekliklerini dolaşır. Her bir \(y\) için karşılıklı hız çarpanı bir kez hesaplanır, referans yay çevresindeki izinli yatay bant belirlenir ve bu bant içindeki bütün \((x,y)\) hedefleri gevşetilir.
Bir gevşetme \(x=w\) sınırına ulaştığında, o ana kadarki en iyi yarım cevap güncellenir. Tüm kaynaklar işlendikten sonra döndürülen sonuç, bu en iyi yarım maliyetin tam iki katıdır ve dokuz ondalık basamakla yazdırılır.
\(w=d/2\) ve \(W\) yatay bant genişliği olsun. Budanmamış monoton DP, \(O(w^2)\) durum ve durum başına \(O(w^2)\) öncül denemesi içerir; dolayısıyla naif zaman maliyeti \(O(w^4)\), bellek maliyeti ise \(O(w^2)\)'dir.
Gerçekte kullanılan sürümde referans çember etrafındaki halka sabit kalınlıktadır; bu nedenle yalnızca \(O(w)\) kadar anlamlı kaynak durum içerir. Her kaynak, tüm hedef yüksekliklerini dolaşırken yatayda sadece \(O(W)\) genişliğinde bir bant gördüğü için yaklaşık \(O(wW)\) hedef hücre inceler. Böylece pratik çalışma maliyeti yaklaşık \(O(w^2W)\) olur; bellek ise \(O(w^2)\) kalır.
Asıl hedef \(d=10000\) için \(w=5000\) ve varsayılan \(W=30\) değerleri, tam DP yerine bu budanmış yöntemi uygulanabilir kılan ana nedendir.
La hormiga parte de \(A(0,1)\) y debe llegar a \(B(d,1)\), donde \(d\in 2\mathbb{Z}_{>0}\). Cada movimiento es un segmento recto entre puntos de la rejilla y siempre avanza en \(x\). Si un tramo empieza a altura \(y_0\) y termina a altura \(y_1\), su velocidad es
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
El objetivo es minimizar el tiempo total; ese mínimo se llama \(F(d)\). Los valores de control publicados son \(F(4)=2.960516287\), \(F(10)=4.668187834\) y \(F(100)=9.217221972\). Para \(F(10000)\), un recorrido exhaustivo de todas las trayectorias de la rejilla es inviable.
Las implementaciones resuelven primero la mitad izquierda del dibujo y luego la reflejan. Escribimos
$$w=\frac d2.$$
Así, la tarea consiste en encontrar un buen camino desde \((0,1)\) hasta la recta vertical \(x=w\), y después duplicar el mejor coste de media trayectoria.
Para un tramo que va de \((x_0,y_0)\) a \((x_1,y_1)\), definimos
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$$
El tiempo de viaje es \(L/v\). Resulta útil escribirlo mediante un factor de velocidad recíproca:
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
Entonces el aporte temporal de cada tramo es
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1).$$
Cuando \(y_1\to y_0\), la segunda rama tiende a \(1/y_0\), de modo que el caso horizontal y el no horizontal encajan de manera continua. Para \(y_0\ne y_1\), la velocidad dada por el enunciado es la media logarítmica de \(y_0\) y \(y_1\).
Los extremos \(A(0,1)\) y \(B(d,1)\) son simétricos respecto de la recta \(x=w\). Reflejar una trayectoria en esa recta preserva las longitudes euclidianas y también el par de alturas de cada segmento reflejado, por lo que el tiempo total se conserva.
Por eso las implementaciones en C++, Python y Java buscan una media trayectoria izquierda desde \((0,1)\) hasta algún punto \((w,Y)\), y luego la reflejan. En ese modelo,
$$F(d)=2\min_{1\le Y\le w} D(w,Y),$$
donde \(D(x,y)\) denota el tiempo mínimo para llegar a \((x,y)\) en la mitad izquierda. En la media trayectoria explorada, la altura solo puede mantenerse o subir; al reflejarla, la bajada de vuelta hasta \(y=1\) aparece automáticamente.
El estado base es
$$D(0,1)=0.$$
Para cualquier punto de la rejilla \((x,y)\) con \(0\le x\le w\) y \(1\le y\le w\), el mejor coste de media trayectoria proviene de un punto anterior \((x_0,y_0)\) con \(x_0\le x\) y \(y_0\le y\):
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
Se trata de un problema de camino más corto sobre un grafo acíclico: \(x\) nunca disminuye y, en la mitad explorada, \(y\) tampoco disminuye. Cualquier estado situado en la frontera \(x=w\) ya representa una solución completa para la mitad y produce el candidato total \(2D(w,y)\).
Si \(d=4\), entonces \(w=2\). Una media trayectoria natural es
$$ (0,1)\to(1,2)\to(2,2). $$
El primer segmento tiene longitud \(\sqrt2\) y factor recíproco
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$$
Por tanto, su tiempo es \(\sqrt2\ln 2\). El segundo segmento es horizontal a altura \(2\), tiene longitud \(1\) y cuesta \(1/2\). En consecuencia, el coste de la mitad es
$$D(2,2)=\sqrt2\ln 2+\frac12.$$
Al reflejarla obtenemos la trayectoria completa
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1), $$
y por ello
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$$
que coincide con el valor de control \(2.960516287\).
Si cada estado \((x,y)\) examinara todos sus predecesores posibles \((x_0,y_0)\), habría \(O(w^2)\) estados y hasta \(O(w^2)\) predecesores por estado. Para \(d=10000\), con \(w=5000\), una implementación literal de esa recurrencia sería demasiado costosa.
Las implementaciones conservan la misma fórmula de coste y la misma idea de media trayectoria, pero podan la búsqueda a una región estrecha donde se espera encontrar los estados casi óptimos.
La curva de referencia usada por las implementaciones es el cuarto de círculo
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w,$$
es decir, la rama izquierda del círculo de centro \((w,0)\) y radio \(w\).
Solo se expanden los estados fuente cercanos a ese círculo, concretamente los que satisfacen
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$$
Para cada altura destino \(y\), las coordenadas \(x\) permitidas se limitan además a una banda horizontal estrecha:
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
En las implementaciones publicadas, los valores por defecto son \(W=30\) y \(\varepsilon=0.5\). Esto no es la DP teórica sin restricciones, sino una poda guiada numéricamente. Aun así, reproduce todos los valores de control publicados y es exactamente el algoritmo que ejecutan las implementaciones en C++, Python y Java.
Las implementaciones en C++, Python y Java crean primero una tabla con los mejores tiempos de media trayectoria para todos los estados de la rejilla con \(0\le x\le w\) y \(1\le y\le w\). Todas las celdas se inicializan con infinito, salvo el estado inicial \((0,1)\), cuyo valor es \(0\).
Después precalculan dos ingredientes geométricos: \(\ln y\) para cada altura \(y\), y la posición \(x_{\mathrm{arc}}(y)\) del arco de referencia. Precalcular los logaritmos ahorra trabajo porque el factor de velocidad recíproca se reutiliza muchas veces.
A continuación, para cada posición horizontal \(x_0\), la implementación precalcula las alturas \(y_0\) que caen dentro del anillo delgado alrededor del círculo de referencia. Solo esos puntos de la rejilla se tratan luego como fuentes expansibles.
Cuando se expande una fuente, la implementación recorre todas las alturas destino \(y\ge y_0\). Para cada una calcula una sola vez el factor de velocidad recíproca, determina la banda horizontal permitida alrededor del arco y relaja todos los destinos \((x,y)\) que quedan dentro de esa banda.
Cada vez que una relajación alcanza la frontera \(x=w\), se actualiza la mejor respuesta parcial. Al terminar todas las expansiones, el valor devuelto es exactamente el doble del mejor coste de media trayectoria, impreso con nueve decimales.
Sea \(w=d/2\) y sea \(W\) el ancho de la banda horizontal. La DP monótona sin poda tiene \(O(w^2)\) estados y \(O(w^2)\) comprobaciones de predecesor por estado, por lo que su complejidad temporal ingenua es \(O(w^4)\), con \(O(w^2)\) memoria.
En la versión implementada, el anillo alrededor del círculo de referencia tiene grosor constante y por ello contiene solo \(O(w)\) estados fuente relevantes. Cada fuente expandida considera \(O(wW)\) celdas destino, porque recorre todas las alturas y solo una banda horizontal de anchura \(O(W)\). En la práctica esto da un coste cercano a \(O(w^2W)\), mientras que la memoria sigue siendo \(O(w^2)\).
Para el objetivo real \(d=10000\), tenemos \(w=5000\) y el valor por defecto \(W=30\), lo que hace viable la versión podada y no la recurrencia completa.
蚂蚁从 \(A(0,1)\) 出发，要走到 \(B(d,1)\)，其中 \(d\in 2\mathbb{Z}_{>0}\) 是正偶数。每一步都是两个格点之间的一条直线段，并且在 \(x\) 方向上只能向前。若一段路从高度 \(y_0\) 出发，到高度 \(y_1\) 结束，则速度定义为
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
我们要求的是最短总时间，记为 \(F(d)\)。题目给出的校验值是 \(F(4)=2.960516287\)、\(F(10)=4.668187834\)、\(F(100)=9.217221972\)。真正目标是 \(F(10000)\)，因此不可能把所有格点路径暴力枚举一遍。
这三个实现先求整条路径的左半部分，再把它关于中线镜像过去。设
$$w=\frac d2.$$
于是问题可以改写为：先找出从 \((0,1)\) 到直线 \(x=w\) 的最佳半程路径，再把这个半程代价乘以 \(2\)。
对于一段从 \((x_0,y_0)\) 到 \((x_1,y_1)\) 的直线，记
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$$
这一段的时间是 \(L/v\)。为了后续递推方便，可以把它改写为“长度乘以速度倒数因子”的形式：
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
那么单段时间就是
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1).$$
当 \(y_1\to y_0\) 时，第二个分支会趋于 \(1/y_0\)，所以水平段和非水平段其实属于同一个连续模型。若 \(y_0\ne y_1\)，题目中的速度正好等于 \(y_0\) 与 \(y_1\) 的对数平均，而 \(\psi\) 就是这个对数平均的倒数。
起点 \(A(0,1)\) 与终点 \(B(d,1)\) 关于直线 \(x=w\) 完全对称。把一条路径对这条直线做镜像，所有线段的欧氏长度不会改变，线段两端的高度对也不会改变，因此总时间也保持不变。
因此，C++、Python 和 Java 实现都只搜索左半边：从 \((0,1)\) 走到某个中点 \((w,Y)\)，然后把这段半程路径镜像到右边。这样就有
$$F(d)=2\min_{1\le Y\le w} D(w,Y),$$
其中 \(D(x,y)\) 表示左半程到达 \((x,y)\) 的最小时间。实现搜索的半程路径还额外要求高度单调不降，也就是中途可以持平或上升，但不下降；镜像之后，右半边自然就给出了从峰值回到 \(y=1\) 的下降部分。
初始状态是
$$D(0,1)=0.$$
对于任意格点 \((x,y)\)，其中 \(0\le x\le w\)、\(1\le y\le w\)，它的最佳半程代价来自某个更早的点 \((x_0,y_0)\)，满足 \(x_0\le x\) 且 \(y_0\le y\)：
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
这本质上是一个有向无环状态图上的最短路问题。因为在被搜索的半程里，\(x\) 只会增大，\(y\) 也只会保持不变或增大，所以不会形成需要回头的循环。任何到达边界 \(x=w\) 的状态，都已经构成了一条完整半程路径，并给出一个完整答案候选 \(2D(w,y)\)。
当 \(d=4\) 时，有 \(w=2\)。一个非常自然的半程路径是
$$ (0,1)\to(1,2)\to(2,2). $$
第一段长度为 \(\sqrt2\)，而它的速度倒数因子为
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$$
因此第一段用时是 \(\sqrt2\ln 2\)。第二段是在高度 \(2\) 上的水平线段，长度为 \(1\)，速度就是 \(2\)，所以用时 \(1/2\)。于是半程总代价为
$$D(2,2)=\sqrt2\ln 2+\frac12.$$
把这条半程路径关于 \(x=2\) 镜像，就得到完整路径
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1). $$
于是
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$$
与题目给出的校验值 \(2.960516287\) 完全一致。这个例子很好地说明了动态规划状态和对称拼接是如何配合工作的。
如果完全不做剪枝，那么每个状态 \((x,y)\) 都要检查所有可能前驱 \((x_0,y_0)\)。状态总数是 \(O(w^2)\)，而每个状态的前驱数量最多也是 \(O(w^2)\)，因此直接实现这条递推大约需要 \(O(w^4)\) 级别的时间。对于 \(d=10000\) 来说，\(w=5000\)，这个规模显然过大。
所以实现没有改变单段成本公式，也没有改变“先做半程、再镜像”的核心思路，而是把搜索限制在一个经验上很接近最优路径的窄区域中。
实现采用的参考曲线是下面这个四分之一圆：
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w.$$
它正是以 \((w,0)\) 为圆心、半径为 \(w\) 的圆的左支。
实现只扩展那些接近这个圆的源状态，也就是满足
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon$$
的格点。对每一个目标高度 \(y\)，允许到达的 \(x\) 还会被限制在参考圆弧附近的一条窄横带里：
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
这三个实现默认使用 \(W=30\) 与 \(\varepsilon=0.5\)。需要强调的是，这并不是完整理论 DP 的严格遍历，而是一种数值上有针对性的剪枝策略。不过它可以重现所有已公布的校验值，而且这正是 C++、Python、Java 三个实现实际采用的算法。
C++、Python 和 Java 实现都会先建立一个表，用来保存所有半程状态 \((x,y)\) 的最优时间，其中 \(0\le x\le w\)、\(1\le y\le w\)。除了起点 \((0,1)\) 被设为 \(0\) 之外，其余状态一开始都设为无穷大。
然后程序会预计算两类几何数据：每个高度的 \(\ln y\)，以及参考圆弧上的水平位置 \(x_{\mathrm{arc}}(y)\)。预先存好这些值之后，在大量转移中就不必重复做相同的对数运算。
接下来，对每个水平坐标 \(x_0\)，实现会预先筛出所有位于参考圆附近薄环带中的高度 \(y_0\)。后续真正被展开的源状态，只来自这些格点。
当程序展开某个源状态时，它会枚举所有 \(y\ge y_0\) 的目标高度。对于每个这样的 \(y\)，先计算一次对应的速度倒数因子，再确定参考圆弧附近允许的水平带，随后对带内所有 \((x,y)\) 目标状态做松弛更新。
一旦某次更新到达了边界 \(x=w\)，当前最优的半程答案就会被刷新。所有源状态都处理完成后，程序返回的最终值就是“最佳半程代价的两倍”，并按九位小数输出。
设 \(w=d/2\)，设横向带宽为 \(W\)。不做剪枝的单调 DP 有 \(O(w^2)\) 个状态，每个状态最多查看 \(O(w^2)\) 个前驱，因此朴素时间复杂度是 \(O(w^4)\)，空间复杂度是 \(O(w^2)\)。
在实际实现中，参考圆周围的环带厚度是常数，因此可展开的源状态总数只有 \(O(w)\) 量级。每个源状态会扫描所有目标高度，但在每个高度上只考虑 \(O(W)\) 宽度的水平区间，所以总的目标单元数约为 \(O(wW)\)。综合起来，实际运行时间大致是 \(O(w^2W)\)，而内存仍然保持在 \(O(w^2)\)。
对真实目标 \(d=10000\) 而言，\(w=5000\)，默认 \(W=30\)。也正因为如此，带状剪枝后的版本是可行的，而完整 DP 则不可行。
Муравей стартует в точке \(A(0,1)\) и должен попасть в \(B(d,1)\), где \(d\in 2\mathbb{Z}_{>0}\). Каждый ход представляет собой прямой отрезок между узлами решетки и всегда идет вперед по оси \(x\). Если отрезок начинается на высоте \(y_0\) и заканчивается на высоте \(y_1\), то его скорость равна
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
Нужно минимизировать суммарное время; это минимальное значение обозначается \(F(d)\). Опубликованные контрольные значения таковы: \(F(4)=2.960516287\), \(F(10)=4.668187834\), \(F(100)=9.217221972\). Для \(F(10000)\) полный перебор всех решетчатых путей невозможен.
Реализации сначала решают задачу только на левой половине рисунка, а затем зеркально достраивают правую половину. Обозначим
$$w=\frac d2.$$
Тогда нужно найти хороший путь из \((0,1)\) до вертикали \(x=w\), а затем удвоить стоимость лучшего полупути.
Для отрезка из \((x_0,y_0)\) в \((x_1,y_1)\) положим
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$$
Время движения по нему равно \(L/v\). Удобно ввести множитель, равный обратной скорости:
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
Тогда вклад одного отрезка можно записать так:
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1).$$
При \(y_1\to y_0\) вторая формула стремится к \(1/y_0\), поэтому горизонтальный и негоризонтальный случаи согласуются непрерывно. Когда \(y_0\ne y_1\), скорость из условия есть логарифмическое среднее значений \(y_0\) и \(y_1\).
Точки \(A(0,1)\) и \(B(d,1)\) симметричны относительно прямой \(x=w\). Отражение пути относительно этой прямой сохраняет евклидовы длины отрезков и пары высот на концах каждого отраженного отрезка, а значит, сохраняет и время.
Поэтому реализации на C++, Python и Java ищут лучший левый полупуть из \((0,1)\) в некоторую точку \((w,Y)\), а затем отражают его. В этой модели
$$F(d)=2\min_{1\le Y\le w} D(w,Y),$$
где \(D(x,y)\) обозначает минимальное время достижения \((x,y)\) на левой половине. В исследуемом полупути высота не убывает: она может сохраняться или расти, а после отражения автоматически возникает симметричный спуск назад к \(y=1\).
Базовое состояние имеет вид
$$D(0,1)=0.$$
Для любой вершины решетки \((x,y)\), где \(0\le x\le w\) и \(1\le y\le w\), оптимальная стоимость полупути получается из некоторого более раннего состояния \((x_0,y_0)\) с \(x_0\le x\) и \(y_0\le y\):
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
Это задача кратчайшего пути на ациклическом графе состояний: \(x\) никогда не убывает, и на рассматриваемой половине высота \(y\) тоже не убывает. Любое состояние на границе \(x=w\) уже задает готовое решение для половины и тем самым дает полный кандидат \(2D(w,y)\).
При \(d=4\) получаем \(w=2\). Естественный полупуть таков:
$$ (0,1)\to(1,2)\to(2,2). $$
Первый отрезок имеет длину \(\sqrt2\), а его множитель обратной скорости равен
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$$
Значит, его время равно \(\sqrt2\ln 2\). Второй отрезок горизонтален на высоте \(2\), имеет длину \(1\), поэтому его время равно \(1/2\). Следовательно, стоимость половины пути равна
$$D(2,2)=\sqrt2\ln 2+\frac12.$$
После отражения получаем полный путь
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1), $$
и потому
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$$
что точно совпадает с контрольным значением \(2.960516287\).
Если бы для каждого состояния \((x,y)\) приходилось проверять все возможные предшественники \((x_0,y_0)\), то было бы \(O(w^2)\) состояний и до \(O(w^2)\) переходов на каждое состояние. Для \(d=10000\), где \(w=5000\), буквальная реализация этой рекурсии была бы слишком медленной.
Поэтому реализации сохраняют ту же формулу стоимости и ту же идею полупути, но ограничивают поиск узкой геометрической областью, в которой численно ожидаются почти оптимальные состояния.
В качестве опорной кривой используется четверть окружности
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w,$$
то есть левая ветвь окружности с центром \((w,0)\) и радиусом \(w\).
Расширяются только те исходные состояния, которые лежат близко к этой окружности:
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$$
Для каждой целевой высоты \(y\) разрешенные координаты \(x\) дополнительно ограничиваются узкой горизонтальной полосой:
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
В опубликованных реализациях используются стандартные параметры \(W=30\) и \(\varepsilon=0.5\). Это не полный теоретический перебор DP, а численно мотивированная стратегия отсечения. Тем не менее она воспроизводит все опубликованные контрольные значения и в точности соответствует тому, что делают реализации на C++, Python и Java.
Сначала реализации на C++, Python и Java создают таблицу лучших времен полупути для всех решетчатых состояний с \(0\le x\le w\) и \(1\le y\le w\). Все значения инициализируются бесконечностью, кроме стартовой клетки \((0,1)\), которая получает значение \(0\).
Затем заранее вычисляются две геометрические последовательности: \(\ln y\) для каждой высоты и положение опорной дуги \(x_{\mathrm{arc}}(y)\). Предварительный расчет логарифмов важен, потому что множитель обратной скорости многократно используется для разных пар высот.
После этого для каждого горизонтального положения \(x_0\) программа заранее собирает все высоты \(y_0\), лежащие в тонком кольце вокруг опорной окружности. Только такие решетчатые точки потом рассматриваются как расширяемые источники.
При расширении одного источника реализация перебирает все целевые высоты \(y\ge y_0\). Для каждой такой высоты множитель обратной скорости вычисляется один раз, затем определяется допустимая горизонтальная полоса вокруг опорной дуги, и после этого выполняется релаксация всех состояний \((x,y)\) внутри этой полосы.
Как только некоторая релаксация достигает границы \(x=w\), обновляется лучший найденный ответ для половины пути. После завершения всех расширений возвращается ровно удвоенная стоимость лучшего полупути, отформатированная с девятью знаками после запятой.
Пусть \(w=d/2\), а \(W\) обозначает ширину горизонтальной полосы. У немодифицированной монотонной DP имеется \(O(w^2)\) состояний и \(O(w^2)\) проверок предшественников на каждое состояние, поэтому наивная временная сложность равна \(O(w^4)\), а память равна \(O(w^2)\).
В реализованной версии кольцо вокруг опорной окружности имеет постоянную толщину, поэтому содержит лишь \(O(w)\) существенных исходных состояний. Каждое расширяемое состояние рассматривает \(O(wW)\) целевых клеток: перебираются все целевые высоты, но по горизонтали допускается только полоса ширины \(O(W)\). Практически это дает время порядка \(O(w^2W)\), при том что память остается \(O(w^2)\).
Для реальной цели \(d=10000\) имеем \(w=5000\) и стандартное \(W=30\), поэтому именно отсеченная версия оказывается выполнимой, а не полная DP.
تبدأ النملة من النقطة \(A(0,1)\) ويجب أن تصل إلى \(B(d,1)\)، حيث إن \(d\in 2\mathbb{Z}_{>0}\) عدد زوجي موجب. كل حركة هي قطعة مستقيمة بين نقطتين شبكيتين، مع تقدّم مستمر في اتجاه \(x\). إذا بدأت قطعة عند الارتفاع \(y_0\) وانتهت عند الارتفاع \(y_1\)، فإن السرعة تساوي
$$v=\begin{cases} y_0, & y_0=y_1,\\ \dfrac{y_1-y_0}{\ln y_1-\ln y_0}, & y_0\ne y_1. \end{cases}$$
المطلوب هو تصغير الزمن الكلي، وهذا الحد الأدنى نرمز له بـ \(F(d)\). قيم التحقق المنشورة هي \(F(4)=2.960516287\) و\(F(10)=4.668187834\) و\(F(100)=9.217221972\). أما الهدف الفعلي فهو \(F(10000)\)، ولذلك فالتعداد الشامل لجميع المسارات الشبكية غير عملي تمامًا.
التنفيذات الثلاثة لا تحاول بناء المسار كاملًا دفعة واحدة، بل تحل نصف المسار الأيسر أولًا ثم تعكسه حول المحور الوسطي. نكتب
$$w=\frac d2.$$
وعندئذ تصبح المهمة هي إيجاد أفضل مسار من \((0,1)\) إلى المستقيم الرأسي \(x=w\)، ثم مضاعفة كلفة هذا النصف.
لأي قطعة تصل بين \((x_0,y_0)\) و\((x_1,y_1)\)، نعرّف
$$\Delta x=x_1-x_0,\qquad \Delta y=y_1-y_0,\qquad L=\sqrt{(\Delta x)^2+(\Delta y)^2}.$$
زمن الحركة على هذه القطعة هو \(L/v\). ومن الأنسب كتابته باستعمال عامل يساوي مقلوب السرعة:
$$\psi(y_0,y_1)=\begin{cases} \dfrac1{y_0}, & y_0=y_1,\\[4pt] \dfrac{\ln y_1-\ln y_0}{y_1-y_0}, & y_0\ne y_1. \end{cases}$$
وبذلك يصبح زمن القطعة
$$\tau\bigl((x_0,y_0)\to(x_1,y_1)\bigr)=L\,\psi(y_0,y_1).$$
عندما يقترب \(y_1\) من \(y_0\)، فإن الفرع الثاني يقترب من \(1/y_0\)، ولهذا ينسجم الوضع الأفقي مع الوضع غير الأفقي ضمن صيغة مستمرة واحدة. وعندما يكون \(y_0\ne y_1\)، تكون السرعة المعطاة في نص المسألة هي المتوسط اللوغاريتمي للعددين \(y_0\) و\(y_1\).
النقطتان \(A(0,1)\) و\(B(d,1)\) متناظرتان بالنسبة إلى المستقيم \(x=w\). إذا عكسنا مسارًا حول هذا المستقيم، فإن أطوال القطع الإقليدية تبقى كما هي، كما تبقى أيضًا أزواج الارتفاعات عند طرفي كل قطعة منعكسة، ولذلك يبقى الزمن الكلي ثابتًا.
لهذا السبب تبحث تنفيذات C++ وPython وJava عن أفضل نصف مسار أيسر من \((0,1)\) إلى نقطة وسطية من الشكل \((w,Y)\)، ثم تعكسه. في هذا النموذج نحصل على
$$F(d)=2\min_{1\le Y\le w} D(w,Y),$$
حيث يرمز \(D(x,y)\) إلى أقل زمن للوصول إلى \((x,y)\) في النصف الأيسر. وفي النصف الذي يجري البحث فيه لا يُسمح للارتفاع إلا أن يبقى ثابتًا أو يزداد؛ وبعد الانعكاس يظهر الهبوط المتماثل عائدًا إلى \(y=1\) تلقائيًا.
الحالة الابتدائية هي
$$D(0,1)=0.$$
ولكل نقطة شبكية \((x,y)\) بحيث \(0\le x\le w\) و\(1\le y\le w\)، فإن أفضل كلفة لنصف المسار تأتي من نقطة سابقة \((x_0,y_0)\) تحقق \(x_0\le x\) و\(y_0\le y\):
$$D(x,y)=\min_{\substack{0\le x_0\le x\\1\le y_0\le y}}\left(D(x_0,y_0)+\sqrt{(x-x_0)^2+(y-y_0)^2}\,\psi(y_0,y)\right).$$
وهذا في جوهره مسار أقصر على رسم بياني لا دوري: قيمة \(x\) لا تنقص أبدًا، وفي نصف المسار الذي يجري بحثه لا تنقص قيمة \(y\) كذلك. وكل حالة تصل إلى الحد \(x=w\) تمثل بالفعل نصف حل كامل، وتنتج مرشحًا كاملاً مقداره \(2D(w,y)\).
عندما \(d=4\)، يكون \(w=2\). أحد أنصاف المسارات الطبيعية هو
$$ (0,1)\to(1,2)\to(2,2). $$
طول القطعة الأولى هو \(\sqrt2\)، وعامل مقلوب السرعة لها يساوي
$$\psi(1,2)=\frac{\ln 2-\ln 1}{2-1}=\ln 2.$$
إذن زمن هذه القطعة هو \(\sqrt2\ln 2\). أما القطعة الثانية فهي أفقية عند الارتفاع \(2\)، وطولها \(1\)، ولذلك زمنها \(1/2\). ومن ثم تكون كلفة نصف المسار
$$D(2,2)=\sqrt2\ln 2+\frac12.$$
وبعكس هذا النصف نحصل على المسار الكامل
$$ (0,1)\to(1,2)\to(2,2)\to(3,2)\to(4,1), $$
وبالتالي
$$F(4)=2\left(\sqrt2\ln 2+\frac12\right)=2.9605162869\ldots,$$
وهو مطابق تمامًا لقيمة التحقق \(2.960516287\). هذا المثال الصغير يوضح كيف تتكامل صيغة الكلفة مع التناظر ومع حالات البرمجة الديناميكية.
إذا سمحنا لكل حالة \((x,y)\) بأن تفحص جميع الأسلاف الممكنين \((x_0,y_0)\)، فسيكون لدينا \(O(w^2)\) حالة، وقد يصل عدد الأسلاف لكل حالة إلى \(O(w^2)\) أيضًا. وعندما يكون \(d=10000\)، أي \(w=5000\)، يصبح التطبيق الحرفي لهذه العلاقة أبطأ بكثير من أن يكون عمليًا.
لذلك تحتفظ التنفيذات بنفس صيغة كلفة القطعة ونفس فكرة نصف المسار، لكنها تقصّ البحث إلى منطقة هندسية ضيقة يُتوقع عدديًا أن تحتوي الحالات شبه المثلى.
المنحنى المرجعي المستخدم في التنفيذات هو ربع الدائرة
$$x_{\mathrm{arc}}(y)=w-\sqrt{w^2-y^2},\qquad 1\le y\le w,$$
وهو الفرع الأيسر للدائرة التي مركزها \((w,0)\) ونصف قطرها \(w\).
لا تُوسَّع إلا الحالات المصدرية القريبة من هذه الدائرة، أي الحالات التي تحقق
$$\left|\sqrt{(w-x_0)^2+y_0^2}-w\right|\le \varepsilon.$$
ولكل ارتفاع هدف \(y\)، تُقيد إحداثيات \(x\) المسموح بها بشريط أفقي ضيق حول القوس المرجعي:
$$\max\bigl(x_0,\ x_{\mathrm{arc}}(y)-W\bigr)\le x\le \min\bigl(w,\ x_{\mathrm{arc}}(y)+1\bigr).$$
في التنفيذات المنشورة، القيم الافتراضية هي \(W=30\) و\(\varepsilon=0.5\). وهذا ليس البرمجة الديناميكية النظرية الكاملة بلا قيود، بل هو أسلوب تقليم موجّه عدديًا. ومع ذلك فهو يعيد إنتاج جميع قيم التحقق المنشورة، وهو بالضبط ما تنفذه نسخ C++ وPython وJava.
تبدأ تنفيذات C++ وPython وJava بإنشاء جدول يحفظ أفضل أزمنة نصف المسار لجميع الحالات الشبكية التي تحقق \(0\le x\le w\) و\(1\le y\le w\). تُملأ الخانات كلها بقيمة لا نهائية، باستثناء الحالة الابتدائية \((0,1)\) التي تأخذ القيمة \(0\).
بعد ذلك يُحسب مسبقًا نوعان من القيم الهندسية: \(\ln y\) لكل ارتفاع \(y\)، والموقع الأفقي \(x_{\mathrm{arc}}(y)\) على القوس المرجعي. حساب اللوغاريتمات مسبقًا مهم لأن عامل مقلوب السرعة يُستخدم مرارًا لكثير من أزواج الارتفاعات.
ثم، لكل موضع أفقي \(x_0\)، تُحضّر الشيفرة قائمة بكل الارتفاعات \(y_0\) التي تقع داخل الحلقة الرقيقة حول الدائرة المرجعية. هذه النقاط فقط تُعامل لاحقًا بوصفها حالات مصدر قابلة للتوسيع.
عند توسيع حالة مصدر معينة، تمر الشيفرة على جميع الارتفاعات الهدف \(y\ge y_0\). ولكل ارتفاع من هذه الارتفاعات تحسب عامل مقلوب السرعة مرة واحدة، ثم تحدد الشريط الأفقي المسموح حول القوس، ثم تجري عملية الإرخاء على جميع الحالات \((x,y)\) الواقعة داخل هذا الشريط.
وحين تصل إحدى عمليات الإرخاء إلى الحد \(x=w\)، يُحدَّث أفضل جواب نصفي تم العثور عليه حتى تلك اللحظة. وبعد اكتمال جميع التوسيعات، تُعاد النتيجة النهائية بوصفها ضعف أفضل كلفة نصفية، مع طباعة تسعة منازل عشرية.
لنكتب \(w=d/2\)، ولتكن \(W\) هي عرض الشريط الأفقي. في البرمجة الديناميكية الأحادية غير المقلمة يوجد \(O(w^2)\) حالة، ولكل حالة حتى \(O(w^2)\) فحصًا للأسلاف، ولذلك يكون التعقيد الزمني الساذج \(O(w^4)\)، مع ذاكرة مقدارها \(O(w^2)\).
أما في النسخة المنفذة فعليًا، فالحلقة حول الدائرة المرجعية ذات سماكة ثابتة، ولذلك تحتوي فقط على \(O(w)\) من حالات المصدر المهمة. وكل حالة مصدر موسعة تفحص تقريبًا \(O(wW)\) خلية هدف، لأنها تمر على جميع الارتفاعات الهدف ولكنها تقصر الامتداد الأفقي على شريط عرضه \(O(W)\). ومن ثم يكون زمن التنفيذ العملي قريبًا من \(O(w^2W)\)، بينما تبقى الذاكرة \(O(w^2)\).
بالنسبة إلى الهدف الحقيقي \(d=10000\)، لدينا \(w=5000\) والقيمة الافتراضية \(W=30\)، ولهذا السبب يكون الأسلوب المقلم ممكنًا عمليًا، بينما لا تكون البرمجة الديناميكية الكاملة ممكنة.