Editorial for DMOPC '14 Contest 3 P5 - Not Enough Servers!

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: FatalEagle

Notice that people will only AC submissions don't matter (unless all of them have all AC). Therefore, we will consider for each test case the set of people it will fail (there are M test cases).

We can use dynamic programming over all 2^N subsets of people. Each state is the minimum number of test cases required to fail that subset of people. We will iterate through the states in increasing size of their subset, and we will break ties by processing the states with the least cost first. For each state, we can try adding each test case and computing the new state, and seeing if the cost of the current state + 1 is better than the cost of the new state. You should use bitmasks to guarantee a good complexity.

A well-implemented backtracker can also get most if not all of the points. You just had to believe!

Time Complexity: \mathcal{O}((M + N) \cdot 2^N)


There are no comments at the moment.