Editorial for COCI '19 Contest 1 #3 Džumbus
Submitting an official solution before solving the problem yourself is a bannable offence.
In the first and second subtasks, we can observe that the pairs of friends form a single chain. We will solve the first subtask using dynamic programming which in its state has a position in the chain , the amount of džumbus we have at our disposal
and a binary flag
which denotes whether person at position
exchanged any solutions. The value
reflects on only the first
people in the chain and it will denote the largest number of people that can exchange solutions with optimal distribution of leftover drink when it is also known (via
) whether person at position
has already done so. The general idea behind the transition is the following:
The answer to query equals to
. The time complexity of this solution is
.
Since there is no additional constraint on value in the second subtask, the dp solution from the first subtask would not fit the time and memory constraints. Luckily, we can think about the same thing in a different light. We will again store the position
in our state and a binary flag
which have the same meaning as before. But now, the amount of džumbus will be the value of our dp and the number of people that have exchanged the solutions will be moved to the state. The transitions are left as an exercise to the reader.
The answer to the query is the largest
such that
. The complexity of this solution is
.
In the third subtask we don't have a chain, but a forest. A forest can be reduced to a single tree by introducing a dummy root node which we treat as a person with infinite . In that way, we are sure that person does not affect the results.
We use a similar dynamic programming solution as in the second subtask, except we do it on a rooted tree. The value of is the smallest amount of džumbus we need to make
people that are in
's subtree to exchange solutions when it is also known whether
exchanged the solutions (bit
). When calculating the dp values for subtree
, we assume we already have all the dp values calculated for the entire subtree. We will also have an auxiliary
which in its state holds the number of people in a subtree of
which have exchanged solutions at least once, as well as number
which denotes that we have taken into consideration the first
children of
thus far. Then, it is obvious that
. Let
denote the
child of node
. The transitions are therefore:
(Implementation details and corner cases should be carefully analyzed by the reader)
When we add up all the states across all of the nodes, we get a total of states in the
and every transition is calculated in at most
steps. Therefore, the complexity can be bounded by
.
I know what you're thinking. There is no way this can be optimized any further.
To solve the fourth and final subtask you should note that, with careful implementation, the complexity of our solutions is in fact . Obviously, it is impossible that a set of people exchanges more solutions than the size of that set. Therefore, when calculating
, it is not necessary to check all options for
and
, just those which are possible (
cannot be larger than the sum of subtree sizes for already processed children increased by
and
cannot be larger than the subtree size of the current child). We will prove that the total complexity of dp calculations for each subtree is at most
. The proof inducts on the tree depth. The claim obviously holds for leaves. Let's fix a node and suppose we have calculated dp values for its children with the mentioned complexity. Suppose that node has
children with subtree sizes
. The total complexity for calculating dp values of that node and its subtree can be expressed as:
The total time complexity of the whole solution is therefore .
Comments