4
$\begingroup$

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.

$\endgroup$

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer! So, if I am correct, the Q1's answer is n/2 ?? $\endgroup$ May 18, 2014 at 18:05
  • 2
    $\begingroup$ @GaurangTandon I don't know. Not that you understand the question, you should be more confident in the answer. Try to convince yourself that your answer is correct. $\endgroup$ May 19, 2014 at 0:43
  • $\begingroup$ I think I got it: Q1 = 2, and Q2 = 1, and the array both 3-ordered and 2-ordered is [1, 2, 3, 5, 4, 6, 7, 8]. I think now that this is indeed the correct answer. $\endgroup$ May 19, 2014 at 12:41
-1
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ I recommend that you use Latex, and proof-read your answer before writing) - as it stands this is a wall of text that is quite imposing. $\endgroup$
    – D.W.
    May 22, 2014 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.