Problem Link: contest, practice
Difficulty: Simple
Pre-requisites: Sorting, Scanline
Problem:
Given a permutation P of N integers. Also, given M ranges (Li, Ri). You are allowed to perform the next procedure a finite number of times: choose any given range (L, R) and shuffle subsegment P[L…R] arbitrarily. You are to determine if it’s possible to obtain P out of the 1, 2, …, N permutation.
Explanation:
At first, let’s assume, that all the ranges don’t intersect(it means, that for any two given ranges A = (L1, R1) and B = (L2, R2) there’s no integer K, that simultaneously belongs to A and B). If that’s not true, than we can unite some of the ranges with a help of scanline algorithm(check out Setter’s and Tester’s solutions if you are not familiar with that algorithm).
So, all the ranges don’t intersect. Then the solution is pretty easy: the answer is “Possible” if and only if i and Pi belong to the same range for each i.
It’s may be not clear why it’s OK to unite some ranges. But it’s not hard to prove the correctness of this approach: we can construct permutation P element-by-element, starting with putting P1 on the first place and so on. We can perform the putting stage of the algorithm with some greedy approach.
Total complexity is O( N log N ) per testcase.
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link