<p>I give a rough idea to solve the problem in polynomial time.</p>

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

<p>These imply a dynamic programming algorithm with polynomial time complexity.</p>

CC BY-SA 3.0
2014-01-09T10:22:11.390Z
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
CC BY-SA 3.0
2014-01-09T11:25:20.997Z
@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
CC BY-SA 3.0
2014-01-09T11:44:39.813Z
@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
CC BY-SA 3.0
2014-01-09T14:15:02.923Z
@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
CC BY-SA 3.0
2014-01-09T14:30:56.943Z
@RaduGRIGore Ah, this makes sense, we have different problems in our heads.
ymbirtt
CC BY-SA 3.0
2014-01-10T01:07:40.097Z
@ymbirtt: you think this problem as a distributed system. But I think the problem is how to find the optimal operations. Thanks for Radu GRIGore's editing. I had better to learn how to write it in the beautiful format.
Bangye
CC BY-SA 3.0
2014-01-09T06:26:30.407Z
2014-01-09T10:09:05.287Z
2014-01-09T10:09:05.287Z
Bangye
<p>Given an array $A[1...n]$ of non-negative integers, 
we want to transform $A$ into $A'$ such that</p>

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

<p>One operation consist of picking two adjacent elements and perform:</p>

<p>1) Add 1 to $A[I]$ and subtract 1 from $A[I + 1]$</p>

<p>2) Subtract 1 from $A[I]$ and Add 1 to $A[I + 1]$</p>

<pre><code>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)
</code></pre>

CC BY-SA 3.0
2014-01-09T01:20:25.067Z
Hmm, that seems like it would be a good homework exercise. :-)
Neal Young
CC BY-SA 3.0
2014-01-09T17:18:15.370Z
Can you provide some background/motivation for the problem, i.e. why are you interested in this problem?
Kaveh
CC BY-SA 3.0
2014-01-12T12:20:05.007Z
This looks like an undergraduate level homework question, which are not allowed on cstheory; [CS.SE](http://cs.stackexchange.com) would be a better home.
Artem Kaznatcheev
<np-hardness><np>
Complexity of an edit distance problem
user3170458
# Complexity of an edit distance problem

(Asked by: username_0 on 2014-01-09)

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)

**Tags:** np-hardness, np
> **Comments:**
> **username_1**: Hmm, that seems like it would be a good homework exercise. :-)  
> **username_2**: Can you provide some background/motivation for the problem, i.e. why are you interested in this problem?  
> **username_3**: This looks like an undergraduate level homework question, which are not allowed on cstheory; [CS.SE](http://cs.stackexchange.com) would be a better home.  

---

## 1 answers

### Answer by username_4 on 2014-01-09. Score: 1

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- Let $T(k,R)$ be the optimal flow on the first $k$ edges such that $\sum\_{i

These imply a dynamic programming algorithm with polynomial time complexity.

> **Comments:**
> **username_5**: 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?  
> **username_6**: @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."  
> **username_5**: @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.  
> **username_6**: @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.  
> **username_5**: @RaduGRIGore Ah, this makes sense, we have different problems in our heads.  
> **username_4**: @ymbirtt: you think this problem as a distributed system. But I think the problem is how to find the optimal operations. Thanks for Radu GRIGore's editing. I had better to learn how to write it in the beautiful format.  

---

