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

Subtask 1

The answer for a given value of C is the maximum strength of a Herobrine created from the ores in node C's subtree. For this subtask, it suffices to solve the problem individually for each value of C, 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 f_1, f_2, \dots, f_k be the list of non-zero frequencies sorted in non-increasing order. If we fix the size of X as i, then f_i Herobrines can be created using the first crafting recipe. It follows that the answer is \max(f_i * i).

Time Complexity: \mathcal{O}(N (\sum M) \log (\sum M))

Subtask 2

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

Let freq_i be the frequency of ore i, and g_i be the number of freq_j satisfying freq_j \ge i. It is easy to see that the answer can also be expressed as \max(g_i * i). Now, consider what happens when ore o is added to the multiset. freq_o is first incremented, then g_{freq_o} is incremented, and the answer is the maximum of the previous answer and g_{freq_o} \times freq_o. This allows us to maintain the answer in O(1) time whenever an ore is inserted.

Time Complexity: \mathcal{O}(N + \sum M)

Subtask 3

Apply the small-to-large merging optimisation on the tree combined with the technique from subtask 2. Note that we can compare either subtree sizes or the total number of ores in each subtree; either works.

It's worth noting that it is possible to implement a solution in O(N) memory, without any maps, yielding a much better constant factor. This relies on the fact that the same time complexity can be reached if the ores in the current node are always swapped only with the ores in the subtree of the heaviest child. Keep global arrays for freq and g. When performing a DFS search of a subtree, the heaviest child should be searched last. Before the heaviest child is searched, freq and g should be reset, so that after the heaviest child is searched, freq and g contain the ores in the heaviest child's subtree, as desired. The remaining ores in the subtree can now be added one by one.

Time Complexity: \mathcal{O}(N + (\sum M) \log N) or \mathcal{O}(N + (\sum M) \log (\sum M))


There are no comments at the moment.