In a previous post, we were asked to sort an array (of size $n$) consisting only of the elements 0,1 and 2. The catch being: the only write operation on the array that was allowed was to reverse a sub-array $A[i, i+1, \dots, j]$.
The task was to use $O(n)$ reversals.
This problem is similar. We still have an array of zeroes, ones and twos, and we can only write by doing reversals.
The difference is that the reversal has a cost associated with it.
Reversing the sub-array $A[i, i+1, \dots, j]$ has cost $j-i+1$ associated with it (similar to what you would normally pay when doing an actual reverse).
Can you now sort the array with $O(n \log n)$ cost?
[Solution]
The task was to use $O(n)$ reversals.
This problem is similar. We still have an array of zeroes, ones and twos, and we can only write by doing reversals.
The difference is that the reversal has a cost associated with it.
Reversing the sub-array $A[i, i+1, \dots, j]$ has cost $j-i+1$ associated with it (similar to what you would normally pay when doing an actual reverse).
Can you now sort the array with $O(n \log n)$ cost?
[Solution]
No comments:
Post a Comment