# Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is:

|               |
|       |       |
|   |   |   |   |


On the other hand, the following configurations would be invalid:

|
|  |
|  |  |


reason: 3rd tree should be higher than the 2nd one

|  |
|  |
|  |


reason: consecutive trees cannot have the same height

Given a sequence of physical trees in a garden, what is the minimum number of physical trees which must be cropped/cut in order to achieve the pattern desired by that gardener?

First, the heights of the physical trees in the garden can be represented by a sequence of integers. For instance, the three examples above can be represented as (3 1 2 1 3), (3 2 1) and (3 3).

Mathematically speaking, the problem maps to find the minimum number of negative sums which must be applied to a sequence of integers (a0, a1, ..., aN) so that each pair of consecutive integers (ai, ai+1) in this sequence alternates between strictly decreasing (ai < ai+1) and strictly increasing (ai > ai+1) . Example: In (2, 3, 5, 7) , the minimum number of negative sums is 2. A possible solution is to add -2 to the 2nd element and then add -3 to the last element, resulting in (2, 1, 5, 4).

My search model is a graph where each node represents a sequence of physical tree heights and each edge represents a decrease of the height of a tree (from now on called "cut"). In this model, a possible path from the initial node to the goal node in the above example would be

• initial node: (2,3,5,7)
• action: sum -2 to a1
• intermediate node: (2,1,5,7)
• action: sum -3 to a3
• goal node: (2,1,5,4).

I have used a breadth-first search to find the shortest path from the initial node to the goal node. The length of this shortest patch is equal to the minimum number of trees that must be cut.

The only improvement to this algorithm that I was able to think was using a priority queue that orders the possible nodes to be explored in increasing order 1st by number of cuts (as traditional BFS already does) and 2nd by the number of "errors" in the sequence of integers in the node: triplets which do not match the required up/down pattern, ie. (ai < ai+1 and ai+1 < ai+2) OR (ai > ai+1 and ai+1 > ai+2), plus the number of consecutive equal numbers pairs (ai == ai+1) . This increases the probability that the goal node will be reachable from the first nodes with N-1 cuts in the queue when the times come to evaluate them. However, it is only useful to reduce the search space of nodes with N-1 cuts and not the complexity of the whole search.

The time required to execute this algorithm grows exponentially with the number of the trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up ?

• @D.W. I have edited the question. This problem is about a sequence of physical trees (eg palm trees). The previous descriptions was ambiguous because both the physical plant and the Computer Science data structure have the same name. I hope it is clearer now. – Alan Evangelista Nov 8 '19 at 20:54
• A possible solution is to add -2 to the 2nd element and then add -3 to the last element that looks two negative addends. If you added -3 to $a_2$, you'd get $(2, 3, 2, 7)$ - a valid solution? – greybeard Dec 19 '20 at 17:16

I'll describe two ways you could solve this problem. Either works. In some sense they are basically the same algorithm, just viewed from two different perspectives.

# Dynamic programming algorithm

This can be solved in linear time with dynamic programming. Let $$d_i$$ denote minimum number of $$a_i,\dots,a_n$$ that must be cut to produce an alternating sequence if you start in the downwards direction for the first pair (the pair $$a_i,a_{i+1}$$) and don't cut $$a_i$$, and $$u_i$$ the minimum number to produce an alternating sequence starting in the upwards direction if you don't cut $$a_i$$, and $$u'_i$$ the minimum number to produce an alternating sequence starting in the upwards direction if you do cut $$a_i$$. Then you can write down a recurrence relation that expresses $$d_i,u_i,u'_{i+1}$$ in terms of $$d_{i+1},u_{i+1},u'_{i+1}$$, and you can evaluate it in $$O(n)$$ time using dynamic programming.

In particular, the recurrence relation is $$u'_i = 1 + d_{i+1}$$ and

$$d_i = \begin{cases} \min(u_{i+1},u'_{i+1}) &\text{if }a_i>a_{i+1}\\ +\infty &\text{otherwise.} \end{cases}$$

$$u_i = \begin{cases} d_{i+1} &\text{if }a_i

Once you've computed all these values, the final answer for the minimum number of cuts needed for the sequence $$a_1,\dots,a_n$$ is $$\min(d_1,u_1,u'_1)$$.

# Graph search

Alternatively, we can solve this by building up a suitable graph and then finding the shortest path in this graph.

Label a tree as a "peak" if in it is higher than its neighbors in the final sequence, and a "valley" if it is lower than its neighbors in the final sequence. The final sequence will alternate between peaks and valleys. Here is the two key observations:

• The optimal solution will never cut any tree that ends up as a peak. (Any solution that involves cutting a peak will remain valid if you don't cut the peak, and that reduces the number of cuts by 1.)

• In the optimal solution, you can assume without loss of generality that every tree that ends up a valley is cut down to the ground, i.e., to the minimum height. (Any solution that involves cutting a valley only partway will remain valid if you cut it down to the ground.)

Since we want to find an optimal solution, we will consider only solutions that follow both rules.

Let $$a_1,\dots,a_n$$ be the sequence. We will build a graph with $$3n$$ vertices. Each vertex has the form $$\langle i,t,c \rangle$$ where $$i \in \{1,2,\dots,n\}$$ is an index that identifies a tree, $$t$$ indicates whether tree $$i$$ will be a peak or a valley in the final solution, and $$c$$ indicates whether tree $$i$$ is cut to the ground or uncut in the final solution. We'll have an edge from one vertex to the next if they can be adjacent in a final solution. Thus, we have the following edges:

• $$\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{no} \rangle$$, with length 0, for those $$i$$ where $$a_i>a_{i+1}$$

• $$\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{yes} \rangle$$, with length 1, for all $$i$$

• $$\langle i, \text{valley}, \text{no}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$$, with length 0, for those $$i$$ where $$a_i

• $$\langle i, \text{valley}, \text{yes}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$$, with length 0, for all $$i$$

Finally, find the shortest path in this graph from a start vertext to an end vertex, where the start vertices are those of the form $$\langle 1, *, *\rangle$$ and the end vertices are those of the form $$\langle n, *, *\rangle$$. The length of this path will correspond to the minimum number of cuts needed in the optimal solution, and the path itself can be used to reconstruct the final solution. This shortest path can be found in $$O(n)$$ time using breadth-first search (BFS) on the graph defined above.

• Does "if you start in the downwards direction for the first pair" refer to the initial tree sequence (before any cuts) or the final tree sequence (after minimum cuts) ? If it is the former, in the example sequence (3,2,1) of size 3, d[2] = d[1] = 0, d[0] = 1 and u[0] and u[1] are not defined . If it is the latter, a downward direction is impossible to achieve when a[i-1] < a[i] and a[i-1] == 1; how could I calculate d[i-1] ? I also cannot find the recurrent relation to express d(i) and u(i) in terms of d(i+1) and u(i+1). – Alan Evangelista Nov 9 '19 at 13:48
• @AlanEvangelista, in the final sequence (after cuts). If it is impossible to achieve, then set $d_i$ to $+\infty$. – D.W. Nov 10 '19 at 2:54
• @AlanEvangelista, see edited answer for a detailed elaboration on how to construct the recurrence relation and the algorithm. – D.W. Nov 10 '19 at 7:25

I think it's pretty easy to solve in O(n) time with one iteration over the array of integers representing the tree heights.

You can only create valleys by your cuts, not hills, so you should count the existing number of valid valleys at even and odd positions and cut depending of the result. Like D.W. said, you can cut every tree down to the ground that you want to convert to a valley and not touch the ones you want to be a hill.

Initialize two counters with 0, evenValleyCount and oddValleyCount.

Now iterate over the array of numbers representing the tree heights and check every value for being a valley (lower than left and right neighbors). If it's a valley increment evenValleyCount if the index of the current element is even or oddValleyCount if the index is odd.

If the length of the array is odd add 0.5 to evenValleyCount and subtract 0.5 from oddValleyCount.

Your result is the length of the array divided by 2 minus the higher value of evenValleyCount and oddValleyCount.

My answer for this was like below

function solution($$A) { // write your code in PHP7.0 res = 0; h = 0; i = 0; foreach (A as a) { if (isset(A[$$i+1])) {

if ($$a ==$$A[$$i+1]) {$$res++;
continue;
}

if ($$h >= 2) { res++; h = 0; } if ($$a < $$A[$$i+1]) {
$h++; } if ($$h <= -2) { res++; h = 0; } if ($$a > $$A[$$i+1]) { $$h--; } }$$i++; } return$res;
}

• This is just a quick think. Im not sure of its correct so please check with example numbers – Adilet Kamchibekov Dec 19 '20 at 16:26
• (While your code layout wasn't entirely consistent to begin with, "code fencing" made an amazing mess of it. I suggested removing blank lines I'd use myself, just because I think it's more valuable not to have to scroll the code.) I think coding answers about as far off topic as coding, even "programming" questions. – greybeard Dec 19 '20 at 17:34
• We're not a coding site, and we discourage answers that consist of only a bunch of code. Please get rid of the source code and replace it with ideas, pseudo code explanation, and arguments of correctness. See here and here for related meta discussions. – D.W. Dec 22 '20 at 8:49