1
$\begingroup$

A little bit of history first. I have asked this question here some days ago. Quoting from there:

An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

If $A$ has just two elements, this reduces to something like a change-making problem. If $\Delta=min(A[0],A[1])$, if I can make change for $\Delta$ using only the given steps from $D=\{1,2,5\}$, I can equalize the array by holding the larger element constant while incrementing the smaller element by the same values that I used to make change for $\Delta$. However,if it's not possible to make change for delta, it's not clear if the two elements can converge two some larger value following this strategy.

I would like to know if this strategy of withholding one element and incrementing the rest by a chosen 'delta' will always make all elements equal in some finite number of steps.

$\endgroup$
1
  • $\begingroup$ You can't equalize $A=\{1,2\}$ with $D=\{2\}$. $\endgroup$
    – kennytm
    May 19, 2016 at 7:16

2 Answers 2

4
$\begingroup$

If the GCD of the array D is larger than 1, then this cannot always be done. The simplest example is $A = \{1,2\},D=\{2\}$. In contrast, if the GCD of the array D is 1, then it is known that large enough integers can be represented as positive linear combinations of elements of D. In particular, there is an integer $N$ such that $N-a$ can be represented for all $a \in A$. Summing all these representations will equalize the array.

For example, when $A = \{2,3,7\}$ and $D = \{1,2,5\}$, we can add $\{1,0,0\}$ once and $\{1,1,0\}$ four times, reflecting the representations $7-2=5 \times 1$, $7-3=4 \times 1$, $7-7 = 0 \times 1$. Even when $D = \{2,5\}$ this has a solution: using $11 = 3 \times 2 + 1 \times 5$, $10 = 2 \times 5$, $6 = 3 \times 2$, we can add $\{2,0,2\}$ three times, $\{5,5,0\}$ once, and $\{0,5,0\}$ once to get $\{13,13,13\}$.

$\endgroup$
2
$\begingroup$

Note that $A +\{x,x,0,x\}$ is equivalent to $A + \{x,x,x,x\}-\{0,0,x,0\}$. Since adding the same value does not affect equalization, so step is isomorphic to subtracting a value in $A$ from a number in $D$.

Furthermore, we could subtract $\min A$ from the array since this does not affect equalization either. Now equalizing the array is equivalent to bring the whole array to zero. Using your example, we have $$A_\text{original} = \{2,2,3,7\} \implies A_\text{reduced} = \{0,0,1,5\} $$ We use two steps A[2] -= 1 and A[3] -= 5 to equalize the array. Note that every step work with independent entries of $A$.

So yes equalization is the same as solving the change-making problem, and we don't need to worry about convergence between values because they are independent after the transformation.

Note that $\min A$ is not always the correct offset to subtract. For instance, the equalization problem is solvable with $A=\{0,1\}$ and $D=\{3,4\}$ but the change-making problem can be solved only with an offset of $-3$.

$\endgroup$

Your Answer

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

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