How to determine the max offset of a value, given the range, step size and amount of steps

Question

Given

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;
Sequences:
−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.

Answer 1

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?

Answer 2

For a given number of steps, the $\delta$ is

$$\delta=\frac{x_e-x_s}{n}$$ and you have the constraints $\delta\le\delta_{\max},n\le n_{\max}$ (if I understand anything of your question).

So

$$\left\lceil\frac{x_e-x_s}{\delta_{\max}}\right\rceil\le n\le n_{\max}.$$

---

There is only a solution when $x_e-x_s\le \delta_{\max}n_{\max}$.