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

user_15306169 0
Viewed 84

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 explain to me why this solution works. I've tried tons of dry-runs but couldn't figure out the logic behind it. To me, this is black magic.

arrays algorithm python
1 Answers

Perhaps a visual example could help:

If your array is already sorted you will get something like this:

 [1, 2, 3, 4, 5]

If you shift it to the right by one position, every number except the last one will be replaced by a larger number. So n-1 is the maximum number of replacements you can do because the largest number cannot be replaced by a smaller one.

 [1, 2, 3, 4, 5]
     |  |  |  |     
    [1, 2, 3, 4, 5]

If the array is not sorted, the replacements occur at different positions but there is the same number of pairs.

If you have a number that repeats, there will be one less larger/smaller replacement. So we end up with n-2 such replacements (where 2 is the maximum repetition)

 [1, 2, 3, 3, 4, 5]
     |  |     |  |   
    [1, 2, 3, 3, 4, 5]

This can be explained by the fact that, to implement the nth replacement, you have to be able to perform the (n-1)th replacement, each of which requires a smaller value. So you'll need a value that has 1 smaller, a value that has 2 smaller, ... a value that has n-1 smaller values. Each repeated value breaks this sequence so a list of 7 elements with a value that has 2 duplicates (i.e. the same value 3 times) is like a list of 5 elements and can have 4 replacements (7-3).

However, if you have two different elements that repeat, you only face the worst case of the two because you can perform replacement again between the extra elements:

[1, 2, 3, 3, 4, 5, 5, 5, 6]
    |  |     |  |        |                  5 replacements
   [1, 2, 3, 3, 4, 5, 5, 5, 6] 

         [3, 5, 5]
             |                              1 replacements
            [3, 5, 5]
 
     For 9 elements with 3 max repeated =   6 replacements

     9-3 = 6 = N - maxRepeat
user_52375600
Related