First I thought this could be a complicated problem, but soon I wrote a 20 line code and got accepted at first submission.
Many ideas passed through my mind and I would like to share them with you.
Let's say we have an algorithim that flips adjacent numbers, but it's not optimal. What makes it non-optimal is the non-required flips it makes.
By the way, what is a non-required flip? It's any flip that's done towice (two numbers being fliped once and unflipped later).
An optimal algorithim does all the required flips but any of the non-required ones. So:
O = T - N
O: Optimal number of flips
T: Total number of flips an algorithim does
N: Non-required flips it does
So we can count the flips (T), discover which were non-required (N) and calculate the O.
But we can go further, because the non-required flips can be recognized without doing them. A non required flip is the one that will need to be undone. So it's a flip that puts a bigger number after a smaller one:
100 50 -> this flip will need to be undone
It's clear that the number N will always be a even number.
Note now that the number of required flips can also be identified. Look at the number 7 in the sequence below. With how many other numbers do you think it needs to flip?
The answer is simple, just count how many numbers greater than 7 exist at it's LEFT and now many numbers smaller than 7 exist at it's RIGHT. All of those need to be flipped with the number 7.
5 1 7 2 6 3 8 4 9
Now, forget about the 7 (or erase it) and do the same process with each one of the other numbers, and you have counted ALL of the REQUIRED flips you need to do
For an easy algorithim, start with the number X at left, count the required flips (how many numbers smaller than it exist on it's right) and forget about such number X.
Repeat this process untill you have "forgotten" all of them.
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180