PROBLEM LINKSDIFFICULTYEASY PREREQUISITESKirchhoff's Matrix Tree Theorem, Math PROBLEMFind the number of Trees that contain k*n nodes, which are labeled from 0 to k*n1, such that
QUICK EXPLANATIONLet us assume there is a graph on k*n vertices such that for any two vertices a and b, if a div k is not equal to b div k, there is an edge between them. On such a graph, every unique spanning tree is a valid tree according to the definition of the problem statement. Since there are only 3 possible different values of k, let us consider them one by one. k = 1The Kirchhoff's Matrix for a graph with n vertices will look like n1 1 1 ... 1 1 n1 1 ... 1 1 1 n1 ... 1 ... 1 1 1 ... n1 We have to find the the determinant of any cofactor of the above matrix to find the number of spanning trees. Let us consider the (n,n) cofactor. n1 1 1 ... 1 1 n1 1 ... 1 1 1 n1 ... 1 ... 1 1 1 ... n1 The (n,n) cofactor consists of n1 rows and n1 columns. The determinant of the above matrix will give us the answer for k = 1. Let us perform some operations that do not affect the determinant and make the matrix triangular. This way the determinant is found as the product of the terms in the major diagonal. Starting from the top row and proceeding downwards, let us subtract the next row from the current row. Thus
n n 0 ... 0 0 0 n n ... 0 0 0 0 n ... 0 0 .... 0 0 0 ... n n 1 1 1 ... 1 n1
Eventually we get n n 0 ... 0 0 0 n n ... 0 0 ... 0 0 0 ... n n 0 0 0 ... 0 1 Thus, the answer for k = 1 is n^{n2}. The analysis for k = 2 and k = 3 are much more involved. EXPLANATIONk = 2(2n,2n) cofactor of the Kirchhoff's Matrix for a graph with 2*n nodes will look like 2n2 0 1 1 ... 1 1 1 0 2n2 1 1 ... 1 1 1 1 1 2n2 0 ... 1 1 1 1 1 0 2n2 ... 1 1 1 ... 1 1 1 1 ... 2n2 0 1 1 1 1 1 ... 0 2n2 1 1 1 1 1 ... 1 1 2n2 It contains 2n1 rows and 2n1 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. 2n2 (2n2) 0 0 ... 0 0 0 1 2n1 (2n1) 1 ... 0 0 0 0 0 2n2 (2n2) ... 0 0 0 0 0 1 2n1 ... 0 0 0 ... 0 0 0 0 ... 2n2 (2n2) 0 0 0 0 0 ... 1 2n1 (2n1) 1 1 1 1 ... 1 1 2n2 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. 2n2 (2n2) 0 0 ... 0 0 0 0 2n (2n1) 1 ... 0 0 0 0 0 2n2 (2n2) ... 0 0 0 0 0 0 2n ... 0 0 0 ... 0 0 0 0 ... 2n2 (2n2) 0 0 0 0 0 ... 0 2n (2n1) 1 1 1 1 ... 1 1 2n2 We can use row 3 on row 2, row 5 on row 4 and so on to convert the matrix into 2n2 (2n2) 0 0 ... 0 0 0 0 2n 0 2n ... 0 0 0 0 0 2n2 (2n2) ... 0 0 0 0 0 0 2n ... 0 0 0 ... 0 0 0 0 ... 2n2 (2n2) 0 0 0 0 0 ... 0 2n (2n1) 1 1 1 1 ... 1 1 2n2 Now we can convert the final row using all the previous rows into 2n2 (2n2) 0 0 ... 0 0 0 0 2n 0 2n ... 0 0 0 0 0 2n2 (2n2) ... 0 0 0 0 0 0 2n ... 0 0 0 ... 0 0 0 0 ... 2n2 (2n2) 0 0 0 0 0 ... 0 2n (2n1) 0 0 0 0 ... 0 (2n2) 2n2 The last row can reduce the second to last row into 2n2 (2n2) 0 0 ... 0 0 0 0 2n 0 2n ... 0 0 0 0 0 2n2 (2n2) ... 0 0 0 0 0 0 2n ... 0 0 0 ... 0 0 0 0 ... 2n2 (2n2) 0 0 0 0 0 ... 0 1 0 0 0 0 0 ... 0 (2n2) 2n2 Of course the matrix is triangular now and the determinant is simply the product of the terms in the major diagonal. There are n occurances of 2n2 and n2 occurances of 2n in the major diagonal. Thus, the answer for k=2 is (2n)^{n2}(2n2)^{n}. We leave k = 3 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 k = 1 and k = 2. The result for any k is (k*n)^{n2}(k*(n1))^{(k1)*n} The limits were intentionally kept low enough to not let the existance of closed form solution be apparent. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 14 May '13, 15:30

@vineetpaliwal 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 :) answered 08 Jun '13, 00:44

@lallu1: 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 npartite graphs" , I had full knowledge of how that would apply to this problem . answered 07 Jun '13, 05:29

@vineetpaliwal 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... answered 07 Jun '13, 00:48

calculated ten different values by hand and then guessed the formula ! answered 17 May '13, 13:33

What I tried during contest:
answered 16 May '13, 11:02

@vineetpaliwal : 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. answered 14 May '13, 17:06

@n2n_ : 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 . @aayushagarwal : 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 . answered 14 May '13, 16:47

"The limits were intentionally kept low enough to not let the existance of closed form solution be apparent" 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. :) answered 14 May '13, 16:42

The problem basically asked for the number of spanning trees in a complete Npartite graph. While searching for the same I found this paper which gives the formula in the very first page. answered 14 May '13, 15:52
i had to search a lot in the internet and after 1 day i got it. this directformula based problem which depends solely on the internet should be avoided in the future . no offence to the setter :)
(14 May '13, 15:57)
