Answers to: TREE - Editorialhttps://discuss.codechef.com/questions/9727/tree-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/TREE">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/TREE">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>EASY</p>
<h1>PREREQUISITES</h1>
<p><a href="http://en.wikipedia.org/wiki/Kirchhoff's_theorem">Kirchhoff's Matrix Tree Theorem</a>, Math</p>
<h1>PROBLEM</h1>
<p>Find the number of Trees that contain <b>k*n</b> nodes, which are labeled from <b>0</b> to <b>k*n-1</b>, such that</p>
<ul>
<li>There is no edge between two vertices <b>a</b> and <b>b</b> for which <b>a div k = b div k</b>, where <b>div</b> is the <b>integer</b> <b>division</b> operator</li>
</ul>
<h1>QUICK EXPLANATION</h1>
<p>Let us assume there is a graph on <b>k*n</b> vertices such that for any two vertices <b>a</b> and <b>b</b>, if <b>a</b> <b>div</b> <b>k</b> is not equal to <b>b</b> <b>div</b> <b>k</b>, there is an edge between them. On such a graph, every unique <b>spanning</b> <b>tree</b> is a valid tree according to the definition of the problem statement.</p>
<p>Since there are only <b>3</b> possible different values of <b>k</b>, let us consider them one by one.</p>
<h2>k = 1</h2>
<p>The <b>Kirchhoff's</b> <b>Matrix</b> for a graph with <b>n</b> vertices will look like</p>
<pre>n-1 -1 -1 ... -1
-1 n-1 -1 ... -1
-1 -1 n-1 ... -1
...
-1 -1 -1 ... n-1
</pre>
<p>We have to find the the <b>determinant</b> of any <b>cofactor</b> of the above matrix to find the number of spanning trees. Let us consider the <b>(n,n)</b> <b>cofactor</b>.</p>
<pre>n-1 -1 -1 ... -1
-1 n-1 -1 ... -1
-1 -1 n-1 ... -1
...
-1 -1 -1 ... n-1
</pre>
<p>The <b>(n,n)</b> <b>cofactor</b> consists of <b>n-1</b> rows and <b>n-1</b> columns.</p>
<p>The determinant of the above matrix will give us the answer for <b>k = 1</b>. Let us perform some operations that do not affect the determinant and make the matrix <b>triangular</b>. This way the determinant is found as the <b>product of the terms in the major diagonal</b>.</p>
<p>Starting from the top row and proceeding downwards, let us subtract the next row from the current row. Thus</p>
<ul>
<li>Subtract row 2 from row 1</li>
<li>Subtract row 3 from row 2, and so on</li>
</ul>
<pre> n -n 0 ... 0 0
0 n -n ... 0 0
0 0 n ... 0 0
....
0 0 0 ... n -n
-1 -1 -1 ... -1 n-1
</pre>
<ul>
<li>We can use the rows 1 to n-2 to eliminate the first -1 in row n-1</li>
<li>We can use the rows 2 to n-2 to eliminate the second -1 in row n-1, and so on</li>
</ul>
<p>Eventually we get</p>
<pre> n -n 0 ... 0 0
0 n -n ... 0 0
...
0 0 0 ... n -n
0 0 0 ... 0 1
</pre>
<p>Thus, the answer for <b>k = 1</b> is <b>n<sup>n-2</sup></b>.</p>
<p>The analysis for <b>k = 2</b> and <b>k = 3</b> are much more involved.</p>
<h1>EXPLANATION</h1>
<h2>k = 2</h2>
<p><b>(2n,2n)</b> <b>cofactor</b> of the Kirchhoff's Matrix for a graph with <b>2*n</b> nodes will look like</p>
<pre> 2n-2 0 -1 -1 ... -1 -1 -1
0 2n-2 -1 -1 ... -1 -1 -1
-1 -1 2n-2 0 ... -1 -1 -1
-1 -1 0 2n-2 ... -1 -1 -1
...
-1 -1 -1 -1 ... 2n-2 0 -1
-1 -1 -1 -1 ... 0 2n-2 -1
-1 -1 -1 -1 ... -1 -1 2n-2
</pre>
<p>It contains <b>2n-1</b> rows and <b>2n-1</b> columns. Similar to how we subtracted the next row from the current one for k = 1, we will subtract the next row from the current one, starting from the top row and working downwards.</p>
<pre> 2n-2 -(2n-2) 0 0 ... 0 0 0
1 2n-1 -(2n-1) -1 ... 0 0 0
0 0 2n-2 -(2n-2) ... 0 0 0
0 0 1 2n-1 ... 0 0 0
...
0 0 0 0 ... 2n-2 -(2n-2) 0
0 0 0 0 ... 1 2n-1 -(2n-1)
-1 -1 -1 -1 ... -1 -1 2n-2
</pre>
<p>We can use the first row to eliminate terms on the left of the major diagonal in the second row. Similarly, we can use the third row to eliminate terms on the left of the major diagonal in the fourth row, and so on.</p>
<pre> 2n-2 -(2n-2) 0 0 ... 0 0 0
0 2n -(2n-1) -1 ... 0 0 0
0 0 2n-2 -(2n-2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n-2 -(2n-2) 0
0 0 0 0 ... 0 2n -(2n-1)
-1 -1 -1 -1 ... -1 -1 2n-2
</pre>
<p>We can use row 3 on row 2, row 5 on row 4 and so on to convert the matrix into</p>
<pre> 2n-2 -(2n-2) 0 0 ... 0 0 0
0 2n 0 -2n ... 0 0 0
0 0 2n-2 -(2n-2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n-2 -(2n-2) 0
0 0 0 0 ... 0 2n -(2n-1)
-1 -1 -1 -1 ... -1 -1 2n-2
</pre>
<p>Now we can convert the final row using all the previous rows into</p>
<pre> 2n-2 -(2n-2) 0 0 ... 0 0 0
0 2n 0 -2n ... 0 0 0
0 0 2n-2 -(2n-2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n-2 -(2n-2) 0
0 0 0 0 ... 0 2n -(2n-1)
0 0 0 0 ... 0 -(2n-2) 2n-2
</pre>
<p>The last row can reduce the second to last row into</p>
<pre> 2n-2 -(2n-2) 0 0 ... 0 0 0
0 2n 0 -2n ... 0 0 0
0 0 2n-2 -(2n-2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n-2 -(2n-2) 0
0 0 0 0 ... 0 1 0
0 0 0 0 ... 0 -(2n-2) 2n-2
</pre>
<p>Of course the matrix is triangular now and the determinant is simply the product of the terms in the major diagonal. There are <b>n</b> occurances of <b>2n-2</b> and <b>n-2</b> occurances of <b>2n</b> in the major diagonal.</p>
<p>Thus, the answer for <b>k=2</b> is <b>(2n)<sup>n-2</sup>(2n-2)<sup>n</sup></b>.</p>
<p>We leave <b>k = 3</b> as an exercise to the reader. As a matter of fact, this month's tester David proved during the testing of this problem that there is a closed form for any k that can be calculated using the same ideas presented above for <b>k = 1</b> and <b>k = 2</b>. The result for any <b>k</b> is</p>
<p><b>(k*n)<sup>n-2</sup>(k*(n-1))<sup>(k-1)*n</sup></b></p>
<p>The limits were intentionally kept <b>low</b> <b>enough</b> to not let the existance of closed form solution be apparent.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/TREE.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/TREE.cpp">here</a>.</p>enSat, 08 Jun 2013 00:44:07 +0530Answer by lallu1https://discuss.codechef.com/questions/9727/tree-editorial/12875<p><a href="/users/8704/vineetpaliwal">@vineetpaliwal</a> I agree with you that math is the backbone of computer science, i really like problems where good knowledge of maths is involved and thats why I really like codechef than any other site :) The only thing I want to point out is, We all are from different backgrounds, maybe maths, maybe physics etc. and we might not have heard about such theorems. Don't you think some direction should have been given, so all of us can attempt to learn "fundamentals of maths", please try to understand that one has to be Kirchoff in order to solve this problem who have not heard of this theorem ever before.... And I apologize to call you lucky btw :)</p>lallu1Sat, 08 Jun 2013 00:44:07 +0530https://discuss.codechef.com/questions/9727/tree-editorial/12875Answer by vineetpaliwalhttps://discuss.codechef.com/questions/9727/tree-editorial/12824<p><a href="/users/15202/lallu1">@lallu1</a>: Obviously the link should not have been provided because its a contest , right ?
I think it is wrong to attribute my discovery to luck . I was already aware of Cayley formula and Kirchoff's Matrix Tree Theorem so I knew how to begin . And only because I had the relevant knowledge I was able to search in the right direction . So when I searched on google for "number of spanning trees of n-partite graphs" , I had full knowledge of how that would apply to this problem .<br>
About "Maths" , maths is the basis of all sciences . There is lot of fundamental play of mathematics in computer science . Theory of Automata , proofs / mappings of NP completeness , graph theory and even if you do computer graphics you have to work with derivates and what not . So it is immature to think that mathematics is not important . It is the most important component of computer science .</p>vineetpaliwalFri, 07 Jun 2013 05:29:44 +0530https://discuss.codechef.com/questions/9727/tree-editorial/12824Answer by lallu1https://discuss.codechef.com/questions/9727/tree-editorial/12813<p><a href="/users/8704/vineetpaliwal">@vineetpaliwal</a> Dont you think the link should be given in the problem, I didnt even know the caley's formula, I started approaching the problem in random direction and got nothing. This problem was a serious waste of time, would have been a lot better if provided the related link. You were lucky, you got that paper on internet, but again you can't share it on the problem page during contest. I actually have no problem in learning something new but with at least a source provided. I think the codechef is not only for Maths students :) May be I am wrong...</p>lallu1Fri, 07 Jun 2013 00:48:11 +0530https://discuss.codechef.com/questions/9727/tree-editorial/12813Answer by knsn1994https://discuss.codechef.com/questions/9727/tree-editorial/10238<p>calculated ten different values by hand and then guessed the formula !</p>knsn1994Fri, 17 May 2013 13:33:43 +0530https://discuss.codechef.com/questions/9727/tree-editorial/10238Answer by flashmthttps://discuss.codechef.com/questions/9727/tree-editorial/10144<p>What I tried during contest:</p>
<ol>
<li>
<p>Looking for solution when K = 2.</p>
</li>
<li>
<p>Brute force for N = 2, 3 when K = 3 and guess the solution by some random formula (fortunately got accepted after 2nd try :D)</p>
</li>
</ol>flashmtThu, 16 May 2013 11:02:56 +0530https://discuss.codechef.com/questions/9727/tree-editorial/10144Comment by gamabunta on bcurcio's answerhttps://discuss.codechef.com/questions/9727/tree-editorial#10131<p>One can only hope to scare away the unseasoned :P</p>
<p>(not that this was ever the intention of course)</p>gamabuntaThu, 16 May 2013 01:50:12 +0530https://discuss.codechef.com/questions/9727/tree-editorial#10131Comment by bugkiller on bcurcio's answerhttps://discuss.codechef.com/questions/9727/tree-editorial#10009<p>A probable reason to 0 sec submission might also be ONE test case per file?</p>bugkillerWed, 15 May 2013 11:06:25 +0530https://discuss.codechef.com/questions/9727/tree-editorial#10009Answer by bcurciohttps://discuss.codechef.com/questions/9727/tree-editorial/9992<blockquote>
<p>The limits were intentionally kept low enough to not let the existance of closed form solution be apparent.</p>
</blockquote>
<p>Because 300 people with a 0 second solution wouldn't be clear enough......</p>bcurcioWed, 15 May 2013 04:44:01 +0530https://discuss.codechef.com/questions/9727/tree-editorial/9992Answer by bugkillerhttps://discuss.codechef.com/questions/9727/tree-editorial/9836<p>For k = 1, the result is straight-forward as i / k != j/k for all i, j ∈ <strong>Z</strong>, hence every tree is a good tree => n^(n-2)</p>
<p>In general cases, I read the paper <a href="http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.aoms/1177698524">here</a>, a very good paper by J.W. Moon</p>bugkillerTue, 14 May 2013 18:55:06 +0530https://discuss.codechef.com/questions/9727/tree-editorial/9836Answer by aayushagarwalhttps://discuss.codechef.com/questions/9727/tree-editorial/9805<p><a href="/users/8704/vineetpaliwal">@vineetpaliwal</a> : Even i also got the formula but perhaps from a diferent paper but same thing. i also got the logic behind it and for k=1 cayley's theorem was known to me and that is a different case but for other values of k its difficult to apply your own idea and derive the formula without the help of the internet. had we were participating in an arena where there is no internet then deriving this formula would become impossible perhaps. its obvious that we get to learn new formulas but searching takes time . only if this problem is limited to contests where we have access to internet then its good but otherwise not.</p>aayushagarwalTue, 14 May 2013 17:06:12 +0530https://discuss.codechef.com/questions/9727/tree-editorial/9805Answer by vineetpaliwalhttps://discuss.codechef.com/questions/9727/tree-editorial/9789<p><a href="/users/2990/n2n_">@n2n_</a> : Yes I used the same paper . The result in that paper is much more general and can apply even when all the partitions don't have same number of elements in them .
<a href="/users/10503/aayushagarwal">@aayushagarwal</a> : On the other hand , we get an opportunity to learn new formulas which are available only in research papers . In this case everyone knew Cayley's formula , but few knew about its generalization including me . But an internet search along the right direction got me there . It takes some knowledge to start searching in the right direction . And it helps us learn new concepts / formulas . I am not against such a problem , frankly speaking .</p>vineetpaliwalTue, 14 May 2013 16:47:29 +0530https://discuss.codechef.com/questions/9727/tree-editorial/9789Answer by anudeep2011https://discuss.codechef.com/questions/9727/tree-editorial/9787<p>"The limits were intentionally kept low enough to not let the existance of closed form solution be apparent" </p>
<p>But then after the 1st few submissions which too 0.00 sec with 2.6mb of space it was clear that it indeed has a closed form formula. :)</p>anudeep2011Tue, 14 May 2013 16:42:14 +0530https://discuss.codechef.com/questions/9727/tree-editorial/9787Comment by aayushagarwal on n2n_'s answerhttps://discuss.codechef.com/questions/9727/tree-editorial#9757<p>i had to search a lot in the internet and after 1 day i got it.
this direct-formula based problem which depends solely on the internet
should be avoided in the future . no offence to the setter :)</p>aayushagarwalTue, 14 May 2013 15:57:48 +0530https://discuss.codechef.com/questions/9727/tree-editorial#9757Answer by n2n_https://discuss.codechef.com/questions/9727/tree-editorial/9749<p>The problem basically asked for the number of spanning trees in a complete N-partite graph. While searching for the same I found this <a href="http://www.cs.ucsb.edu/~omer/DOWNLOADABLE/multipartite94.pdf">paper</a> which gives the formula in the very first page. </p>n2n_Tue, 14 May 2013 15:52:06 +0530https://discuss.codechef.com/questions/9727/tree-editorial/9749