Marathon Match 120
Topcoder MM 120 - **ReversalSort** is now live!
Problem Setter: dimkadimon
Problem Testers: JacoCronje and kphmd
Problem Overview:
You are given a sequence S containing **N** numbers in the range [0, **K**). Your task is to sort this sequence into monotonically increasing order, in a way that incurs the smallest penalty. You are allowed to select any contiguous sub-sequence of numbers and reverse their order. Formally, if the sub-sequence is (S[i], S[i+1], ..., S[k-1], S[k]), where 0 <= i < k < **N**, then its reversal is (S[k], S[k-1], ..., S[i+1], S[i]). The penalty incurred by this reversal is floor[(k-i+1)^**X**], where **X** is a given penalty parameter. Your task is to minimize the total penalty incurred by all the reversals.
Best of luck!
- the Topcoder Team
