PERMSUFF - Editorial

general
, , ,
21

yjanin35: it is giving me Impossible, which is correct, it can be done with this approach

22

@freeman92 thanks a lot

23

can someone please point my bug please? http://www.codechef.com/viewsolution/4621820

24

Okay, I got it. For example if I query an interval which has the value 0 but if I break the current interval and all the constituent intervals have value 1 then the answer should be ā€œPossibleā€ while my code gives ā€œImpossibleā€.

25

its giving me ACCESS DENIED when I click on setterā€™s solution or testerā€™s solution.

26

@freeman92 Thanks a lot

27

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.

28

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

29

no ā€¦it should be ā€œpossibleā€

30

I thought of the same thing. It canā€™t work as segment tree doesnā€™t store all the possible intervals explicitly but rather as sum of intervals, which creates the problem here. [1,2] and [3,4] being ā€œconnectedā€ separately doesnā€™t mean that [1,4] is ā€œconnectedā€ necessarily.

31

Exactly. It canā€™t be solved using segment trees. You got my point.

32

I try to solve this problem by using segment tree

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

Can anyone give me some test case pleaseā€¦

33

I also try to slove this one by segment tree . But getting WA :frowning:

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

Any test case please ?

34

I donā€™t think the problem is solvable using seg trees. On the basis of above observations, you can create many test cases where the approach would fail.

35

rachilies: how can it be possible, could you show it step by step. n is 4 3 2 1 so when shuffling 1 2, it can be 3 4 2 1, so after this even if we shuffle 2 3 or 3 4 it ainā€™t gonna do any good to 3 which is in first position, so it should generate impossible

36

Sorry, i missed that part of can use the pair more than once, yeah it should be possible, and we are suppose to get the permutation given by user from initial permutation (1,2,3ā€¦N) using those pairs.
I was trying to solve by shuffling the input permutation to get the initial permutation (1,2,3ā€¦N).

37

can anyone tell me what is wrong with my solution?thanx in advance.
link to my solution is http://www.codechef.com/viewsolution/4624448 any test case where my solution fails?

38

please explain the solution in a more elaborate way

39

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!!

40

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.