Two problems on k-ordered arrays

[taro_curly]

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

 

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

 

for all i such that 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

[f2003800]

answer for Q1 is n/2 which can be found by verification of given example!!!

[ethanph]

q2 is d, i think

[taro_curly]

@f2003800

 

Do you know of a more analytical way in which this problem can be approached? Relying on an example can be misleading...

 

@ethanph

 

If the array was at least 2-ordered, the answer should be atleast as large as the answer to Q1.

[grabanca]

Consider the 2-ordered Array of size 10 (n = 5)

1 6 2 7 3 8 4 9 5 10

 

6 is put into position 2 instead of position 6 => distance is 4, which is greater than n/2. So the answer could only be n or 2n-1. Thinking about the fact that any number is sorted in raport to n other numbers leads to the conclusion that the answer is n.

[R0jkumar]

For the 1st question, if the array is 2-ordered, then the elements are such that the following hold :

 

a[0]

and

a[1]

 

In other words, we have 2 non-decreasing sequences of numbers each of length n. And 1-ordered is basically a sorted array.

 

In a sorted array we have

 

a[0]

 

If you take any number from a 2-ordered list, it is already in its correct position relative to the rest of the (n-1) numbers from the same list but it maybe out of order with respect to the n-numbers from the other list. Hence each number can be a maximum of n-positions from its correct position in the sorted list.

 

 

I am still thinking about the second part :)

[iamdaisy]

For Q2 , I think the correct answer is 1.

 

The no. below are for array index ( eg: 3 = a[3])

For 2-0rdered :

 

0 1

2 3

4 5

6 7

 

where

0

1

 

For 3-ordered :

 

0 1 2

3 4 5

6 7 8

 

where

0

1

2

 

This implies that we can only choose between the positions 0 and 1.

 

Correct me if I am wrong

[f2003800]

@f2003800

 

Do you know of a more analytical way in which this problem can be approached? Relying on an example can be misleading...

 

@ethanph

 

If the array was at least 2-ordered, the answer should be atleast as large as the answer to Q1.

 

i didn't notice "maximum number of positions" in teh given problem. I just checked it for the given example... it led to wrong answer :( ..... the number of positions vary...

 

thanks taro_curly

[grabanca]

My answer for Q2 is E as well, though I am not sure...

 

Any number is ordered correctly relative to n-1 other items. It is also ordered correctly relative to 1/3 of the remaining items (because it is 3-ordered) which implies that a number is ordered correctly relative to |_4n/3_| items. Generally a number can be up to [2n/3] positions away from its place in the ordered array.

For n = 1, 2n/3 = 1 as well.

 

Ex. [2,1] is 2-ordered and 3-ordered, n=1 and the maximum distance is 1.

 

I would choose 2n/3 if there were such a choice. Otherwise I think n makes most sense.

[admiyo]

If an n-ordered subset is all of the numbers that are n ordered together, then any number is in two n-ordered subset, one that is 2 ordered and one that is three ordered. When there was only a single 2 ordering forced on the whole set, there was no relationship between the subset beginning with the first value and the subset beginning with the second value. Same with three orderings: there are three distinct sets. I'll label the two ordred subsets s2-1 and s2-2, and the three 3ordered sets as s3-1 s3-2 and s3-3.

 

If you only have to deal with s2-1 and s2-2, you can have the case where the loweset value in s2-2 is greater than the highest value of s2-1 as in this set {1, 7, 3, 9, 5, 11}. However, since a set is both two and three ordered, there is a relationship forced by the fact that a given value is in both sets. The set {1, 7, 3, 9, 5, 11} fails 3 ordering because 7 > 5. Thus 1/6th of the numbers are going to common between each 2 ordered and 3 ordred subset. The question is how much "wiggle room" do you have?

 

The fully ordered set {2, 6, 8, 10, 11, 12, 13 ,14, 17 } Is 2 ordered and three orded. Within the 2 ordering, I can switch any two adjacent values and still be two ordred. Within the three ordering, I can switch any value with the one two prior or two after it and still be three ordred. Additionally I cannot switch any value with a member of a disjoint n-set further away, as I will violate the ordering of one or both sets.

 

Take the smallest value and:

Move it one away {6, 2, 8, 11, 10, 12, 13 ,14, 17 } OK

Move it two away {8, 6, 2, 10, 11, 12, 13 ,14, 17 } and violate the ordering of n2-1

Move it three away {10, 6, 8, 2, 11, 12, 13 ,14, 17 } and violate the ordering of n3-1

Move it four or more away and violate the ordering of n2-1

{11, 6, 8, 10, 2, 12, 13 ,14, 17 }

{12, 6, 8, 10, 11, 2, 13 ,14, 17 }

{13, 6, 8, 10, 11, 12, 2 ,14, 17 }

{14, 6, 8, 10, 11, 12, 13 ,2, 17 }

{17, 6, 8, 10, 11, 12, 13 ,14, 2 }

 

 

 

from a relationship perspective Each position is in a sub set of ordering with the other positions marked with an X below.

 

1 2 3 4 5 6 7 8 9

1|X|

2|O|X|

3|X|O|X|

4|X|X|X|X|

5|X|X|X|O|X|

6|O|X|X|X|O|X|

7|X|O|X|X|X|O|X|

8|O|X|O|X|X|X|O|X|

9|X|O|X|O|X|X|X|O|X

 

In order to swap the values in a position between two fields with out violating ordering, there must be no relationship between these fields. Thus two can swap with 9...or can it? 6 and 9 have a three ordered relationship. 6 and two have a two ordered relationship. Swapping 2 and 9 violate the two ordered relationship between 2 and 6.

 

What if we tried a three way swap? 2->6 6->9 9->2? No go, as 2 and 6 are still two ordered, and the original value in 9 would be greater than the original value in 6.

 

How about 1 and 6? If we swap the values in these positions, 2 ordering between 1 and 3 will be violated.

 

Answer is 1.

[Payel Maity]

For Q2 , I think the correct answer is N.

 

 

If we take an array of 2N elements where N=6.

Now, A[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] be an array for eg.

 

For 2-0rdered :

0 1

2 3

4 5

6 7

8 9

10 11

where

0

1

 

For 3-ordered :

 

0 1 2

3 4 5

6 7 8

9 10 11

 

where

0

1

2

 

 

now lets take the 10th element i.e. A[10]=9 . in 3 ordered its position is in 4th where as in 1 order its position is in 10th. so (10-4=6 ) ie. N position far .