How do I permute a list of integers so that as many possible integers will move to a place where a smaller integer used to stand?

Question

I'm trying to understand the solution to an algorithm/logic problem. The problem statement is as follows:

You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers. For instance, if we are given an array [10,20,30,40], we can permute it so that it becomes [20,40,10,30]. Then on the first and the second positions the integers became larger (20>10, 40>20) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals 2. Help Vasya to permute integers in such a way that the number of positions in a new array, where integers are greater than in the original one, is maximal.

Input The first line contains a single integer (1≤≤105) — the length of the array. The second line contains integers 1,2,…, (1≤≤109) — the elements of the array.

Output Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.

Sample I/O: example input/output

I've looked at the solution but couldn't really understand the intuition behind it. I understand how it works, but I don't understand WHY it works. Here's the solution:

The answer is minus maximal number of equal elements. Let the maximal number of equals be . Let's prove that − is reachable. It's clear that for every permutation of the array the answer will be the same, so let's sort the array in non-decreasing order. Now we should just make a left shift on . After it, the − right elements will move to a position of a smaller element. Now let's prove that the answer is no more than −. Let's consider some permutation. It's known that every permutation breaks into cycles. Let's look at two occurrences of the same number in the same cycle. Then there is at least one number between them which will move on a position of a non-smaller element. Even if it the same occurrence and even if the length of the cycle is 1, we can say that for every occurrence of this number there is at least one number that moves on a position of a non-smaller one. So if some number occurs times, there are at least bad positions and therefore no more than − good positions.

Please break this explanation down to a level I can understand. I've tried tons of dry-runs but couldn't figure out the logic behind it. To me, this is black magic.

Answer 1

Let's start by simplifying a bit. Notice that the initial order of the numbers do not matter, so we can reorder them as we please.

Then, you need to both prove that there is a permutation such that the elements in n-x positions become greater after the action of the permutation, and that there is no permutation doing that for more than n-x positions.

To prove the first one, let's write the numbers you get in a column in order, but with all duplicates of the same number in the same line. For example, if the numbers are [1,1,1,2,3,4,4], you'd write:

1,1,1

2,

3,

4,4,

Then, the permutation obtained by sending each number to the number below's position (looping around as necessary) does the job. In the example's case, It'd give [2,4,1,3,4,1,1]

Now you need to show that there is no better solution. To do that, let's pick any permutation. Then for the x identical numbers, look at their successive images through the permutation until the antecedent is larger or equal than its image. Since the initial numbers are equal, it is impossible that one of them is part of another's sequence of images. Therefore, for each initial number, there is exactly one number whose image is smaller or equal to itself. In other words, it's impossible to do better than our solution.

In conclusion, we have shown that the maximum number of positions whose value can be increased with a permutation is n-x, with n being the total number of elements, and x being the maximum number of identical numbers.

Feel free to ask any questions you may have.