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$ ~C~ is the maximum strength of a Herobrine created from the ores in node $C$ ~C~'s subtree. For this subtask, it suffices to solve the problem individually for each value of $C$ ~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$ ~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$ ~X~ as $i$ ~i~, then $f_i$ ~f_i~ Herobrines can be created using the first crafting recipe. It follows that the answer is $\max(f_i * i)$ ~\max(f_i * i)~.

Time Complexity: $\mathcal{O}(N (\sum M) \log (\sum M))$ ~\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$ ~C~ from $N$ ~N~ down to $1$ ~1~, provided that we can add ores to current multiset and maintain the answer.

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

Time Complexity: $\mathcal{O}(N + \sum M)$ ~\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)$ ~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$ ~freq~ and $g$ ~g~. When performing a DFS search of a subtree, the heaviest child should be searched last. Before the heaviest child is searched, $freq$ ~freq~ and $g$ ~g~ should be reset, so that after the heaviest child is searched, $freq$ ~freq~ and $g$ ~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)$ ~\mathcal{O}(N + (\sum M) \log N)~ or $\mathcal{O}(N + (\sum M) \log (\sum M))$

Comments

There are no comments at the moment.