Editorial for Mock CCC '20 Contest 2 S4 - Rotational Arrays
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
The first subtask was to reward brute force solutions.
Time Complexity: or similar.
Subtask 2
It can be proven that a rotational array of length
has some subarray
that repeats over the entirety of
. In addition, the length of this segment will be divisible by
, or a factor of
. Thus,
. The proof for these is left as an exercise for the reader.
If we check for all ,
has only so many factors. The maximum number of factors
has is
for
. Thus, we can simply brute force, as
will pass!
We can loop from to
, and for all numbers
that are a factor of
, assume that
. We then must make
for all
. Since
for this subtask, we can try both: How many modifications are required to modify everything to
? How many are required to modify everything to
? Take the minimum of these.
Time Complexity: , where
is the number of factors of
.
Subtask 3
Building onto subtask 2, we can see that the restriction on has been removed. In addition, going through all
is way too slow.
Let us remodel the problem of making for all
. We can imagine placing points on a number line, where
is placed at the point
. The problem now reduces to moving these points to a common integer location, where the distance they travel is their cost. It can be shown that the lowest cost consists of moving all the points to the median of the set of points (see Geometric Median). This can be done in
time, multiplied by
for doing this for all
times.
Time Complexity: , where
is the number of factors of
.
Comments