Editorial for COCI '22 Contest 1 #3 Berilij
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's define graph with vertices representing spaceships and edges representing the condition of two spaceships touching externally. Additionally, let the weight of an edge be the distance between the circles it connects. Now the task is equivalent to finding non-negative values for the vertices such that for each edge the sum of values of both vertices it connects is equal to the weight of that edge, for which the sum of squares of values of vertices is the least possible. If the vertices
are connected with the edge of weight
then for the values of vertices the conditions
,
, and
hold.
In the first subtask, graph is an odd cycle. Let's assume that, for now, the value of the first vertex is
. Since we can calculate the values
for each edge, we can uniquely determine the value of the second vertex in a cycle. Now that we know the value of the second vertex we can uniquely determine the value of the third, and so on until we circle back to the first vertex with the condition that its value should be
. Let's now attempt to increase the value of the first vertex by
. To keep the conditions satisfied we now need to decrease the value of the second vertex, and after that increase the value of the third vertex, and so on until we circle back to the first vertex with the new condition that its value must be
. Since
we can determine
uniquely as
. Now we only need to check if substituting
as the value of the first vertex yields non-negative values for all other vertices.
In the third subtask, the graph is a forest, but it is enough to solve it for each tree separately. Let's pick any vertex as a root and denote its value as . To satisfy the conditions of the task we can now uniquely determine the value of each vertex
as a linear polynomial
, where
is a constant with value equal to the alternating sum of weights of edges from vertex
to the root. Since every value must be non-negative, vertices with values of
set a lower bound for
, while vertices with values of
set an upper bound for
. If upper bound is less than lower bound there are no solutions. To determine the
for which the sum of squares of values of vertices is the least possible let's sum the squares of linear polynomials for each vertex. The result is a quadratic polynomial
. Notice that
is equal to the size of the tree so the quadratic polynomial has a minimum at
. Since
is not used in this expression and
is equal to the sum of
for each vertex where
is the sign in front of
in polynomial
, we can calculate
without squaring any numbers. If
is between lower and upper bound,
is our solution, else for
we take the value of lower or upper bound whichever is closer to
.
For full solution, let's solve the task for each component on any spanning tree as in the solution for subtask three. Now we only need to analyse cycles. Let's note that in the solution of the third subtask, the polynomial for each vertex on even depth from the root is , while for every vertex with odd depth it's
. Since even cycles connect vertices of different depth parity, they only add conditions of the form
, in other words
.
and
are constants so it is easy to check if this condition is met. Odd cycles connect vertices of same depth parity and add conditions of forms
, in other words
which gives us only one solution for
as in subtask one.
The time complexity of the described algorithm is . Alternatively, the task could be solved with better implementations of ternary search with complexity
, where
is maximal absolute value of coordinates
and
is the required precision.
Comments