k-ordered array problem

Problem Detail: 

An array $A[1...n]$ is said to be k-ordered if

$$A[i - k] \leq A[i] \leq A[i + k]$$

for all $i$ such that $k < i \leq n - k$.

For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.

Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2 c) n/2                 d) 1                 e) n 

Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2 c) n/2                 d) 1                 e) n 

I can understand how the example array is two ordered, but I am having trouble understanding what the questions 1 and 2 are trying to say.

Can someone please explain to me the meaning of the questions in simple terms?

Thanks!

P.S. First time questioner here. Sorry if I missed anything.

Asked By : Gaurang Tandon

Answered By : Yuval Filmus

Take your example $$ A = [1,4,2,6,3,7,5,8]. $$ An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together: $$ 1,4,2,6,3,7,5,8 \\ 1,2,3,4,5,6,7,8 $$ You can see that matching digits are at distance at most 2.

An array is 2-ordered if its even elements are 1-ordered and its odd elements are 1-ordered. This could be helpful in question 1. A similar property is true for 3-ordered arrays. How do these two properties combine? I suggest you try writing out a few 2- and 3-ordered arrays to see what the possibilities are.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25839