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:
- The entire array is shifted. Then,
is unaffected.
- 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
.
- 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 
Comments