Editorial for Yet Another Contest 8 P3 - Herobrine

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.

Author: Josh

The answer for a given value of is the maximum strength of a Herobrine created from the ores in node 's subtree. For this subtask, it suffices to solve the problem individually for each value of , so let's consider a given multiset of ores and determine the maximum strength of a Herobrine created from it.

We only care about the frequency of each ore, so let be the list of non-zero frequencies sorted in non-increasing order. If we fix the size of as , then Herobrines can be created using the first crafting recipe. It follows that the answer is .

Time Complexity:

In this subtask, the tree is a line. This means we can solve for each from down to , provided that we can add ores to current multiset and maintain the answer.

Let be the frequency of ore , and be the number of satisfying . It is easy to see that the answer can also be expressed as . Now, consider what happens when ore is added to the multiset. is first incremented, then is incremented, and the answer is the maximum of the previous answer and . This allows us to maintain the answer in time whenever an ore is inserted.

Time Complexity: