Inclusion-Exclusion Principle

Resources

Introduction

The inclusion-exclusion principle relates to finding the size of the union of some sets.

Verbally it can be stated as following:

The mathematical identity of the above is:

Written in a compact form:

Mobius Function

The Mobius function is a multiplicative function that comes in handy when dealing with inclusion-exclusion technique and divisors-related problems. It has values in $\{-1, 0, 1\}$ depending on number's factorization.

Below you can see the first $19$ values of $\mu(n)$:

Let's take a look at how the mobius function can be precomputed with a slightly modified sieve.

Copy
mobius[1] = -1;
for (int i = 1; i < VALMAX; i++) {
	if (mobius[i]) {
		mobius[i] = -mobius[i];
		for (int j = 2 * i; j < VALMAX; j += i) { mobius[j] += mobius[i]; }
	}
}

Applications

SQFREE

Explanation

A perfect application for inclusion-exclusion principle and mobius function. In this particular case the set $A_i$ - previously mentioned in the tutorial section - denotes how many numbers are divisible with $i^2$ and we're asked to find out $\bigg| \bigcup_{i=1}^{\sqrt{n}} A_i \bigg|$. The precomputed mobius array tells whether to add or subtract $A_i$.

Implementation

Time Complexity: $\mathcal{O}(V \log V + T \cdot \sqrt{n})$, where $V = 1e7$

Copy
#include <iostream>
#include <vector>

using namespace std;

const int VALMAX = 1e7;

int mobius[VALMAX];

int main() {

Cowpatibility

Explanation

In this particular case the set $A_i$ - previously mentioned in the tutorial section - denotes how many pairs of cows have at least $i$ ice cream flavors in common. From the total number of pairs subtract the union of $A_i$. The global answer is:

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	ifstream in("cowpatibility.in");
	int n;
	in >> n;

	map<vector<int>, int> subsets;
	for (int i = 1; i <= n; i++) {

Copy
from collections import defaultdict

with open("cowpatibility.in", "r") as read:
	n = int(read.readline().strip())
	subsets = defaultdict(int)

	for _ in range(n):
		flavors = list(map(int, read.readline().strip().split()))
		flavors.sort()

The number of strings that match a certain pattern

Explanation 1

A dynamic programming approach with bitmasking would look like this:

$dp[i][mask] = \text{the number of strings of length i that match all the patterns in set, but none other patterns. }$ The recurrence is:

The following code illustrates this:

Implementation

Time Complexity: $\mathcal{O}(M \cdot N \cdot 2^N)$, where $M$ is size of each strings in patterns and $N$ is the size of patterns.

Copy
const int MOD = 1000003;

int howMany(vector<string> patterns, int k) {
	int n = patterns.size();
	int m = patterns[0].size();
	vector<vector<int>> dp(50, vector<int>(1 << n));
	for (int i = 0; i < m; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			int mask = 0;
			for (int j = 0; j < n; j++) {

Explanation 2

The problem can also be solved using the inclusion exclusion principle.

An important observation is that we can easily count the strings that satisfy some specific patterns. Simply iterate through the positions of all patterns. If all the patterns contain $?$ then we can use any letter from $a$ to $z$ giving us $26$ solution, otherwise we can only put the fixed letter contained by a pattern. The answer is the product.

Iterate over subsets - denoted by $A$ - of patterns consisting of exactly $k$ strings. For this specific subset count the number of string that can only match all the patterns in subset $A$. Apply the inclusion-exclusion principle over all supersets $B$ such that $A \subset B$.

$f(B)$ denotes the number of strings matching at least set $B$

The global answer is:

Implementation

Time Complexity: $\mathcal{O}(\binom{N}{k} \cdot 2^{N - k} \cdot M \cdot N)$

Copy
const int MOD = 1000003;

int howMany(vector<string> patterns, int k) {
	int n = patterns.size();
	int m = patterns[0].size();
	int ans = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		// subsets with exactly k patterns matters
		if (__builtin_popcount(mask) != k) { continue; }
		// iterate over all superset of current subset mask