Internet Problem Solving Contest

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:

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.