Author: Hanlin Ren
Tester: Jakub Safin
Editorialist: Jakub Safin
Determine if it’s possible to select 5 problems with required difficulties for a Cook-Off, given a list of N problems with known difficulties.
Straightforward - check the given conditions.
As the easiest problem in this contest, there isn’t much to be said about its solution.
Notice that there are no overlaps among the difficulties required for the 5 problems, so we can just independently check for each problem if at least one of the required difficulties for it appears among the input strings.
We don’t even need to remember all the input strings - it’s enough to remember how many times each of them appeared in the input. That makes checking the required conditions even easier.
Time complexity: O(N). Memory complexity: O(1).
Too easy? You can think about how this problem could be generalised. An arbitrary number of difficulties, arbitrary lists of allowed difficulties for each spot, upper or lower bounds on the total number of used problems of each difficulty, etc…