PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given a permutation array A of size N. Determine the number of ranges [L, R] such that, after erasing all elements A_i where
- i\notin [L,R] or,
- A_i\notin [L,R],
the resultant array is sorted.
EXPLANATION:
Definition: Call a range-array valid, if its elements are sorted in increasing order.
Claim: If the range-array of [L, R] is valid, then the range-array of [L',R'] is also valid, for all L\le L' \le R'\le R.
Proof
Consider a sequence of steps that changes [L, R] to [L',R'] by reducing the size of the range in each step (increasing L or decreasing R by 1).
In each step, elements from the initial range-array are deleted to create the range-array of the new range, and it is easy to see that no new elements are added to the range-array.
Therefore, since the range-array of [L, R] is sorted, deleting any number of elements from it (while preserving the order) still keeps it sorted, implying the range-array of [L',R'] is sorted and thus valid.
For each r, let us calculate the number of ranges [l, r] whose range-array is valid. Then, the answer is equal to the sum of the number of ranges, over all r. More formally, if v_r is the smallest value such that range-array [v_r, r] is valid, the answer to the problem is equal to:
From the initial claim, it is clear that v_i \le v_j for all i<j. This little observation allows us to calculate array v in an increasing fashion efficiently, using a modified two-pointer approach.
Implementation
Let L and R be the bounds of the range we are currently considering. Also, let S be the range-array of [L,R]. Initially, L=R=1.
Iterate R from 1 to N. In each iteration, do the following.
First, update S to reflect the range-array of the new range [L,R] (recall that S is currently equal to the range array of [L, R-1]).
How?
If you observe the range-array of [L, R-1] and [L, R], the only new elements (there are no deletions) in the range array of the latter range are:
- element A_R, only if L\le A_R\le R holds, and
- element R, only if L\le pos_R \le R-1 holds (where pos_x is the position index of element x in A).
(The case work required to arrive at the above conclusion is trivial and left to the reader as an exercise.)
Insert the necessary values at their corresponding positions in S to get the new range-array of [L, R] (how to do this is explained later, bear with me).
Then, while S is not sorted, increase the value of L by 1 and recompute the range-array of the new range.
How?
Similar to the previous spoiler, the only deletions in the range-array of [L,R] to get the range-array of [L+1, R] are:
- element A_L, only if L\le A_L\le R holds, and
- element L, only if L+1\le pos_L \le R holds.
It is easy to deduce that the value of L at the end of the two steps in each iteration is equal to v_R.
To compute S efficiently in each step, we can use an ordered set of pairs, sorted by the first term (std::set<pair<int, int>> in C++).
-
To insert element A_i in its corresponding position in the range-array, we can insert pair (i, A_i) into S.
-
We can similarly remove element A_i by erasing (i, A_i) from S.
-
Everytime we insert into S, we can check if the range-array is still sorted by comparing the second value of the inserted pair with it’s left and right neighbours in S (If S is no longer sorted after an insertion, we keep increasing L, removing elements in the process, until S is sorted again).
Each of the above operations takes O(\log |S|).
TIME COMPLEXITY:
(Refer implementation spoiler for terminologies).
Since each element of A is inserted and removed from S at most once, and since each operation on S has complexity O(\log |S|), the total time complexity per test case is
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters