Editorial for COCI '15 Contest 6 #4 Parovi

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.

Let's denote the family of sets that have the partition located at index $k$ $k$ as $A_k$ $A_{k}$ , and the family of all possible initial sets as $X$ $X$ .

Then the solution is all sets from $X \setminus \bigcup_{i=1}^N A_i$ $X ∖ ⋃_{i = 1}^{N} A_{i}$ .

The inclusion-exclusion principle provides us with an efficient way of calculating the size of the solution set. It holds:

$\displaystyle \left|X \setminus \bigcup_{i=1}^N A_i\right| = \sum_{S \subseteq \{1, 2, \dots, N\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|$ $| X ∖ ⋃_{i = 1}^{N} A_{i} | = \sum_{S \subseteq {1, 2, \dots, N}} (- 1)^{| S |} | ⋂_{i \in S} A_{i} |$

In order to calculate the cardinality of the required intersection, we need to count how many pairings such that the partitions are located at $S$ $S$ . We are not interested in partitions at other locations.

That number is equal to $2^t$ $2^{t}$ , where $t$ $t$ is the total number of pairs that don't "cross over" any partition location. The time complexity of this solution is $\mathcal O(2^N \times N)$ $O (2^{N} \times N)$ .

Please note: A solution using dynamic programming also exists and is left as an exercise to the reader.

Comments

There are no comments at the moment.