k-ordered array problem

Question

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.

Answer 1

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.

Answer 2

2.) Suppose A=[1,2,3,4,5,6,7,8,9,10] index from 1-10. k=3 from condition 3 < i <=10-3 for i=4,5,6,7

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 4 A[1]<=A[4]<=A[7], i=5 A[2]<=A[5]<=A[8], i= 6 A[3]<=A[6]<=A[9], i=7 A[4]<=A[7]<=A[10]

3-ordered A=[1,4,7,2,5,8,3,6,9,10]

k=2 from condition 2 < i <=10-2 for i=3,4,5,6,7,8

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 3 A[1]<=A[3]<=A[5], i=4 A[2]<=A[4]<=A[6], i= 5 A[3]<=A[5]<=A[7], i=6 A[4]<=A[6]<=A[8], i= 7 A[5]<=A[7]<=A[9], i=8 A[6]<=A[8]<=A[10]

2-ordered A=[1,4,2,5,3,6,8,7,9,10] similarly 1-ordered A=[1,2,3,4,5,6,7,8,9,10]

so maximum position of the element is N/2 (see from 2-ordered A[8]=7 and from 3-ordered A[3]=7 so position = 8-3=5 but total number of element N=10 hence 10/2=5)

Now lets A=[1,2,3,4,5,6,7,8] index from 1-8. k=3 from condition 3 < i <=8-3 for i=4,5

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 4 A[1]<=A[4]<=A[7], i=5 A[2]<=A[5]<=A[8],

3-ordered A=[1,4,7,2,5,8,3,6]

k=2 from condition 2

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 3 A[1]<=A[3]<=A[5], i=4 A[2]<=A[4]<=A[6], i= 5 A[3]<=A[5]<=A[7], i=6 A[4]<=A[6]<=A[8]

2-ordered A=[1,4,2,5,3,6,7,8] similarly 1-ordered A=[1,2,3,4,5,6,7,8]

so maximum position of the element is N/2 (see from 2-ordered A[7]=7 and from 3-ordered A[3]=7 so position = 7-3=4 but total number of element N=8 hence 8/2=4)

Hence (C) N/2

1.) similarly , A=[1,2,3,4,5,6,7,8,9,10] index 1-10 2-ordered A=[1,4,2,5,3,6,8,7,9,10] 1-ordered A=[1,2,3,4,5,6,7,8,9,10]

so maximum position of the element is 2 (2-ordered A[2]=4, 1-ordered A[4]=4 hence position = 4-2=2 or 2-ordered A[5]=3, 1-ordered A[3]=3 hence position = 5-3=2)

Lets A= [1,2,3,4,5,6,7,8] 2-ordered A=[1,4,2,5,3,6,7,8] 1-ordered A=[1,2,3,4,5,6,7,8]

so maximum position of the element is 2 (2-ordered A[2]=4, 1-ordered A[4]=4 hence position = 4-2=2 or 2-ordered A[5]=3, 1-ordered A[3]=3 hence position = 5-3=2)

Hence (b) 2