PERMSUFF - Editorial

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

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 ?

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 :slight_smile:

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 :stuck_out_tongue: (although mine is also O(NlogN)), but check in case you still don’t understand, maybe it helps.

2 Likes

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?

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

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

Can anyone tell a test case why my


[1] is giving WA.


  [1]: https://www.codechef.com/viewsolution/7523518

Here is O(N) approach.

https://www.codechef.com/viewsolution/10054840

Even me!
My solution link : CodeChef: Practical coding for everyone

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

2 Likes

Yeah your approach is correct, so is mine.

@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

Me too :frowning: My solution link :CodeChef: Practical coding for everyone

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

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…

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?