Editorial for IOI '18 P6 - Meetings


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

If a meeting place is given, you can calculate the cost of a meeting in \mathcal O(N). Thus, by testing every possible meeting place, the cost of a meeting can be calculated in \mathcal O(N^2) time.

The total time complexity is \mathcal O(N^2 Q).

Subtask 2

By iterating through the mountains with maintaining an upper envelope, you can get costs for all meeting places in \mathcal O(N) time.

The total time complexity is \mathcal O(NQ).

Subtask 3

Find the longest contiguous subsequence consisting only of 1 by SegmentTree. The total time complexity is \mathcal O(N + Q \log N).

Subtask 4

For each meeting, divide the range at the highest mountains and recursively solve the problem.

If you pre-calculate the answer to some ranges, such as maximal ranges in which heights of all mountains are at most some constant, and you prepare a proper data structure for Range Minimum Queries, you can get the minimum cost of a meeting in \mathcal O(\max\{H_i\} \log N) time.

Pre-calculation can be done in \mathcal O(\max\{H_i\} N) time.

The total time complexity is \mathcal O(\max\{H_i\} (N + Q \log N)).

Subtask 5

For convenience, let's assume that all values of H are distinct (this does not matter much). For each meeting, we can assume that the index of the optimal meeting place is greater than or equal to \arg\max_{L \le i \le R}(H_i), because by reversing the array H and solving the same problem we can get a real answer.

We denote the problem of calculating the minimum cost of a meeting with the range [L, R] as query [L, R].

  • Let \mathrm{Cost}(L,R) be the answer to the query [L, R].
  • Let \mathrm{RangeL}(v) be the smallest x such that \arg\max_{x \le i \le v}(H_i) = v.
  • Similarly, let \mathrm{RangeR}(v) be the largest x such that \arg\max_{v \le i \le x}(H_i) = v.
  • Also, let S(v) be the array of length

\displaystyle \mathrm{RangeR}(v)-\mathrm{RangeL}(v)+1

such that the i^\text{th} (0 \le i \le \mathrm{RangeR}(v)-\mathrm{RangeL}(v)) value of S(v) is

\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v), \mathrm{RangeL}(v)+i)

We are going to compute S(v) for all v, and then it is easy to get answers to all queries. The order of indices in which we compute S(v) is very important. Here, we use depth-first-search post-order of the cartesian tree of H.

We define the cartesian tree of H as the rooted tree such that the lowest-common-ancestor of nodes u and v is the node \arg\max_{u \le i \le v}(H_i).

The cartesian tree can be obtained in linear time by an iteration with a stack data structure. It can be easily seen that every node of the cartesian tree has at most two children, one to the left and another to the right. Let lc(v) be the left child of the node v and rc(v) be the right child of the node v (here we assume that the node v has two children).

Now the remaining task is to somehow merge S(lc(v)) and S(rc(v)) into S(v). Clearly, first some elements of S(v) is exactly S(lc(v)).

All we need is to compute \mathrm{Cost}(\mathrm{RangeL}(v), p), for all p (v \le p).

Since H_v is the maximum value in the range [\mathrm{RangeL}(v), \mathrm{RangeR}(v)], you can see

\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v), p) = \min\{\mathrm{Cost}(\mathrm{RangeL}(v), v) + (p-v) \times H_v, (v-\mathrm{RangeL}(v)+1) \times H_v + \mathrm{Cost}(v+1, p)\}

and

\displaystyle \begin{align*}
&\mathrel{\phantom\le} (\mathrm{Cost}(\mathrm{RangeL}(v), v) + (p-v) \times H_v) - ((v-\mathrm{RangeL}(v)+1) \times H_v + \mathrm{Cost}(v+1, p)) \\
&\le (\mathrm{Cost}(\mathrm{RangeL}(v), v) + (p+1-v) \times H_v) - ((v-\mathrm{RangeL}(v)+1) \times H_v + \mathrm{Cost}(v+1, p+1))
\end{align*}

where p+1 \le \mathrm{RangeR}(v).

The inequality follows from the observation that

\displaystyle \mathrm{Cost}(v+1, p+1) - \mathrm{Cost}(v+1, p) \le \max_{v+1 \le i \le p+1}(H_i) \le H_v

It indicates that there exists a certain index z such that

\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v), p) = \mathrm{Cost}(\mathrm{RangeL}(v), v) + (p-v) \times H_v

for all p \le z, and

\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v), p) = (v-\mathrm{RangeL}(v)+1) \times H_v + \mathrm{Cost}(v+1, p)

for all z < p.

Therefore, you can get S(v) in the following way:

  • Let T be the array obtained by adding a certain value to all elements of S(rc(v)).
  • Update first some elements of T with a certain linear function.
  • Concatenate S(lc(v)), \mathrm{Cost}(\mathrm{RangeL}(v), v), and T.

To carry out these operations fast, we use a compressed representation for S(v). S(v) is represented by the list of ranges. Each range has a certain linear function such that the values of S(v) in the range can be calculated by the linear function.

Adding a certain value can be done by lazy propagation.

To update first some elements, we simply iterate through T from the beginning. The ranges before the break point are replaced by one range, so the total number of iterations is \mathcal O(N).

Concatenating two arrays can be done as follows:

  • We maintain end points of ranges in a global set and store the information of ranges in a global array. Then, we do not have to do anything for ranges.
  • Concatenating lazy propagation information for adding can be done by Weighted-union heuristic:
    • Let W(s) be the value which should be added to elements of the array s.
    • When we concatenate two arrays s and t, we pick the smaller one and arrange the elements of it so that W(s) = W(t).
    • By Weighted-union heuristic, this can be done in \mathcal O(N \log N) time in total.

Getting the answer to a query requires one lower bound operation of the set. Thus in \mathcal O(Q \log N) time we can get answers to all queries.

The total time complexity is \mathcal O((N+Q) \log N).


Comments

There are no comments at the moment.