Editorial for Mock CCC '22 Contest 1 J5 - New Year's Restrictions

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.

For the first subtask, note that the answer is always N, N-1, or N-2.

With M = 0 or M = 1 being trivial, let's take a look at when M = 2.

If the two pairs form a "chain" such as (r_i, r_j) and (r_j, r_k), we can remove r_j leading to N-1 resolutions being kept.

If not, however, we must remove one resolution from each pair, leading to N-2 resolutions being kept.

The full solution involves generating all subsets of the resolutions, and checking each restriction to determine if the subset is valid. This can be done in \mathcal{O}(M2^N) time.

A subtask was given for suboptimal or factorial time solutions.

Time Complexity: \mathcal{O}(M2^N)


There are no comments at the moment.