PERMSUFF - Editorial

[kostya_by]

Problem Link: contest, practice

Difficulty: Simple

Pre-requisites: Sorting, Scanline

Problem:

Given a permutation P of N integers. Also, given M ranges (L_i, R_i). 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 = (L₁, R₁) and B = (L₂, R₂) 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 P_i 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 P₁ 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

[siddhartha4444]

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

My solution link : CodeChef: Practical coding for everyone

[aditya1495]

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

[rachilies]

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 …CodeChef: Practical coding for everyone…
(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 …)

[ayushj10]

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: CodeChef: Practical coding for everyone

Thanks

[mertiya]

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

[trophies]

Can anyone provide resources for the scanline algorithm?

[vedsarkushwaha]

its giving me ACCESS DENIED when I click on setter’s solution or tester’s solution.

[h43k3r]

I tried to solve this using Union Find.

I am using Union find to find the range.

http://www.codechef.com/viewsolution/4618833

I don’t know where this code is failing.

[deepsaggas]

Ah…nyc question…missed the case of Completely overlapping cases during contest(eg. [1,4] and [2,3]) and got WA…Fixed Now . Thanks @Witua and @Kostya_by

[sudharsansai]

can anyone tell me what is wrong with my solution?thanx in advance.
link to my solution is CodeChef: Practical coding for everyone any test case where my solution fails?

[vineet9888]

please explain the solution in a more elaborate way

[arp95]

i m still not able to understand.
If we sort the elements in query range for each query then in the last the array we should get is the permuted one if “possible” n “impossible” if not possible !!
pls help!!

[garg17793]

http://www.codechef.com/viewsolution/4621752
i used the union find approach. And for every interval i merge from a+1 to b.
and finally check of parent of index and target permutation should be same.
Please help me where i am wrong.
And provide resources of scanline algo. this tutorial was not so helpful me. Don’t know why this time i can not understand the problem.

[s183]

CodeChef: Practical coding for everyone Can anyone tell me why i am getting wrong answer…please help

[mjnovice]

Can this be solved by making a graph of the allowed permutation nodes, and then checking if P[i] and i, belong to the same component of the graph ? My solution, gives a TLE, but judging the complexity, why should it not pass ?

[alvarobsp]

I see a lot of ppl with questions about the scanline algorithm.
I couldn’t find any reference to it too, but I think that what they are referring as scanline is the algorithm to merge the intervals.
I didn’t understand the solutions first, but after rolling my own ‘merge’ code and getting AC, Setter’s solution made a lot of sense. I’ll try to explain how it works.

Imagine you have a vector of pair(int,int) called intervals, representing all the intervals you can choose, and you want to merge them, so as (2,5) and (4,7) become (2,7), for example. Assume that for a test case this have all the (Li, Ri) given and (i, i) for all i in (1…N) (since you can always ‘shuffle’ (i,i)

This is how the code would look like, using the algorithm from the setter’s solution (result is stored in the vector ‘merged’).

sort(intervals.begin(), intervals.end()); //need to sort it first
//l and r stores our current interval, starting with the first in the array
int l = intervals[0].first, r = intervals[0].second;
for (int i=1; i<intervals.size();  i++) {
    if (intervals[i].first > r) {
       //this condition means interval 'i' is out of our current (l, r) interval, so our old (l,r) is done
       merged.push_back(make_pair(l, r));
       // We start a new interval with information from intervals[i]:
       l = intervals[i].first; r = intervals[i].second;
    } else {
        //else, it means that the interval intersects (because it's sorted), so we just update the 'r' value with the maximum, merging the interval (l,r) with intervals[i]
       r = max(r, intervals[i].second);
    }
    merged.push_back(make_pair(l,r)); //push the last ones we were checking
}

This would be the ‘scanline’ algo, as far as I understand (compare it with the code from the setter’s solution).
Now, what the setter does is that he doesn’t really generate the ‘merged’ vector. Each time he has found a new interval, instead of pushing it to ‘merged’, he sorts the interval on the original permutation array. This works because, if it was possible to reach that state, you will get the original array (1…N) doing that.
By doing this, he also doesn’t need all the (i, i) intervals, since calling sort from i to i would be useless

In my solution ( CodeChef: Practical coding for everyone ) I did something similar to the scanline code above, but using a stack (the merge() function). Then I checked to what interval each number belonged using binary search (the intervalFor() function).
Needless to say, setter’s solution is faster and way more cleaver (although mine is also O(NlogN)), but check in case you still don’t understand, maybe it helps.

[deepak14036]

http://www.codechef.com/viewplaintext/5615453

My code is giving WA but it is giving me correct to me at all output.
So please tell me how it is wrong?

[empty_life]

For those getting WA , try this test case . Answer should be Possible . Hope this helps.

1
4 2
4 2 3 1
1 3
2 4

[geek_geek]

The method of uniting can be done without sorting
http://www.codechef.com/viewsolution/7308971

Have an Array of size P and for every l and r

do

p[l]+=1

p[r]-=1

and find cumlative sums and things between zeros are connected or united