PERMSUFF - Editorial

general
, , ,
41

no …it should be “possible”

42

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.

43

Exactly. It can’t be solved using segment trees. You got my point.

44

I try to solve this problem by using segment tree

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

Can anyone give me some test case please…

45

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

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

Any test case please ?

46

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.

47

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

48

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

49

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

50

@kostya_by Can you provide the link for scanline algorithm please

51

The code didn’t render correctly, here it is:

52

added an answer explaining it (the way I understand, at least :P).
hope it helps: ( PERMSUFF - Editorial - #17 by alvarobsp - general - CodeChef Discuss )

53

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