Editorial for Baltic OI '07 P2 - Sorting


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Important observations

When looking at the description of what happens when moving a player, we can see that if we move a player towards the front of the list, the moving cost of some other players increases, whereas if we move a player towards the end of the list, the moving cost of some other players decreases. So, it might be helpful to move players first which have to be moved towards the end of the list to decrease the moving costs of future moves. This observation may lead to the following two ideas:

  1. Each player is moved at most once.
  2. The players who are moved are moved in ascending order according to their score.

A proof that these two ideas are correct will follow later.

Brute force solution

Using the two ideas mentioned above, a brute force solution would try all selections of players to be moved, and then move them to their required position in ascending order according to their score. The complexity of this solution would be \mathcal O(n^2 \cdot 2^n).

Dynamic programming solution

Let the players be numbered from 1 to n according to their final position in the ranklist. With dynamic programming, we want to determine the minimum cost to get the players i \dots n in their correct relative order with the first of these players at original position j. It is tricky to determine the current position of the next player to be moved. It would be far easier if we knew that all players (i+1) \dots n already moved towards the end of the list; in that case, in order to determine the current position of player i, we could count how many players with bigger scores exist which have an original index position smaller than player i. Obviously, if some of the players with the n-i smallest scores didn't move, the current position for player i determined by this method can be too small.

However, if we assign a moving cost to each player who doesn't move, we can take care of the underestimated moving cost for players with bigger score. Let's see what happens if we didn't move player j. This means that players with bigger score will be moved before him, so when determining the position of a player i which appears after player j in the list, the determined rank would be too small by j-i. So the moving cost for a player who doesn't move is the sum of j-p_i for all players p_i < j which appear between player j and the position of player j+1.

It is possible to implement a dynamic programming solution using this idea with complexity \mathcal O(n^2). With dynamic programming, we can determine the minimal overall moving costs and which players were moved. Now, we simply need the second part of the brute force solution to generate the actual moves performed.

Proof

Here is the proof of why the two ideas mentioned above are correct:

Let's look at the player p_\min with the smallest score, who has to end up at position n.

Claim 1: If p_\min is moved at all, it is optimal to move him directly to the end of the list.

Proof: Obviously, moving him towards the front will only increase the costs of other players to be moved. So assume he will be moved towards the end to a position i < n (thus saving n-i steps). Now there are two possibilities: either, the n-i players after him in the list have to be moved and their costs are increased by 1 (as opposed to that p_\min was moved to the end), or p_\min has to be moved again, which clearly is not optimal.

Claim 2: If p_\min is moved at all, we can do this in the first move.

Proof: Following from Claim 1, we already know the second part of the moving costs is fixed. So the only reason not to move p_\min first is that his current position decreases caused by moving other players. But these players have their moving costs increased by 1 because p_\min wasn't moved to the end.

If p_\min is moved, we have reduced our problem to the same problem with n-1 players. If p_\min is not moved, we have a similar problem with n-1 players with the additional restriction that all players after p_\min have to be moved before p_\min.

Let p'_\min be the player with the smallest score among the remaining n-1 players. We can see that it does not help to move p'_\min after p_\min, because that would mean we have to move him again, and we gain nothing from moving him past other players still to be moved (for each of them, we decreased the moving cost by 1, and increased the moving cost of p'_\min by at least one). If p'_\min is currently placed before p_\min in the list, by similar arguments as for Claim 1 we can argue that if p'_\min is moved at all, it is optimal to move him directly before p_\min. Also, Claim 2 still works. So we are left with the case that p'_\min is currently placed after p_\min and has to be moved towards the front. If there are players between p_\min and p'_\min, we could consider moving them first. If we move p'_\min first, the start positions of the players in between are increased by 1. But if we move some player in between first, the end position where p'_\min has to be moved to increases by 1, so it can't be bad if we move p'_\min first.

So, we can see that by using induction and the arguments presented above we can prove that each player is moved at most once, and the players can be moved in ascending order according to their score.


Comments

There are no comments at the moment.