DEFOREST - Editorial

admin · December 28, 2017, 2:40pm

PROBLEM LINK:

PROBLEM

You are given N trees on the X-axis. Tree T_i has height H_i and is planted at x = x_i.
You need to choose two trees T_i and T_j (where x_i < x_j and H_i < H_j) and connect the tops of these trees with a rope such that the following conditions are satisfied:

The angle between the rope and the X-axis is equal to 45 degrees.
The rope does not pass through any other trees.

In order to satisfy the second condition, you are allowed to reduce the height of any trees except T_i and T_j. Formally, you should choose numbers C_1, C_2, ..., C_N, such that 0 \le C_k \le H_k for each 1 \le k \le N and C_i = C_j = 0, then decrease H_k by C_k for each 1 \le k \le N.

Find the maximum value of (\text{Length of the rope between the two tops} - \sum_{i = 1}^{N} C_i)

Note that the rope can touch the top of some intermediate tree.

Constraints: N \le 2.5 \cdot 10^5. All x_i are distinct.

PREREQUISITES

Knowledge of Fenwick Tree or Segment Tree.

EXPLANATION

Partitioning into groups

First, we analyze the constraint given to connect two trees. Note that the two trees we choose cannot have any height reductions. Suppose the pair (i, j) is a valid candidate for the answer. Then we must have H_j - H_i = X_j - X_i. Rearranging this equation, we get that H_i - X_i = H_j - X_j. This gives us a partitioning of all the trees into
groups based on their H_i - X_i value. We denote this value as G_i. We can connect two trees if and only if they belong to the same group.

Solving each group

Consider two trees i and j belonging to the same group i.e. G_i = G_j. Let’s analyze the cost of rope between T_i and T_j. We denote this as cost(i ,j). If we need to cut the tree at (X_k, H_k) then G_k > G_i and the cost is precisely G_k - G_i. Thus, the total cost is the summation of G_k - G_i where G_k > G_i and X_i < X_k < X_j. Note that if we process the groups in decreasing order of G_i value, then the condition G_k > G_i will implicitly be taken care of, and we would have to consider only the X_i < X_k < X_j constraint, which can be done by using Fenwick Trees indexed by X_i values.

So now we can compute the cost of each candidate pair in O(\log{n}), but we’re still not done. Why? Because we
can potentially have O(n^2) candidates since a group can have O(n) elements. We’re almost there!

Reduction to Maximum Subarray Sum

We now present another observation to optimize the previous step. Sort the trees in each group G in increasing order of their X_i values. Now consider three trees (T_i, T_j, T_k) in this sorted group (i.e. X_i < X_j < X_k). Then, cost(i, k) = cost(i, j) + cost(j, k). Similarly, let’s denote len(p, q) as the length of rope between a valid candidate pair
(p, q) and profit(p, q) as len(p, q) - cost(p, q). Then, len(i, k) = len(i, j) + len(j, k) and profit(i, k) = profit(i, j) + profit(j, k).

This implies that we need to consider only adjacent trees in a group, and then the profit of any pair can be represented as a sum of a subarray of the profit list we computed. Thus, we only need to consider O(n) adjacent pairs to build this profit list, and then find the maximum sum subarray in this list. This is a very well known problem and can be solved efficiently in O(n \log{n}).

That’s it! Note that the complexity is O(n \log{n}) since we use a Fenwick Tree or Segment Tree to efficiently compute
the cost and profit of candidate pairs. Note that the fact that we process the groups in decreasing order of G_i values is important too; We would require some more complicated data structures if we didn’t do that.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.