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

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~, $N-1$ ~N-1~, or $N-2$ ~N-2~.

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

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

If not, however, we must remove one resolution from each pair, leading to $N-2$ ~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)$ ~\mathcal{O}(M2^N)~ time.

A subtask was given for suboptimal or factorial time solutions.

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

Comments

There are no comments at the moment.