## IPSC 2006

## Solution to Problem B – Biased Standings

Computing the answer is surprisingly simple: Sort the teams
according to the position where they want to finish, and compute
the badness for this ranklist.

Why does this solution work? Let's rephrase the problem statement
in an equivalent way: Imagine that initially we put each
team on the place where they want to be. Now we need to move some
of the teams so that no two teams occupy the same place.
Moving one team by one place costs us one coin, and we want
to minimize the cost. (Before reading any further, convince yourself
that this is really an equivalent task.)

We claim that there is an optimal solution such that if at the
end some team A is better than some team B, then in the beginning team A
wasn't worse than team B. (In other words, all teams maintained
their original order, we only split ties.)

Why is it so? Take any optimal solution, write down the moves you
made, but omit the team names – for each step write only "I moved
a team from place X one place up/down". Now, put the teams back on
their desired places and "replay" the solution according to your
notes, with two additional rules:

- If I have to move a team from place X to X-1, I move the team
with the best desired place (out of the teams currently on place X).
- If I have to move a team from place X to X+1, I move the team
with the worst desired place (out of the teams currently on place X).

This way we will get an equally good solution, and it can easily be seen
that at any moment all the teams are ordered by their desired places.