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,…,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,…,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(nlogn) 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,…,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(nlogn) cost?
[Solution]
No comments:
Post a Comment