Module 1: String Algorithms

String Hashing Algorithms
Z-function
Prefix function. Knuth-Morris-Pratt algorithm
Manacher's Algorithm

Module 2: Graph Algorithms

Kuhn's algorithm — maximum matching in a bipartite graph
Kőnig's theorem

Module 3: Various DP ideas

DP on a DAG
DP subtree
Connected Component DP
Open and Close Interval Trick
DP on Subarrays
Submask DP
Digit DP

Module 4: Combinatorics

Inclusion-Exclusion (Advanced)

Module 5: Meet-in-the-middle

Meet in the Middle

Module 6: Fenwick Tree

Fenwick Tree

Module 7: Centroid Decomposition

Centroid Decomposition

Module 8: Virtual Trees

Virtual Tree / Auxiliary Tree

Module 9: Parallel Binary Search

Parallel binary search

Module 10: [BONUS]

Bitset Optimization
Hashing techniques

Inclusion-Exclusion (Advanced) - Preparation to IOI Part 5

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 5/Module 4: Combinatorics/Inclusion-Exclusion (Advanced)

Inclusion-Exclusion (Advanced)

Inclusion-Exclusion (Advanced)

Main idea: reduce by grouping subsets by size

A lot of hard IE problems look impossible because there are $2^m$ subsets.

The trick is:

first write IE on subsets
then prove the intersection count depends only on $|S|$ , not on the exact subset

If

f(S) = g(|S|)

then

\sum_{S \subseteq [m]} (-1)^{|S|} f(S) = \sum_{t=0}^{m} (-1)^t \binom{m}{t} g(t)

S \subseteq [m] \sum (- 1)^{∣ S ∣} f (S) = t = 0 \sum m (- 1)^{t} (t m) g (t)

This is the most important simplification trick.

Checklist for simplifying hard IE

When you get a scary formula, ask:

What are the bad events $A_i$ ?
What is the intersection $\bigcap_{i \in S} A_i$ ?
Does its size depend on:
- exact subset $S$ , or
- only the number of chosen constraints $|S|$ ?
If only on $|S|$ , collapse to a single sum over $t$ .

Example 1

Problem

Count strings of length $n$ over $m$ symbols such that every symbol appears at least once.

IE setup

Let $\bigcap_{i \in S} A_i$ = “symbol $i$ is missing”.

Then:

\text{ans} = \sum_{S \subseteq [m]} (-1)^{|S|} \cdot (m-|S|)^n

Simplification

The intersection only depends on how many symbols are forbidden:

if $|S| = t$ , then we have $(m-t)^n$ strings

So group by size:

\text{ans} = \sum_{t=0}^{m} (-1)^t \binom{m}{t}(m-t)^n

Why this is easy now

No subset loop anymore — just one loop over $t$ .

Example 2

Problem

Count permutations of $1 \ldots n$ with no fixed points.

IE setup

Let $A_i$ = “position $i$ is fixed”.

Then:

!n = \sum_{S \subseteq [n]} (-1)^{|S|}(n-|S|)!

Simplification

If $|S| = t$ , fixing those $t$ positions leaves $(n-t)!$ permutations.

So:

!n = \sum_{t=0}^{n} (-1)^t \binom{n}{t}(n-t)!

Again, scary subset IE becomes a single sum.

Example 3

Problem

Count solutions of

x_1 + x_2 + \cdots + x_n = S,\quad 0 \le x_i \le B

IE setup

Let $A_i$ = “ $x_i \ge B+1$ ”.

For a chosen set $S$ of violated variables, substitute:

x_i' = x_i - (B+1) \quad (i \in S)

Then total sum decreases by $|S|(B+1)$ .

Number of nonnegative solutions becomes:

\binom{S - |S|(B+1) + n - 1}{n - 1}

Simplification

Depends only on $|S|=t$ , so:

\text{ans} = \sum_{t=0}^{n} (-1)^t \binom{n}{t} \binom{S - t(B+1) + n - 1}{n - 1}

(Invalid terms are $0$ .)

Example 4

Problem

Count numbers in $[1,N]$ divisible by at least one value from $\{p_1,\dots,p_m\}$ .

IE setup

Let $A_i$ = “number is divisible by $p_i$ ”.

Then:

\left|\bigcap_{i \in S} A_i\right| = \left\lfloor \frac{N}{\mathrm{lcm}(p_i : i \in S)} \right\rfloor

If $p_i$ are distinct primes, lcm is just product.

Not every IE needs to be “collapsed”. Sometimes the optimization is proving that $m$ is small.