# MAXMATCH - Editorial **URL:** \ **Category:** editorial\ **Tags:** combinatorics, dynamic-programming, editorial, ltime24, medium\ **Created:** [May 27, 2015, 3:55pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976 "2015-05-27T15:55:06Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![saurabh060792](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabh060792/32/306717_2.png) [@saurabh060792](https://discuss.codechef.com/u/saurabh060792)\ **Post date:** [May 27, 2015, 3:55pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/1 "2015-05-27T15:55:06Z")
### PROBLEM LINK: [Practice](http://www.codechef.com/problems/MAXMATCH) [Contest](http://www.codechef.com/LTIME24/problems/MAXMATCH) ### DIFFICULTY: MEDIUM ### PREREQUISITES: Combinatorics, Dynamic Programming ### PROBLEM: Given a bipartite graph having partites **X** and **Y**. Partite **X** will contain all permutations of Set **S = {1,2,..n}**. Partite **Y** will contain all strings of length **(N-1)** having characters **‘I’** and **‘D’** only.There will be an edge between permutation **x** and string **y** if string **y** is the signature of the permutation **x** and weight of the edge will be the square of the inversion count in permutation **x**. We have to find the maximum weighted matching in the given bipartite graph. ### EXPLANATION: We are given a bipartite graph in which partite **X** contains permutations of **S** and partite **Y** contains strings of length N-1 containing I and D only. There is an edge between x\in X and y \in Y if and only if y is the signature ( explained in question ) of x. Notice here that degree of all the vertices in partite **X** is 1 and the degree of a vertex in partite **Y** will be equal to the number of permutations that satisfy this particular signature string corresponding to that vertex. Hence to get the maximum matching, for each vertex in partite **Y** , we have to select the edge with maximum weight. Now the question arises that which permutation will give the maximum inversion count corresponding to a particular signature string. It is not very difficult to note that the lexicographically greatest permutation will give us the maximum inversion count. Lets digress a little bit, assume that the weight of the edges is equal to the inversion count of the permutation instead of square of it. In this case, a naive solution is very easy i.e. for each signature string find the inversion count of lexicographically greatest permutation and add it to the answer. But by dynamic programming we can reduce the time complexity of the algorithm. Define _f(n)_ as the sum of inversion count of lexicographically greatest permutation of all signature strings of length _n_. Consider a particular class of signature strings of length _n_ in which exactly first _k_ characters are **I**. A general string of this class will look like this ![image](http://i.imgur.com/BEMcwxi.jpg) The lexicographically greatest permutation will have n-k+1, n-k+2 … n+1 as its first _k+1_ number ( solve [this](https://www.hackerrank.com/contests/101hack22/challenges/permutation-of-natural-numbers) problem if you are unsure about constructing lexicographically greatest permutation of a given signature string ). So due to this part number of inversion count will be _(k+1)\*(n-k)_ and there are 2^{n-k-1} strings which has exactly first _k_ characters as **I**. So the inversion count due to this class of stings will be (k+1)(n-k)2^{n-k-1} + f(n-k-1). Hence our dp formulation will be as follows f(n) = \sum\_{k=0}^{n-1}(k+1)(n-k)2^{n-k-1} + f(n-k-1) Coming back to our original problem where we have the square of the inversion count as the edge weight. The solution to this problem is just a extension of what we have solved above. Define _g(n)_ as the sum of square of inversion count of lexicographically greatest permutation of all signature strings of length _n_. Consider the class of signature strings in which exactly first _k_ characters are **I**. The answer for this class of strings will be (k+1)^2(n-k)^22^{n-k-1} + 2(k+1)(n-k)f(n-k-1)+g(n-k-1). Hence our dp formulation will be as follows g(n) = \sum\_{k=0}^{n-1}(k+1)^2(n-k)^22^{n-k-1} + 2(k+1)(n-k)f(n-k-1)+g(n-k-1) Now precompute all the _f(n)_ and _g(n)_, then answer each test case in \mathcal{O}(1) time. The time complexity of the algorithm is \mathcal{O}(n^2). ### AUTHOR’S AND TESTER’S SOLUTIONS: Author’s solution can be found [here](http://www.codechef.com/download/Solutions/LTIME24/Setter/MAXMATCH.cpp) Tester’s solution can be found [here](http://www.codechef.com/download/Solutions/LTIME24/Tester/MAXMATCH.cpp) ---
**Author:** ![prashkr](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@prashkr](https://discuss.codechef.com/u/prashkr)\ **Post date:** [May 31, 2015, 8:49pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/2 "2015-05-31T20:49:09Z")
How did you get the second term in equation of g(n)? ---
**Author:** ![midnight\_coder](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@midnight\_coder](https://discuss.codechef.com/u/midnight_coder)\ **Post date:** [June 2, 2015, 9:26am UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/3 "2015-06-02T09:26:50Z")
Please explain how did you derive the formula for g(n)? ---
**Author:** ![singh99](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@singh99](https://discuss.codechef.com/u/singh99)\ **Post date:** [June 14, 2015, 8:28pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/4 "2015-06-14T20:28:37Z")
Why is it (k+1)(n-k)? Shouldn’t it be (k+1)(n-k-1)? ---
**Author:** ![shubh\_gupta](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@shubh\_gupta](https://discuss.codechef.com/u/shubh_gupta)\ **Post date:** [July 17, 2015, 1:22pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/5 "2015-07-17T13:22:55Z")
please explain second folmula in little breif 🙂 ---
**Author:** ![saurabh060792](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabh060792/32/306717_2.png) [@saurabh060792](https://discuss.codechef.com/u/saurabh060792)\ **Post date:** [June 6, 2015, 6:24pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/6 "2015-06-06T18:24:07Z")
Sorry for the late reply. Lets consider a particular string of the class which has exactly k characters as I and then a D. Inversion count of that string is (k+1)\*(n-k) [because of the first part III…ID] and x\_i [because of the second part s\_k+2…s\_n]. Square of this will be [(k+1)(n-k) + x\_i]^2 = (k+1)^2(n-k)^2 + x\_i^2 + 2(k+1)(n-k)x\_i Now there are 2^(n-k-1) string in that class. Taking account of all of that we will get that expression for g(n). Hope that clears your question. ---
**Author:** ![saurabh060792](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabh060792/32/306717_2.png) [@saurabh060792](https://discuss.codechef.com/u/saurabh060792)\ **Post date:** [June 6, 2015, 6:25pm UTC](https://discuss.codechef.com/t/maxmatch-editorial/10976/7 "2015-06-06T18:25:23Z")
Please read my comment on @prashkr question.