659 views | 659 views

Q1:

If the array is 1-ordered, it means that It is an array of ascending order. This is the only chance that it can be of 1-ordered.

It means that if array has 2N element and 1-ordered then its element can be of [1,2,3,4,5,...........,2N-1,2N].

Now an array can be 2-ordered only when its odd position is 1-ordered with odd position and even position is 1-ordered with even position element. So it can be arranged like this. [N+1,1,N+2,2,N+3,3,N+4,4,N+5,5,..........,N-2,2N-2,N-1,2N-1,N,2N].

So the maximum number of position difference can be N. ( See the First Element of both the array).

So, Option (e) is correct.

Q2:

The first element has to be <= the 3rd, 5th, ... elements by the 2-orderedness and <= the 4th,6th,... elements by the 3-orderedness and the 2-orderedness combined. So it has to be in either the 1st or 2nd position.
Suppose that the first element (if any) not in its usual position is the kth element. Then it has to be in position k+1 by a similar argument.
Now consider what must be in position k - it has to be k+1. If not it is bigger than k+1 and comes at least 2 before k+1 in the list, acontradiction.
So at worst k,k+1 have swapped places. Then the first k+1 places can not effect the remainder of the list (as
they must all be less than any element in the remainder of the list) so we can repeat the same argument further on. Thus the answer must be (d) i.e.1.