answer for Q1 is n/2 which can be found by verification of given example!!!
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
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.
For the 1st question, if the array is 2-ordered, then the elements are such that the following hold :
a[0] <= a[2] <= a[4] <= a[6] ............ <= a[2n]
and
a[1] <= a[3] <= a[5] <= a[7] <= <= 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[0]< = a[1] <= a[2] <= .............. 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
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<=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
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.
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.
There are currently 1 users browsing this thread. (0 members and 1 guests)