Editorial for COCI '19 Contest 6 #3 Konstrukcija
Submitting an official solution before solving the problem yourself is a bannable offence.
We are asked to construct a graph with nodes and
edges such that
, where
. Let
be a set of nodes
such that there is a path from
to
, there is a path from
to
and
is different from
. We can remove the last element of each ordered array
and obtain another ordered array
that begins with
, ends in some node from
and whose length is smaller by one than the length of
, so
. Therefore
.
We will build our graph level-by-level. The first level will always contain a single node and the last level will contain a single node
. In the first two subtasks, all nodes (except
) in a certain level will have directed edges towards all nodes in the next level. The general solution will be slightly modified.
The graph which solves the first subtask has three levels. The first level contains node
, the second level contains
nodes, and the last level contains node
. For example, for
the graph looks like the one depicted below.
In this example, using the recurrence relation for , we can see that
,
,
.
We will solve the second subtask with in a similar manner. For example, for
the graph looks like the one depicted below.
By inspecting the solutions for the first two subtasks we can observe that, by adding nodes in a new level, we are multiplying the sum of all
values by
. It is also clear from the recurrence relation that
is equal to the sum of all
values, where
, multiplied by
. If
has the form
, by adding three nodes in a new level, the sum of
is multiplied by
so we can obtain the value
up to its sign using
nodes. If we get the wrong sign, we can simply add
nodes in the next level to multiply the solution by
.
All that is now left to determine is how to increase the absolute value of the current value by . Then we can use multiplications by
and additions by
to perform a popular algorithm for transposing the number from binary to its decimal notation. If the current sum is negative, we can simply subtract
by adding a new node to the current level that is connected with node
. Similarly, if the sum is positive, we can add two nodes to a new level that are connected to all from the previous level, thereby negating the sum and subtracting
as described.
This algorithm constructs a graph for given in less than
edges.
Comments