0
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2021 at 18:56
  • $\begingroup$ I don't understand the problem statement. What's $X$? What data type is it? What do you mean by its starting and ending values? What do you mean by "values that $X$ could become"? Can you specify the task more clearly? What is the meaning of the "sequences" and the max and min in your example? $\endgroup$
    – D.W.
    Dec 19, 2021 at 8:17
  • $\begingroup$ Your explanations are pretty obscure. In particular, I cannot make any sense of your "sequences". An min/max values of what ??? $\endgroup$
    – user16034
    Apr 13, 2023 at 7:43

2 Answers 2

0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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