## Editorial for UACC 1 P5 - A Lab Report

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.

Author: Josh

For the sequence to become an arithmetic sequence, we need the differences between adjacent elements to be equal. This motivates us to consider the difference array , where for . We can now ignore array . There are three possible types of operations:

1. The entire array is shifted. Then, is unaffected.
2. Either the first or the last element of the array is part of the shifted array, but not both. Then, exactly one element of increases or decreases by .
3. Neither the first nor the last element of the array is part of the shifted array. Then, exactly one element of is increased by , and exactly one element of is decreased by .

Suppose that we want all elements of to be equal to , and let be the number of operations needed for this to occur. It would be useful to find a formula for . A natural step is to separately consider the elements of greater than , and the elements of less than . Let be the sum of for all , and let be the sum of for all . We can think of and as the number of decrements and increments needed, respectively, in order for all elements of to be equal to . Note that:

• A lower bound of is . This is because each operation can decrease by at most , and decrease by at most .
• An upper bound of is . This is because we can repeatedly pair one increment with one decrement using a type operation. If we run out of increments or decrements, we can use type operations instead.

It follows that .

Now, we should try to find the optimal value of . Observe that as increases, decreases while increases. This means that is minimised when and are approximately equal. It's possible to compute immediately using a binary search, but there is a more direct formula. Let be the number of elements of greater than or equal to , and let be the number of elements of smaller than , so that . In order for and to be equal, we would require:

This means that the optimal value of is the mean of . This should make sense intuitively as well, considering the mean as some kind of equilibrium value. (Indeed, it is directly analagous to clockwise torque being equal to anticlockwise torque around the centre of mass.) If the mean is not an integer, we should try both rounding the mean down as well as up. Computing the value of using our formula yields the correct answer. Be careful of the special case where as the mean of an empty sequence is undefined.

Time complexity: or