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

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

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 test cases).

We can use dynamic programming over all 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:

## Comments