Find the Order of boxes

Question

There are boxes on the shelf, and each box has an ID number associated with it. There are Q queries.

Each query is in the form l r, and the query is executed by moving all boxes in the inclusive range to the head (front) of the shelf.

Given queries and the initial ordering of all boxes, can you find the final ordering of the box IDs on the shelf?

Sample Input:

6
1 2 3 4 5 6
3
4 5
3 4
2 3

Sample Output:

2 4 1 5 3 6

Explanation:

The shelf initially looks like this: [1,2,3,4,5,6]. We execute our queries in the following order:

1. Move the 4^th and 5^th items to the front, so our shelf looks like this: [4,5,1,2,3,6]
2. Move the 3^rd and 4^th items to the front, so our shelf looks like this: [1,2,4,5,3,6]
3. Move the 2^nd and 3^rd items to the front, so our shelf looks like this: [2,4,1,5,3,6]

We then print this final ordering of ID numbers as our answer.

Question Link

Is there any better solution than O(Q*N)?

Answer 1

(See also Kundor's excellent explanation of how Onaka uses a treap-like structure (How does a treap help to update this ordered queue? ).)

A rope structure can allow for an O(m log n) time solution. Each node in the binary tree, except for the root, stores the weight of its left subtree; in our case, weight is the number of elements. The current order of our list is stored in the leaves from left to right.

The subtree containing the current ith to jth elements can be accessed in O(log n) time by following the nodes: if i is less than the node weight, go left; otherwise, subtract the weight of the left node from i and go right.

To move the elements, split the subtree containing them, (update the side edges), and concatenate the split-off section with the front of the tree. You may need to think about how to keep the tree reasonably balanced.

The following example stores the indexes of the elements in the original list (non zero based), rather than the elements themselves, to allow for range entries (e.g., 1-3):

input [1,2,3,4,5,6]

rope     6
       (1-6)


1. Move 4th-5th to front:

         2    |    3    |   1
split  (4-5)  |  (1-3)  |  (6)

concat          6
                5
         2              1
   (4-5)   (1-3)       (6)


2. Move 3rd-4th to front:

split           4           |
                3           |
         2              1   |     2
   (4-5)    (3)   (6)       |   (1-2)

concat         6
       2                 3
     (1-2)         2           1
             (4-5)   (3)      (6)

3. Move 2nd-3rd to front:

split        4                 |
       2             2         |
      (1)       1         1    |     2
             (5) (3)     (6)   |   (2,4)

concat        6
              3
       2               2
   2       1       1        1
 (2,4)    (1)   (5) (3)    (6)

Answer 2

As Gassa points out, you can use a splay tree for this.

In (untested!) C, the structure would look like

// Splay tree of boxes
struct Box {
    struct Box *left;  // root of the left subtree
    struct Box *right;  // root of the right subtree
    struct Box *parent;
    int left_size;  // size of the left subtree
    int id;  // box id
};

Some basic manipulation routines:

void box_init(struct Box *box, int id) {
    box->left = box->right = box->parent = NULL;
    box->left_size = 0;
    box->id = id;
}

void box_link_left(struct Box *box1, struct Box *box2, int box2_size) {
    box1->left = box2;
    box1->left_size = box2_size;
    if (box2 != NULL) {
        box2->parent = box1;
    }
}

void box_link_right(struct Box *box1, struct Box *box2) {
    box1->right = box2;
    if (box2 != NULL) {
        box2->parent = box1;
    }
}

// Changes
//
//     box         left
//    /   \        / \
//  left   c  =>  a  box
//  / \              / \
// a   b            b   c
void box_rotate_right(struct Box *box) {
    struct Box *left = box->left;
    struct Box *parent = box->parent;
    if (parent == NULL) {
    } else if (parent->left == box) {
        parent->left = left;
    } else {
        parent->right = left;
    }
    box_link_left(box, left->right, box->left_size - left->left_size - 1);
    box_link_right(left, box);
}

void box_rotate_left(struct Box *box) {
    // code here
}

void box_splay_to_root(struct Box *box) {
    // code to bottom-up splay here
}

struct Box *box_rightmost(struct Box *box) {
    while (box->right != NULL) {
        box = box->right;
    }
    return box;
}

The unusual parts are finding a box by index:

struct Box *box_at(struct Box *root, int i) {
    struct Box *box = root;
    while (1) {
        if (i <= box->left_size) {
            box = box->left;
            continue;
        }
        i -= box->left_size;
        if (i == 1) {
            return box;
        }
        i--;
        box = box->right;
    }
}

and doing surgery on the box order:

struct Box *box_move_to_front(struct Box *root, int l, int r) {
    if (l == 1) {  // no-op
        return root;  // new root
    }
    struct Box *br = box_at(root, r);
    box_splay_to_root(br);
    // cut right of br
    struct Box *right_of_r = br->right;
    br->right = NULL;
    struct Box *bl1 = box_at(br, l - 1);
    // cut right of bl1
    struct Box *mid = bl1->right;
    // link
    bl1->right = right_of_r;
    // link
    mid = box_rightmost(mid);
    box_splay_to_root(mid);
    box_link_right(mid, bl1);
    return mid;  // new root
}

Answer 3

There is a rather simple practical solution to this.

It's based on appending numbers to the original data, [number of picks] times, while maintaining an index array. Then one grabs the result from the data, using that index array.

The idea is to work n the right side of the array, as most systems support efficient appending. Alternatively, one can right from start append [2 * number of picks] zeroes to the data, to then be later on filled.

This requires having the original data mirrored.

Pseudo:

data = 6 5 4 3 2 1  // Mirrored original data, an integer array, will increase in size

ind = 6 5 4 3 2 1   // A fixed size, length-6 (tot nr of picks) integer array

picks = (5 4)       // Row 1 - mirrored 2-column (and 3 row in this example) table
        (4 3)       // Row 2
        (3 2)       // Row 3

s = 6               // 6 is the total number of picks, ie. 2 * 3 (cols * rows)

:For row :In 1 2 3  // Loop through the pick rows
    a = 1 + s - picks[row;] // a is now a 2-element array, as picks[row] is 2 elements
    data ,= data[a] // Adding 2 elements to data per each cycle
    s += 2
    ind[data[a]] = (s - 1), s // 2 elements of ind get assigned (overwritten) here
:End

// Grab the result
// data is now: 6 5 4 3 2 1 5 4 2 1 4 2
// ind is now: 10 12 4 11 7 1
order = [grab the ascending sort order of ind] // Will be 6 3 5 1 4 2 in this example
result = data[ind[order]]     // Will be 6 3 5 1 4 2
result = [reverse of] result  // Will be 2 4 1 5 3 6

There is an alternative way to grab the result, where no index maintenance (ie. ind variable) or sorting is needed:

// Grab the result 2:
result = [unique] [mirror of] data

Imho, there exists no magic to get the result. This solution is pretty much proportinal in time to the number of picks.