Okay so I’ve been working upon this question for a long time now:
The question requires the implementation of the “Scanline Algorithm”, but I was wondering if this could be solved using the simple union-find method.
Here is my proposed solution: http://www.codechef.com/viewsolution/5676061
But all I’ve been getting is a series of WAs and have exhausted out of test data where my solution might fail.
Would greatly appreciate any help from you guys as to where my solution might be failing.
3 3 3 3 3
Check this Edit:
2 1 4 3 6 5
 gives `impossible` while it's `possible`. It's the mistake in your logic you need to correct. If you'll go by your code and see how it's working when `li=ri`, it then becomes simple to get the case. I'd like to mention here that for getting the test cases to test, always explore the possibilities and then see how your code should work for that manually and then check your output and the one your code is giving.
Hey, thanks for reaching out to me but isn’t the input array needs to be a permutation of the numbers [1,n] ?
Oh, I missed that point. But I tested my code for this case and it gave “possible”. I’ll see to it once again, but then there’s surely some test case in test file then according to the constraints.
I just did a check for that too, still WA
Hey wait nellex … i am telling you problem in your code …
I would like to tell you that you have understood the problem the problem … wrongly … dear…
Problem says that you can shuffle all the elements in the range from L to R… and you have done it for where we can swap element L and R … Here is my AC solution for this problem …
I am posting a test case for which your solution will give wrong result …
@nellex check the above edit… Your code gives impossible but the answer is possible…
look at this simple test case dear
2 1 3 4 5
it is possible to obtain this but your code is giving impossible …
Hey first of let me tell you what is he doing in his code… if you have checked then he is just making an edge between the pair of integers and then just finding the connected components right …
let us consider … we have five elements in the arrays names as
A B C D E respectively …
2 segments …
what does that mean according to his code …
A,B,D are connected and he can change position of these elements to obtain the given permutation right …
I solved this problem during the contest itself and also my code is bit clear you can understand it …
I am just merging the segment which can be possibly merge and checking whether i have all the element in the merged range which i need to make the required permutation …
If you find anything difficult please post i will help you in getting this surely …
Yeah, thanks. I just missed that part of the code, Even I solved during the contest by merging the intervals and then did the same check as in your code. Thanks for the help…
Haha…damn it…Thanks a ton for pointing that out bro. Will try it now and get back to you if there’s some problem.
sure brother and wishing you both a very happy new year…
btw you can try logic on this problem it is essentially same …
Haha…that was the question which inspired me to apply the same logic to this one but this one’s for range that one is directly for indexes.