1. The starting and the end values of X
  2. The maximum step (maximum delta)
  3. Exact amount of steps

I need to determinte the maximum and the minimum possible values that X could become during this chain of changes and still make it from the start value to the end value with the steps that are less or equal to the maximum step value.

E.g. for data:

  • X_start = -10; X_end = 1;
  • MaxDelta = 7;
  • MaxSteps = 4;

The answer would be: Max = 4; Min = -11;
−10 → −3 → 4 →1
−10 → −13 → −6 →1

P.S. There is no need to generate such sequences, only the max and min values.

I have been thinking about the ways to do it efficiently and I am stuck. I have an idea that a binary search might be useful.

Any help/tips/suggestions would be much appreciated.

  • $\begingroup$ You do can use binary search (namely, binary search the answer). There is also and $O(1)$ solution (start from the simplest case, when $x_{start}=x_{end}$, make it slightly harder (e.g. $|x_{start} - x_{end}| < step$), then even harder, etc.). $\endgroup$ – user114966 Mar 23 at 18:56

Suppose we start at $s$ and want to end up at $e$. We take $n$ steps, $n^+$ positive steps and $n^-$ negative steps. Then we can reach maximum $m \in[s, s + n^+\delta]$ and can end up in $[m-n^-\delta, m]$. We get equations:

\begin{align} n &= n^+ + n^-\\ n^+ &\geq 0\\ n^- &\geq 0\\ s &\leq m \leq s+n^+\delta\\ m-n^-\delta &\leq e \leq m\\ \end{align}

Rearranging we get our upper bounds:

\begin{align} m &\leq s+n^+\delta\\ m&\leq e+n^-\delta\\ \end{align}

Substitute and realize maximum:

\begin{align} m &= \min(s+n^+\delta, e+n\delta - n^+\delta)\\ m &= s + \min(n^+\delta, e-s+n\delta - n^+\delta) \end{align}

This looks complicated, but set $x = n^+\delta$ and $c = e-s+n\delta$ you only need to solve how to maximize:

$$\min(x, c - x)$$

Can you take it from here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.