Task PAROVI

Let's denote the family of sets that have the partition located at index k as Ak, and the family of all possible initial sets as X.

Then the solution is all sets from ~X \setminus \bigcup_{i=1}^{n} A_i~

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

$$\displaystyle | X \setminus \bigcup_{i=1}^{n} A_i| = \sum (-1)^k \cdot |\bigcap_{j=1}^{k} A_{i[j]}|$$

In order to calculate the cardinality of the required intersection, we need to count how many pairings such that the partitions are located at certain k indices there are (we are not interested about partitions at other locations).

That number is equal to ~2^t~, where t is the total number of pairs that don’t “cross over” any partition location. The time complexity of this solution is ~O(2^N * N)~. For implementation details, consult the official solution).

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

Necessary skills: inclusion-exclusion principle, mathematics

Category: mathematics