TREE - Editorial
#PROBLEM LINKS
[Practice][1]
[Contest][2]
#DIFFICULTY
EASY
#PREREQUISITES
[Kirchhoff's Matrix Tree Theorem][5], Math
#PROBLEM
Find the number of Trees that contain <b>k\*n</b> nodes, which are labeled from <b>0</b> to <b>k\*n</b>, <b>k\*n\-1</b>, such that
* 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
#QUICK EXPLANATION
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.
Since there are only <b>3</b> possible different values of <b>k</b>, let us consider them one by one.
## k = 1
The <b>Kirchhoff's</b> <b>Matrix</b> for a graph with <b>n</b> vertices will look like
<pre>
n-1 -1 -1 ... -1
-1 n-1 -1 ... -1
-1 -1 n-1 ... -1
...
-1 -1 -1 ... n-1
</pre>
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>.
<pre>
n-1 -1 -1 ... -1
-1 n-1 -1 ... -1
-1 -1 n-1 ... -1
...
-1 -1 -1 ... n-1
</pre>
The <b>(n,n)</b> <b>cofactor</b> consists of <b>n-1</b> rows and <b>n-1</b> columns.
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>.
Starting from the top row and proceeding downwards, let us subtract the next row from the current row. Thus
* Subtract row 2 from row 1
* Subtract row 3 from row 2, and so on
<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>
* We can use the rows 1 to n-2 to eliminate the first -1 in row n-1
* We can use the rows 2 to n-2 to eliminate the second -1 in row n-1, and so on
Eventually we get
<pre>
n -n 0 ... 0 0
0 n -n ... 0 0
...
0 0 0 ... n -n
0 0 0 ... 0 1
</pre>
Thus, the answer for <b>k = 1</b> is <b>n<sup>n-2</sup></b>.
The analysis for <b>k = 2</b> and <b>k = 3</b> are much more involved.
#EXPLANATION
## k = 2
<b>(2n,2n)</b> <b>cofactor</b> of the Kirchhoff's Matrix for a graph with <b>2\*n</b> nodes will look like
<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>
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.
<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>
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.
<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>
We can use row 3 on row 2, row 5 on row 4 and so on to convert the matrix into
<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>
Now we can convert the final row using all the previous rows into
<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>
The last row can reduce the second to last row into
<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>
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.
Thus, the answer for <b>k=2</b> is <b>(2n)<sup>n-2</sup>(2n-2)<sup>n</sup></b>.
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
<b>(k\*n)<sup>n-2</sup>(k\*(n-1))<sup>(k-1)\*n</sup></b>
The limits were intentionally kept <b>low</b> <b>enough</b> to not let the existance of closed form solution be apparent.
#SETTER'S SOLUTION
Can be found [here][3].
#TESTER'S SOLUTION
Can be found [here][4].
[1]: http://www.codechef.com/problems/TREE
[2]: http://www.codechef.com/MAY13/problems/TREE
[3]: http://www.codechef.com/download/Solutions/2013/May/Setter/TREE.cpp
[4]: http://www.codechef.com/download/Solutions/2013/May/Tester/TREE.cpp
[5]: http://en.wikipedia.org/wiki/Kirchhoff's_theorem