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

Question

A gardener considers 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 (a₀, a₁, ..., a_N) so that each pair of consecutive integers (a_i, a_i+1) in this sequence alternates between strictly decreasing (a_i < a_i+1) and strictly increasing (a_i > a_i+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 a₁
• intermediate node: (2,1,5,7)
• action: sum -3 to a₃
• 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. (a_i < a_i+1 and a_i+1 < a_i+2) OR (a_i > a_i+1 and a_i+1 > a_i+2), plus the number of consecutive equal numbers pairs (a_i == a_i+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 trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up?

Answer 1

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<a_{i+1}\\ +\infty &\text{otherwise.} \end{cases}$$

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<a_{i+1}$

• $\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.

Answer 2

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.

Answer 3

I think cutting tree in sequence way has a problem itself. It's not always the minimum number of tree cuts if you do it in sequence.

Ex: With the tree array is (2,3,4,5,6,9). If you cut it in sequence, the result will be (2,1,4,3,6,5) it will return 3. But it is not the exactly answer, I think the answer for this case is 2 with (2,3,2,5,4,9). The problem is the longer the array length, the harder it is to check for nodes afterward.

So in my opinion, we can use a simpler way to approach it. Let create a new array contains the boolean value if that a tree taller than the previous one. And we all know that in aesthetically appealing gardens, this array will contains the interleaved value (Like (true, false, true, false,...) or (false, true, false, true,...)). We will need to compare the array of height-difference to two desired arrays (true, false, true, false, true and false, true, false, true, false) and note about how many difference items for each array. The bigger matching number of item, the less effort to cut tree.

Back to my example, with the tree array is (2,3,4,5,6,9), the height-difference array is (true, true, true, true, true) and we will compare it with two desired array ((true, false, true, false, true) and (false, true, false, true, false)). The bigger matching number of item is 3 when compare with (true, false, true, false, true) so the tree you need to cut is only the number of difference items between two array (In this case is 2, each array has 5 items and it has 3 items matched)

The java code:

public int solution(int[] A)
{
    int res = 0;
    int res1 = 0;
    boolean B = true;
    
    for (int i = 1; i < A.length; i++)
    {
        if ((A[i] > A[i - 1]) == B)
        {
            res++;
        }
        else
        {
            res1++;
        }
        
        B = !B;
    }
    
    return res > res1 ? A.length - 1 - res : A.length - 1 - res1;
}

Because two desired array will have opposite value at same index so I will only need to create one array (B)

That is my solution. I dont know if it is right or not. Sorry for my bad English

Answer 4

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;
}

Answer 5

Hii here is my approach using C++. You can follow it along with the comments.

int solution(vector<int> &A){
int count = 0;

//First checking if we can cut zero or not
if(A[1]-A[0] > 0 && A[2]-A[1] > 0){
    count++;
}

if(A[1]-A[0] < 0 && A[2]-A[1] < 0){
    count++;
}

//Checking if we can cut from first till last
for(int i =0; i<A.size()-2; i+=2){

    //If 4 consecutive trees are increasing order
    if(A[i] <=A[i+1] && A[i+1] <=A[i+2] && A[i+2] <=A[i+3])
    return -1;

    //If 4 consecutive trees are in decreasing order
    if(A[i] >=A[i+1] && A[i+1] >=A[i+2] && A[i+2] >=A[i+3])
    return -1;

    //checking whether we can cut the tree or not
    if(A[i+1] -A[i] >0 && A[i+2]-A[i] >0){
        if(A[i+3] - A[i+2] < 0)
        count++;
        if(A[i+3] - A[i+1] < 0)
        count++;
    }

    //checking whether we can cut the tree or not
    if(A[i+1] -A[i] <0 && A[i+2]-A[i] <0){
        if(A[i+3] - A[i+2] > 0)
        count++;
        if(A[i+3] - A[i+1] > 0)
        count++;
    }
}
return count;
}