RARRAY - Editorial

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:

\sum_{r=1}^{N} (r-v_r+1)

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++).

  1. To insert element A_i in its corresponding position in the range-array, we can insert pair (i, A_i) into S.

  2. We can similarly remove element A_i by erasing (i, A_i) from S.

  3. 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

O(2\times N\log |S|) \approx O(N\log N)

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

4 Likes

" after erasing all elements of A outside the range and also erasing all elements whose values are outside the range", What is the difference between two ?

Thank you for pointing it out. Updated to make it clearer.

Mine implementation works in linear time.
Solution: 51748031 | CodeChef

Pardon me for writing this over here. But can someone please provide editorial for question MXMNSSUM of same lunchtime

2 Likes