Editorial for Mock CCC '19 Contest 2 J4 - Tudor Buys Some Cheesecake


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.

To solve the subtask, one can manually match each candle that Tudor has with one that is needed for the message. In the worst-case, looping over each character, it will take \mathcal O(|A|) time to determine if a matching is possible, for a runtime of \mathcal O(|A|\cdot|B|).

To solve the problem fully, note that ordering does not matter and all that matters is how many candles of each letter are needed. We start by enumerating how many candles of each letter that we need and then decrease the need for any given letter by one for each candle of that letter that we need. This runs in \mathcal O(|A| + |B|).


Comments

There are no comments at the moment.