Editorial for 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.

Author: leo

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


Comments

There are no comments at the moment.