Editorial for DMOPC '18 Contest 3 P6 - Bob and Suffering


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.

Authors: r3mark

For the first subtask, brute-force all possible subarrays for each query.

Time Complexity: \mathcal{O}(QN^2)

For the second subtask, consider each element. Using two stacks, we can determine the index of the rightmost element to the left of it which is strictly less than it, and the leftmost element to the right of it which is strictly less than it. Then for each query, we only need to loop through each element instead of all subarrays.

Time Complexity: \mathcal{O}(QN)

For the third subtask, note that the answer to each query is either the suffering of the longest subarray which contains only the greater value, or it is the suffering of the entire subarray. The first value can be computed using a segment tree. The other value is easy to compute.

Time Complexity: \mathcal{O}((N+Q)\log N)

There are two solutions to the fourth subtask. One simply extends the solution to the third subtask. The other, which we will discuss, sheds light on the full solution.

Let par[i][0] be the rightmost element to the left of i which is strictly less than v_i and par[i][1] be the leftmost element to the right of i which is strictly less that v_i. As mentioned in the solution to subtask 2, these values can be computed in \mathcal{O}(N). Also, remember that for a minimum element at index i, we only need to consider its subarray from \max(l, par[i][0]+1) to \min(r, par[i][1]-1).

Consider a subarray contained within an array. There are three cases: the subarray contains the leftmost element, it contains the rightmost element, or it contains neither. For the first case, note that we only need to consider when l, par[l][0], par[par[l][0]][0], and so on are the indices of the minimum elements. Let K be the number of distinct values. Since K is small, this can be done quickly. The second case is handled similarly.

For the third case, we only need to consider when l\le par[i][0]+1 and par[i][1]-1\le r. We can use a segment tree and handle the queries offline.

Time Complexity: \mathcal{O}((N+Q)\log N + KQ)

Some users have noticed that the subtasks were taken from IOI '18 F. Indeed, the full solution bears some similarities.

For the final subtask, we speed up the solution described for subtask 4. Specifically, the first two cases must be sped up. Note that the par values defined implicitly build two trees. Also, when stopping at a certain index j (which was some par[par[...][...]][0]) in the first case, then the suffering obtained is v_j\cdot (prefix\_sum[par[j][0]-1]-prefix\_sum[l-1]) = m_j x + b_j, where x=prefix\_sum[l-1], m_j = -v_j, b_j = v_j\cdot prefix\_sum[par[j][0]-1].

So the first two cases become a convex hull problem on the path of two trees. This can be done by performing heavy-light decomposition and building a segment tree of convex hulls. Sorting the queries based on left/right endpoint (depending on which case) can speed up the \mathcal{O}(\log ^3 N) per query to \mathcal{O}(\log ^2 N) per query (during testing, there was very little change in performance from this optimization).

Time Complexity: \mathcal{O}((N+Q)\log ^2N)


Comments

There are no comments at the moment.