A datastructure for Robotic Sort

Question

I am trying to solve this problem :

https://www.spoj.pl/problems/CERC07S/

I have identified that i need a datastructure in which reversing operations have lesser time complexity. I tried to create one using a doubly linked list, in which (i thought) reversing can be done in O(1) by just changing a value associated with the starting and ending node which indicates the direction of traversing the list. I tried to implement it but got stuck. Maybe the approach is wrong!

Are trees applicable here? If yes, how? Any ideas or links are appreciated?

Thanks in advance.

Answer 1

This is a Selection sort in disguise. You are right about O(1) reversal using doubly linked lists. (Don't be confused about the lists being into another list. You could remove the sublist to be reversed, reverse, and reinsert it, all in O(1), or whatever makes your code simpler).

I understand this is just an exercise, but one can note that the reversal doesn't matter, all that matters is the swapping of the first and the last elements. This is all it takes to maintain the invariant at step i, the list up to position i is sorted. For larger i's, the list contains has an undefined order. If you reverse an undefined order, all you have is still an undefined order :)

Answer 2

Dimitris is right about what this algorithm really is, in effect. That said, considering the problem does actually require that you perform reversals, a doubly linked list is appropriate. And you are right about reversing in O(1). What might have gotten you stuck was this part:

[I thought] reversing can be done in O(1) by just changing a value associated with the starting and ending node...

The trick is not to specifically do anything to the nodes, but rather to the list itself (i.e., the object encapsulating the list's structure); change its state so that to iterate, it starts on its last node and goes backwards from there. If the list's mutability were to be maintained (not relevant in this example), you would also make this state responsible for ensuring that methods which previously purported to add nodes to the end of the list would add them to the "beginning" (the new end) and vice versa. Intuitively, this "state" would really just be a simple binary switch indicating whether the list were reversed or not.

Answer 3

I agree with the doubly linked lists. Here's one way to implement it.

For each node, have the two pointers as an array. Also in the node have the value of the number and a boolean variable dir. Initially, point the first pointer in each node to the previous node, point the second pointer to the next node, and set dir for all nodes to 0. As you traverse the linked list, keep track of a variable that has the direction, D. Set it to 1 at first. It indicates which pointer to follow to get to the next element at each node. When you arrive at a node, if dir is set to 1, set D to the NOT of D and continue to use D to find the next node.

To reverse a sequence of nodes, set dir to the NOT of dir in the last node and the node after the last node of the sequence of nodes that you want to reverse, point the correct pointer of the node before the sequence to the last element of the sequence (and vice versa), and point the correct pointer of the node after to the sequence to the first element of the sequence (and vice versa).

Hopefully, that gives you some idea of at least one way to go forward.