← All solutions

Shortest judge solution: 1206 bytes. Shortest team solution (during contest): 1054 bytes.

This problem asks for the cost of a Huffman coding of the 4ⁿ strings of length n over the alphabet {S, C, R, F}, where the probability of a string with f_S S’s, f_C C’s, f_R R’s, and f_F F’s is p_sunny^f_S · p_cloudy^f_C · p_rainy^f_R · p_frogs^f_F. Unfortunately, 4ⁿ is so large that we can not simulate the Huffman coding procedure naively. However, due to the product structure of the distribution, there will be many nodes in the Huffman coding having the same probability, so we can group these together and just keep their count.

Initially, there are n(f_S, f_C, f_R, f_F) = n!/(f_S! f_C! f_R! f_F!) nodes with the probability p_sunny^f_S · p_cloudy^f_C · p_rainy^f_R · p_frogs^f_F (for each combination of non-negative values f_S, f_C, f_R, f_F summing up to n). Now we proceed with Huffman encoding: pick the smallest probability node, say this probability is p. If there are K nodes with this probability, they give rise to ⌊K/2⌋ nodes of probability 2p, and if K is odd then one remaining node of probability p gets matched with one of the nodes with the second smallest probability value.