Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
In the first subtask, the students and their friendships form a line.
One approach to this subtask involves dynamic programming. Let
be the minimum cost required for
the first
students to end up intending to write the CCC (ignoring any later students). Note that
,
and our answer will be
.
For each value of
from
to
, we'll consider transitions onwards from that state, with the subarray of
students from
to
(for each possible
such that
) ending up intending to write the CCC. If
at least one of those students has a
value of Y
, then it's possible to perform this transition by choosing a
Y
student and "expanding their influence" to all others, updating
accordingly.
For each
, we can consider all possible values of
while computing their transitions' minimum costs in a
total of
time, resulting in an overall time complexity of
.
To solve the remaining subtasks, we'll use a different dynamic programming formulation, this time on the
tree structure formed by the students and their friendships. We'll consider the tree to be rooted at an
arbitrary node (student), such as node
.
Let
(defined for
and
) be the minimum cost required for all students in
's
subtree to end up intending to write the CCC, such that:
- if
,
will be influenced by its parent
- if
,
will have no particular interaction with its parent
- if
,
will influence its parent
Our answer will then be
.
As is typical for DP on trees, we'll recurse through the tree, and for each node
, we'll compute
based on the DP values of
's children. Each value
must be computed carefully, with different logic
depending on the values of
and
.
An implementation of this algorithm may take
time (with some DP transitions taking
time
each to compute), but optimizations can be applied to reduce it to an overall time complexity of
and
have it earn full marks.
Comments