Editorial for WC '16 Contest 1 S2 - Alucard's Quest

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.

Alucard actually has very little choice. In order to reach each chamber that contains an item, Alucard must necessarily pass through all of the passageways between that chamber and the $1^\text{st}$ ~1^\text{st}~ chamber at some point. Furthermore, he never has a reason to pass through any of the remaining passageways (those which are not between the $1^\text{st}$ ~1^\text{st}~ chamber and any chamber containing an item). Therefore, it's clear exactly which set of chambers and passageways Alucard should pass through at least once, regardless of the order in which he collects the $K$ ~K~ items.

For a given chamber $i$ ~i~, let's try to determine if Alucard will have to visit it. Let $A(i)$ ~A(i)~ be $\text{true}$ ~\text{true}~ if he will, and $\text{false}$ ~\text{false}~ otherwise. If chamber $i$ ~i~ contains an item itself, then certainly $A(i) = \text{true}$ ~A(i) = \text{true}~. Otherwise, if we model the castle as a tree rooted at the $1^\text{st}$ ~1^\text{st}~ chamber, then $A(i) = \text{true}$ ~A(i) = \text{true}~ if and only if $A(c) = \text{true}$ ~A(c) = \text{true}~ for at least one child $c$ ~c~ of chamber $i$ ~i~. This is because, in order to reach chamber $c$ ~c~, Alucard will have to pass through chamber $i$ ~i~.

How does this translate into the amount of magic power required in total?

For each chamber $i$ ~i~ such that $i > 1$ ~i > 1~ and $A(i) = \text{true}$ ~A(i) = \text{true}~, Alucard will need to use the passageway between $i$ ~i~ and its parent at some point. Therefore, assuming we can compute the $A$ ~A~ values, we can add up then add up the monster counts in these passageways connecting chambers which must be visited to yield the answer.

What remains is computing the $A$ ~A~ values. $A(i)$ ~A(i)~ is computed based on chamber $i$ ~i~ and the $A$ ~A~ values of $i$ ~i~'s children, meaning we can recursively compute it starting from the $1^\text{st}$ ~1^\text{st}~ chamber. For convenience, we can pass in the index of $i$ ~i~'s parent in the recursive call so that we can determine which of its neighbours are its children when iterating over them.

We can also tally up the total answer during this process, rather than iterating over all nodes with true $A$ ~A~ values afterwards.

Since each of the $N$ ~N~ chambers is visited only once in the recursion, the algorithm has a time complexity of $\mathcal O(N)$ ~\mathcal O(N)~.

Comments

There are no comments at the moment.