# Complexity of an edit distance problem

Given an array $A[1...n]$ of non-negative integers, we want to transform $A$ into $A'$ such that

$|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations.

One operation consist of picking two adjacent elements and perform:

1) Add 1 to $A[I]$ and subtract 1 from $A[I + 1]$

2) Subtract 1 from $A[I]$ and Add 1 to $A[I + 1]$

E.g.: 1 3 5 2
1 4 4 2 (picking 3,5)
2 3 4 2 (picking 1,4)
2 3 3 3 (picking 4,2)

• Hmm, that seems like it would be a good homework exercise. :-) – Neal Young Jan 9 '14 at 1:20
• Can you provide some background/motivation for the problem, i.e. why are you interested in this problem? – Kaveh Jan 9 '14 at 17:18
• This looks like an undergraduate level homework question, which are not allowed on cstheory; CS.SE would be a better home. – Artem Kaznatcheev Jan 12 '14 at 12:20

I give a rough idea to solve the problem in polynomial time.

1. In the optimal solution, the flow on each edge is unidirectional.
2. The final value of each element is not far from the mean. Also $\sum_{i<k}A'_i$, the prefix-sum of the optimal $A'$, is bounded in a range at most $O(n^2)$.
3. Let $T(k,R)$ be the optimal flow on the first $k$ edges such that $\sum_{i<k}A'_i=R$. Then $T(k,R)$ can be computed from $T(k-1,R')$ for all possible $R'$.

These imply a dynamic programming algorithm with polynomial time complexity.

• This appears to solve a different problem, and does not account for the fact that this model of computation has only the specified two operations. Suppose I were to input the array $1, 1, 1, ..., 1, 1, 2^n$ - would you be able to produce the specified output using only the specified operations in polynomial time? – ymbirtt Jan 9 '14 at 10:22
• @ymbirtt: What exactly do you think would not work? Suppose you have $k$ ones in your example. The mean is $(k+2^n)/(k+1)$. The solution starts $\pm n$ around the mean. In other words, I think you may have missed this: "The final value of each element is not far from the mean." – Radu GRIGore Jan 9 '14 at 11:25
• @RaduGRIGore, in this model of computation we can't directly compute the mean and put it in the relevant slots, all we can do is increase or decrease the value at a specific array index by 1. The mean in my example is $\frac{1}{n}(2^n+n-1) \sim \frac{2^n}{n}$. Even if we could compute this value, if you want to put it in any array index other than the last one, you'll need to use $O(\frac{2^n}{n})$ operations. I'm aware that an actual real-word computer does not have this restriction, however OP specified exactly two available operations. – ymbirtt Jan 9 '14 at 11:44
• @ymbirtt: The decision problem is: Given $A$ and $m$, can we transform $A$ into a "good" array using $\le m$ operations? The answer here says that this problem is in P. The algorithm described outputs the minimum $m$ for which the answer is "yes". It is also easy to change the algo to output a concise description of the list of operations: $x_1,\ldots,x_{n-1}$ where $x_i$ means how many times to move from $A_i$ to $A_{i+1}$, and $x_i$ could be negative. Yes, a full list of the operations is long. – Radu GRIGore Jan 9 '14 at 14:15
• @RaduGRIGore Ah, this makes sense, we have different problems in our heads. – ymbirtt Jan 9 '14 at 14:30