Problem Link:
author: Tasnim Imran Sunny
tester: Roman Rubanenko
editorialist: Utkarsh Lath
Difficulty:
Hard
Pre-requisites:
inclusion-exclusion, dynamic-programming, combinatorics, bipartite-graphs
Problem:
Given 3 * N matrix, whose first two rows are filled with permutations of [1…N], and third row is empty, find the number of ways of filling the third row such that each number(between 1 to N) appears at most once in each row and each column. The part of matrix already filled satisfies this property.
Explanation:
The current problem can be translated to finding the number of perfect matchings in a given (N-2)-regular N*N bipartite graph.
The vertices on left hand side of bipartite-graph represent positions in the third row. The vertices on the right hand side represent colors that can be filled into some position. The edges are assignments compatible with the first two rows (i.e. if first row is array A[i] and second row is array B[i], then there is an edge from i to all colors except A[i] and B[i]).
Coloring the third row of our matrix is equivalent to choosing exactly one edge(from the above graph G) incident to each position. The manner in which we have put edges ensure that C[i] ∉ {A[i], B[i]}. To make sure that C[i] ≠ C[j], the edges chosen should form a perfect matching.
Therefore, we need to find number of perfect matchings in a given (N-2)-regular bipartite graph G.
Let me define another related graph G’ which has same set of vertices as G, and all left to right edges that are not in G (i.e. vertex i on LHS has edge to vertices A[i] and B[i] on RHS).
The first step towards solution is realizing that the graph G’ has very simple structure. Every vertex has degree 2, so it is a union of disjoint cycles. If suppose we were asked to count number of matchings in G’, it would be far simpler. Given the size of all cycles of G’, the number of k-matchings can be found with a simple DP(details given later). Let ϕ(k, G’) denote number of k-matchings in G’.
Let F(k) = The number of perfect matchings in G U G’ such that exactly k edges belong to G’ and N-k edges belong to G.
Any such matching consists of a k-matching in G’. So, can we use the value of ϕ(k, G’) ?
The only problem in using ϕ(k, G’) is that we dont know the number of ways to match the remaining vertices only using edges from G. To overcome this, we will consider all matchings of the remaining vertices in G U G’ (which is (N-k)! in number), and then remove those where more than k edges are used from G’.
F(k) = ϕ(k, G’) * (N-k)! - F(k+1) * (k+1 choose k) - F(k+2) * (k+2 choose k) … - F(N) * (N choose k) --(1)
Justification:
ϕ(k, G’) * (N-k)! is the number of perfect matchings in G U G’ where
- k or more edges are chosen from G’
- some k of the matched edges that belong to G’ have been marked (these marked edges come from ϕ(k, G’) term, and the rest come from (N-k)! term).
Therefore, the perfect matchings where exactly k+i edges are used from G’ are counted (k+i choose k) times in the term ϕ(k, G’) * (N-k)!, hence the above recurrence.
If ϕ(k, G’) can be built, then (1) above can be used to find our solution (= F[0]) in O(N^2) time.
Constructing ϕ(k, G’)
ϕ(k, G’) = number of matchings of size k in G’, is coefficient of xk in matching polynomial of G’.
Denote
C(k, n) = number of matchings of size k in a cycle graph with n vertices.
L(k, n) = number of matchings of size k in a line graph with n vertices.
Then we have
L(k, n) = L(k-1, n-2) + L(k, n-1)
In any k-matching, either
- Edge (0,1) is used. The number of ways of matching remaining edges is L(k-1, n-2).
- Edge (0,1) is not used. The number of ways of matching remaining edges is L(k, n-1).
C(k, n) = L(k, n) + L(k-1, n-2)
Because, in any k-matching, either
- the edge (0, 1) is used. Number of ways of matching remaining edges is L(k-1, n-2)
- the edge (0, 1) is not used. Number of ways of matching remaining edges is L(k, n)
Once we construct the arrays C(k, n), ϕ(k, G’) can be found as follows:
Let G’ be a union of l cycles of sizes n1, n2, n3 … nl.
Consider any k-matching of G’. It will be a set of k edges of G’, where no two edges have same end point.
The connected components of graph G’ are the cycles. If we pick a matching of size ki from cycle ni and matching of size kj from cycle nj, then the union of these two matching(a matching is a set of independent edges) is also a matching, and its size is ki+kj.
The same idea can be used backwards to say that any k-matching of G’ will consist of a matching of size k1 in cycle n1, matching of size k2 in n2, …, a matching of size kl in nl, such that k1 + k2 + … + kl = k. for a given set of values of ki's, the number of k-matchings of G’ which uses ki edges from cycles ni, is Π li=1 C(ki, ni). The total number of k-matchings of G’ is
Σk1+k2+…+kl=k Π li=1 C(ki, ni)
It is easy to see that if C(n) = Σ nk=1 C(k, n) xk is the matching
polynomial of cycles of length n, then
coefficient of xk in C(n1) * C(n2) … C(nl) is Σk1+k2+…+kl=k Π li=1 C(ki, ni)
Therefore,
ϕ(G’) = Σ nk=1 ϕ(k, G’) xk = C(n1) * C(n2) … C(nl)
The term Σ nk=1 ϕ(k, G’) xk is called matching polynomial of graph G’.
In fact, it can be stated in general that if ϕ(G) is matching polynomial of graph G, then
ϕ(G1 U G2 U G3 …) = ϕ(G1) * ϕ(G2) * ϕ(G3) …
The polynomials C(n) can be precomputed in O(N2) time, and the matching polynomial for ϕ(G’) can be constructed in (O(n2) time. The coefficient of xk in ϕ(G’) is ϕ(k, G’).