k-ordered array problem

ignougroup
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