Editorial for COCI '16 Contest 6 #6 Gauss
Submitting an official solution before solving the problem yourself is a bannable offence.
First, let's notice that, in the optimal solution, Gauss will perform the operation of the second type (leaving the current number on the board) only for one number. Let's denote with the initial number, with
the final number, and with
the number we left on the board.
Secondly, let's notice that the number of operations between numbers and
and between
and
is at most
, because in each moment the new number is smaller than or equal to the half of the old number. It is not difficult to notice that the cost of the shortest way from
to
is equal to the cost of the shortest way from
to
(analogously for
and
).
Given the specificity of the formula to calculate the costs, we see that the cost of the shortest path to is equal for, for example, numbers
and
. More precisely, let
be exponents of the prime numbers in the factorization of a number into prime numbers. Then the cost of the shortest path from that number to
is equal to all such numbers that have the same multiset of exponents
. We can generate all such numbers and see that there are less than
of them. We assign to each number
the smallest number with which it shares a multiset, and denote it with
.
Let's summarize the results so far: The shortest path from to
is over a number
. The cost from
to
is equal to the cost from
to
, and that is equal to the price of
to
. Analogously for
to
and
.
Let's denote with the shortest path from
to
such that it holds
and
and the total length of paths from
to
and
to
is equal to
(not counting the moves from
to itself). This array can be calculated quickly enough at the beginning of the program with one optimization - we will calculate it only for pairs
and
such that
, because otherwise the pairs are not useful to us.
How do we reply to queries when we have this array? Let's go over all possible and look at the formula for the total number of moves
, and denote with
the number of moves when we leave
on the board: The total cost is
. Now we see that, for a fixed
, we need to find a pair
that minimizes the value of the upper expression, which is actually a standard problem where we need to calculate the lower hull of the lines, and for each
find the intersection of the vertical line
with the hull. We must also notice that all lines for a fixed
have the same slope, so it is sufficient to calculate the larger intersection of its lines with the
-axis and only add that one to the hull. The queries where
need to be processed separately using dynamic programming.
Comments