E - Rush Hour 2 Editorial by en_translator
Since we can spend time wherever and whenever we want, we only have to consider the earliest time we can reach each city.
First, let us think about the following problem with only one road:
Problem: We want to travel from City \(A_i\) to City \(B_i\) using Road \(i\). If we are in City \(A_i\) at time \(T\), when is the earliest time we can arrive City \(B_i\)?
If we depart from City \(A_i\) at time \(t\), we arrive at City \(B_i\) at time \(f(t):=t+C_i+\left\lfloor \frac{D_i}{t+1}\right\rfloor\). For this \(f(t)\), the following claim is true:
Claim: A function from non-negative integer to non-negative integer \(f(t)=t+C+\left\lfloor \frac{D}{t+1}\right\rfloor\) has a minimum at \(t=\lfloor \sqrt{D}\ \rceil -1\), is weakly monotonically decreasing in \(0\leq t \leq \lfloor \sqrt{D}\ \rceil -1\), and is weakly monotonically increasing in \(\lfloor \sqrt{D}\ \rceil -1 \leq t\). (\(\lfloor x \rceil\) denotes the nearest integer to \(x\))
Proof of the claim
Subtracting a constant from $f(t)$ does not change $t$ that takes the minimum value and the convexity of $f$. Therefore, we can subtract $C - 1$ to consider $f(t)=t+1+\left\lfloor \frac{D}{t+1}\right\rfloor$. Moreover, we can shift $t$ by $1$ to obtain $g(t)=t+\left\lfloor \frac{D}{t}\right\rfloor$. If $\frac{D}{t} - \frac{D}{t+1}>1$, $\left\lfloor \frac{D}{t}\right\rfloor - \left\lfloor \frac{D}{t+1}\right\rfloor \geq1$, so $g(t)-g(t+1) \geq 0$. Therefore $g(t)$ is weakly monotonically decreasing in this range. If $\frac{D}{t} - \frac{D}{t+1} \leq1$, $\left\lfloor \frac{D}{t}\right\rfloor - \left\lfloor \frac{D}{t+1}\right\rfloor \leq1$, so $g(t)-g(t+1) \leq 0$. Therefore $g(t)$ is weakly monotonically increasing in this range. Hence, $g(t)$ takes the minimum value at the minimum $t$ such that $\frac{D}{t} - \frac{D}{t+1} \leq1$. Solving the equation, we obtain $t=\left\lceil \frac{-1+\sqrt{4D+1}}{2}\right\rceil$. With a careful transformation we obtain $\left\lceil \frac{-1+\sqrt{4D+1}}{2}\right\rceil=\lfloor \sqrt{D}\ \rceil$, and consequently $f$ has the minimum at $t=\lfloor \sqrt{D}\ \rceil-1$, shifted by $1$ from $g$.We can infer from the claim that, in order to arrive at City \(B_i\) as fast as possible, we should wait until time \(\lfloor \sqrt{D_i} \rceil -1\) if \(T\leq \lfloor \sqrt{D_i} \rceil -1\) before using the road, or otherwise we should depart immediately.
Therefore, one can solve this problem in a total of \(O(N+M\log N)\) time with an irregular Dijkstra’s algorithm.
We can realize that \( \lfloor \sqrt{D_i} \rceil -1\) by experimenting with small cases. Also, once you know that it is optimal around \(\sqrt{D}\), we can exhaustively check from \(\sqrt{D}-2\) through \(\sqrt{D}+2\).
Note that you cannot directly apply ternary search when searching for the optimal solution. Can you figure out why?
posted:
last update: