An interesting binary search problem. This problem appeared in the ACM ICPC World Finals 2017.

We need to calculate an unknown constant $c$ (possibly negative).

First we need to establish an upper and lower bound on the value of $c$. The problem statement mentions that: “Note that while Sheila’s speedometer might have negative readings, her true speed was greater than zero for each segment of the journey.”

Given Sheilas true speed as $s + c$, we have, $s + c > 0$ at any given point in time.

Our strategy will be to guess the value of $c$, and then check if it is a valid guess. If not, then just keep guessing until we have a valid value of $c$.

Say, we have a guess $c^\prime$. How can we know if this is a valid guess?

We know that, $t = \ddfrac{d}{s}$. Where, $t = \textrm{time}$, $d = \textrm{distance}$, and $ s = \textrm{speed}$.

So we have guessed the actual speed as $s + c^\prime$. Given our guess and the distances of each segment, we can check if the journey actually takes time $t$ or not. Namely we’re checking,

\[ \sum_{i = 1}^{n} \ddfrac{d_i}{s_i + c^\prime} \stackrel{\Large{?}}{=} t\]

Now, $s_{\textrm{min}} = -1000$. So, $ c \not\leq -1000$.

Again, $d_{\textrm{max}} = 1000$. In order to find $c_{\textrm{max}}$, we let $d_i = 1000$ and $s_i = -1000$ for $1 \leq i \leq n$. So we have,

\[ \sum_{i = 1}^{1000} \ddfrac{1000}{-1000 + c_{\textrm{max}}} = t_{\textrm{min}} = 1\] \[ \Longrightarrow \ddfrac{1000 \times 1000}{-1000 + c_{\textrm{max}}} = 1\] \[ \Longrightarrow -1000 + c_{\textrm{max}} = 10^6 \] \[ \Longrightarrow c_{\textrm{max}} = 10^6 + 1000\]

Now that we’ve established both the lower and upper bound for $c$, we can carry out binary search.

Here’s my implementation in C++: