Author: Chandan Boruah
Tester: Pushkar Mishra
Editorialist: Florin Chirica
Let’s define a ranklist as a sequence of numbers between 1 and x of length n, such as ALL numbers between 1 and x must appear in the sequence at least once. An operation can change one element in what value you want. Your goal is to create a sequence containing all numbers between 1 and n exactly once by using minimal number of operations.
Let’s iterate a number x meaning that all numbers between 1 and x appear in the ranklist. The cost of any ranklist with values between 1 and x is n - x. We need to determine if numbers between 1 and x are enough to create a sum s. Let’s note that a ranklist defined by x can create all sums between minSum and maxSum, where minSum = x * (x + 1) / 2 + (n - x) and maxSum = x * (x + 1) / 2 + (n - x) * x.
To solve this problem, we need to make two observations. They seem pretty easy and intuitive, but after we make them, the problem is solved.
A ranklist containing elements between 1 and x (no element greater than x) will need n - x operations to be transformed into a sequence of numbers between 1 and n, no matter how sequence looks like.
We already have all elements between 1 and x (from the definition of a ranklist). However, we need to also have elements x + 1, x + 2, …, n - 1, n. Those do not appear (since all are greater than x), so we have to make some operations to get them. We can keep exactly one position which contains a value i, for each i between 1 and x. Rest of n - x positions must be modified. We’ll put in the remaining n - x positions values x + 1, x + 2, …, n - 1 and n. So cost of a ranklist containing elements between 1 and x becomes n - x.
A ranklist containing elements between 1 and x (no element greater than x) can generate all sums s, such as minSum <= s <= maxSum. More, all sums that can be generated by this ranklist are the ones that are between minSum and maxSum.
Let’s find out who is minSum. We are forced to place x elements: 1 2 … x. The rest of them we can complete them with 1s. So minSum = (1 + 2 + … + x) + (n - x) = x * (x + 1) / 2 + (n - x). maxSum can be obtained by completing the first x elements 1 2 … x and the rest of them with x value (the maximum we’re allowed to use). So we get maxSum = (1 + 2 + … + x) + (n - x) * x = x * (x + 1) / 2 + (n - x) * x.
Obviously, no sum s can be less than minSum or greater than maxSum (because those values are the minimum/maximum one can get). Let’s proof now that each sum s which has minSum <= s <= maxSum can be obtained. The idea is to see how those n - x terms can vary: they can be from 1 1 1 … 1 1 1 to x x x … x x x. Suppose we obtained a configuration corresponding to a sum s. Unless s is equal to maxSum, we can always obtain s + 1 as well. If s equal to maxSum, then all terms are equal to x. Otherwise, at least one term isn’t x. Since it isn’t x, we can increment it. Now, the obtained sum is s + 1 and it’s obtained assuming that s is different from maxSum.
Putting the observations together
In fact, those 2 observations are enough to solve the problem. The key that puts them together is that we can iterate x from 1 to n. Let’s see for a fixed x if a sum s can be obtained. For the given x, we can calculate minSum and maxSum and if minSum <= x <= maxSum, then sum s can be obtained and a ranklist containing only values between 1 and x is valid. The cost to transform this ranklist into 1 2 … n is n - x. So, for all valid ranklists (those who can give sum s), we keep minimum of n - x and we’re done.
Since we iterate the x variable from 1 to n, the complexity is O(n).