http://www.codechef.com/viewsolution/4613635 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 ?
how for n=7 and m=1 where ar[]={4,5,6,7,1,2,3} and for m=1(l=1 and r=7) is giving answer possible as through it we can just shuffle a[0] and a[6].
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 ( http://www.codechef.com/viewsolution/4683513 ) 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.
2 Likes
added an answer explaining it (the way I understand, at least :P).
hope it helps: ( http://discuss.codechef.com/questions/50146/permsuff-editorial/50493 )
I think it can be solved with segtrees, but with a different approach. Assuming your tree has a efficient ‘range update’ function, you could:
For each node, store the lowest node it is connected to (initially, the value is the i itself). Now, every time you get a interval (L, R), you query what is the value of node L, then range_update(L+1, R, value_of_L); Then assuming the value x is in position i of the permutation array that was given, you need to check if the value of node x is the same of node i in the tree.
Kinda overkill, since it uses only the range update, but not any range query
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 4The 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