PERMSUFF - Editorial

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

7 Likes

I used the same approach but always got wa any tricky cases ?

My solution link : http://www.codechef.com/viewsolution/4620285

To editorialist, consider a case n = 6, m = 2
a{} = {2 1 4 3 6 5},
1 2,
5 6.
Some accepted solutions are giving WA.
For ex : http://www.codechef.com/viewplaintext/4617643

2 Likes

Even me!
My solution link : http://www.codechef.com/viewsolution/4620410

No, it won’t give “possible” since 4 and 8 belong to different segments.

2 Likes

Yeah your approach is correct, so is mine.

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 …)

@Kostya_by: http://www.codechef.com/viewplaintext/4617643

It’s giving WA on : n = 6, m=2,
2 1 4 3 6 5

1 2
5 6
Giving possible but ans is impossible.

1 Like

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

Thanks :slight_smile:

Me too :frowning: My solution link :http://www.codechef.com/viewsolution/4620237

@p00r >> here is one test case on which your code fails:

4 3
4 3 2 1
1 3
2 2
3 4

P.S: I think there are some other bugs too in your code.

1 Like

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.

Tell me why my code giving wrong answer
My solution link is
http://www.codechef.com/viewsolution/4620861

Please check this testcase which is wrong by your logic’
1
4
3
4
3
2
1
1 2
2 3
3 4

1 Like

@apple1 >> your code also fails on the same above test case.

here is the link to your AC solution: 4621504

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

thanx !! for pointing that out…

Can anyone provide resources for the scanline algorithm?

10 Likes

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?

Thats the only bug. Fixed! Thanks!

//