# Thread: Two problems on k-ordered arrays

1. ## Two problems on k-ordered arrays

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  Reply With Quote

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

3.  Reply With Quote

4. @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.  Reply With Quote

5. 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.  Reply With Quote

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

a <= a <= a <= a ............ <= a[2n]
and
a <= a <= a <= a <= <= a[2n-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< = a <= a <= .............. a[2n].

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   Reply With Quote

7. For Q2 , I think the correct answer is 1.

The no. below are for array index ( eg: 3 = a)
For 2-0rdered :

0 1
2 3
4 5
6 7

where
0<=2<=4<=6
1<=3<=5<=7

For 3-ordered :

0 1 2
3 4 5
6 7 8

where
0<=3<=6
1<=4<=7
2<=5<=8

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

Correct me if I am wrong  Reply With Quote

8. Originally Posted by 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.
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  Reply With Quote

9. 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.  Reply With Quote

10. 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.  Reply With Quote