This is a programming problem that I'm trying to solve at TopCoder arena. However, I feel like it need Mathematics to prove its correctness.
Problem
Given a list $L$ of $n$ elements, and a number $k, k \leq n$, where $k$ defined as a number consecutive elements can be reversed. For example: $L = \{ 4, 3, 2, 1 \}$ and $k = 3$
reverse at $0$ yield a new list $L = \{ 2, 3, 4, 1 \}$
So our goal is to sort the list in ascending order by reversing $k$ element each time if possible.
My question is, what condition must be hold in order to have an impossible case? And how to find the fewest moves in term of $n$ and $k$? Here are few examples:
{1,2,3} 3 Fewest move is 0 {3,2,1} 3 Fewest move is 1 {5,4,3,2,1} 2 Fewest move is 10 {3,2,4,1,5} 4 This is impossible case
Thanks,