warehouse problem of IEMCO6!

can anyone explain how to solve warehouse problem of IEMCO6!
link to question—https://www.codechef.com/IEMCO6/problems/IEMCO6B

Let f(i) be the minimum cost for the subarray A_{1..i} such that A_i is not swapped with A_{i-1}.
Similarly, let g(i) be the minimum cost for the same subarray if A_i and A_{i-1} are swapped.

Then, figuring out a little gives the relations

\begin{aligned} f(i) &= \min(|A_i - A_{i-1}| + f(i-1), |A_i - A_{i-2}| + g(i-1)) \\ g(i) &= \min(|A_{i-1} - A_i| + |A_i - A_{i-2}| + f(i-2), |A_{i-1} - A_i| + |A_i - A_{i-3}| + g(i-2)) \end{aligned}

These should make sense, but I can explain further if you want me to.

Of course the answer is simply \min(f(n), g(n)).


thanks bro!!

No problem :slight_smile: