The relief can be seen as a histogram. A histogram is good if it can be made using the moves shown in the task.

Notice that every histogram is good if and only if it satisfies the following three conditions:

• the first and the last column have a height of ~0~
• the difference between two adjacent columns is at most ~1~
• no column has a negative height

Proof

It is easily seen that a move in the task does not disrupt these three conditions. The first because we never increase the first or the last column. The second because we increase the column by ~1~ on the interval where every height is the same and we don't change the borders of the interval. The third because we only increase the relief.

Since the initial situation satisfies the conditions and a move does not disrupt them, we have proved one direction of the claim.

We now have to prove that every good histogram can be achieved by a series of moves.

Let us choose every column of height ~0~ in a good histogram. There are at least two of them: the first and the last. Between every two non-adjacent zeros we make a "reverse move" by reducing every column between those two by one. Since the second condition is valid, we have at least doubled the number of zeros in the histogram using the moves we have made. We repeat this procedure until every column in the histogram has a height of ~0~. The moves we have made bring us to the starting histogram. Thus, the statement is proved.

Solution

The solution is possible to construct in a quadratic complexity by calculating the number of ways to set heights of the first ~K~ columns so that the last column has a height of ~H~, for each state ~(K, H)~. Since the height of this column depends only on the height of the previous column, the relation is of constant complexity. The solution is memory efficient if implemented iteratively, remembering ~\mathcal O(N)~ states of the previous iterations.