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.
I tried solving the problem using following approach …
suppose we have permutation P(for example P={3 1 2 4 5 7 6} )…and now given N-1 queries…
now for each query …sort this permutation arr P…from L to R …and at the end of all queries…
we check in the modified P …whether …P[i]==i+1 …if that is true than possible otherwise Impossible…test cases satisfied …checked some manual inputs …no problems …but still WA,
was my approach correct …or i have misunderstood the problem …
here is my solution …http://www.codechef.com/viewsolution/4616992…
(P.S …as it can easily be understood after sorting the P on each query range …we will have a sorted version of P .and if its not sorted then ans is Impossible …)
Can’t this problem be solved with segment trees? In all the m queries, I marked the interval specified with value=1 in the segment tree which signifies that this interval is “well connected”.
In the end I just check if the interval consisting of destination position of a no and it’s original position is “well connected” or not. i.e. if the value in the segment tree for the given interval is 1 or not. I am getting WA after a running time of 0.90s. Any test case/flaw with the approach?
Here is my solution: http://www.codechef.com/viewsolution/4620580
no in that case …even for disconnected ranges it may assume that is connected …for example …for query …1 2 2 3 and 4 4…here connected range should be only from 1-3 but in ur case it would considering 1-4 …because 4 will also be updated to 1.
I have followed the same approach of sorting every range (storing them in a temp array and then updating the original list).
it will take n^2 time, and hence i got time limit exceeded error when i submitted. You might have done some mistake
Yes, I’ve got what you’re trying to say. But I have not called the update function if both the no’s in the interval are same. So it perfectly runs fine for the case you’ve specified. There is something else which is probably going wrong. Are you able to pinpoint what’s missing?
My solution link :