Sponsored Ad:
Page 1 of 2 12 LastLast
Results 1 to 10 of 11

Thread: Two problems on k-ordered arrays

  1. #1
    Trying to make mom and pop proud
    Join Date
    Oct 2007
    Posts
    22
    Rep Power
    13


    Good post? Yes | No

    Two problems on k-ordered arrays

    Sponsored Ad:
    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

  2. #2
    Within my grasp! f2003800's Avatar
    Join Date
    Sep 2007
    Posts
    110
    Rep Power
    13


    Good post? Yes | No
    answer for Q1 is n/2 which can be found by verification of given example!!!
    Last edited by f2003800; 10-22-2007 at 10:49 AM. Reason: better explanation

  3. #3
    Eager!
    Join Date
    Oct 2007
    Posts
    31
    Rep Power
    13


    Good post? Yes | No
    q2 is d, i think

  4. #4
    Trying to make mom and pop proud
    Join Date
    Oct 2007
    Posts
    22
    Rep Power
    13


    Good post? Yes | No
    @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.

  5. #5
    Trying to make mom and pop proud
    Join Date
    Sep 2007
    Posts
    23
    Rep Power
    13


    Good post? Yes | No
    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.

  6. #6
    Eager!
    Join Date
    Mar 2005
    Posts
    41
    Rep Power
    16


    Good post? Yes | No
    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

  7. #7
    Eager!!
    Join Date
    Oct 2007
    Posts
    28
    Rep Power
    13


    Good post? Yes | No
    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

  8. #8
    Within my grasp! f2003800's Avatar
    Join Date
    Sep 2007
    Posts
    110
    Rep Power
    13


    Good post? Yes | No
    Quote Originally Posted by taro_curly View Post
    @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

  9. #9
    Trying to make mom and pop proud
    Join Date
    Sep 2007
    Posts
    23
    Rep Power
    13


    Good post? Yes | No
    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.

  10. #10
    Trying to make mom and pop proud
    Join Date
    Oct 2007
    Posts
    1
    Rep Power
    13


    Good post? Yes | No
    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.

Page 1 of 2 12 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Ordered pair (n,r) is
    By sheelanadh in forum GMAT Problem Solving
    Replies: 1
    Last Post: 08-11-2010, 11:04 PM
  2. ordered a Kindle today - your thoughts?
    By bheld in forum Lounge
    Replies: 5
    Last Post: 02-21-2009, 06:07 PM
  3. ordered pairs
    By dynamicdhiraj in forum GMAT Problem Solving
    Replies: 4
    Last Post: 05-24-2008, 04:32 PM
  4. OG problems vs. problems in the test
    By janson54 in forum GMAT
    Replies: 1
    Last Post: 10-08-2007, 08:49 PM
  5. Replies: 1
    Last Post: 01-27-2003, 11:36 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •