TREE - Editorial

[gamabunta]

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Kirchhoff’s Matrix Tree Theorem, Math

PROBLEM

Find the number of Trees that contain k*n nodes, which are labeled from 0 to k*n-1, such that

• There is no edge between two vertices a and b for which a div k = b div k, where div is the integer division operator

QUICK EXPLANATION

Let 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 = 1

The Kirchhoff’s Matrix for a graph with n vertices will look like

n-1  -1  -1 ...  -1
 -1 n-1  -1 ...  -1
 -1  -1 n-1 ...  -1
...
 -1  -1  -1 ... n-1

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.

n-1  -1  -1 ...  -1
 -1 n-1  -1 ...  -1
 -1  -1 n-1 ...  -1
...
 -1  -1  -1 ... n-1

The (n,n) cofactor consists of n-1 rows and n-1 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

• Subtract row 2 from row 1
• Subtract row 3 from row 2, and so on

 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

• 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

 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^n-2.

The analysis for k = 2 and k = 3 are much more involved.

EXPLANATION

k = 2

(2n,2n) cofactor of the Kirchhoff’s Matrix for a graph with 2*n nodes will look like

 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

It contains 2n-1 rows and 2n-1 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.

 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

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.

 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

We can use row 3 on row 2, row 5 on row 4 and so on to convert the matrix into

 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

Now we can convert the final row using all the previous rows into

 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

The last row can reduce the second to last row into

 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

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 2n-2 and n-2 occurances of 2n in the major diagonal.

Thus, the answer for k=2 is (2n)^n-2(2n-2)ⁿ.

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)^n-2(k*(n-1))^(k-1)*n

The limits were intentionally kept low enough to not let the existance of closed form solution be apparent.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

[n2n]

The problem basically asked for the number of spanning trees in a complete N-partite graph. While searching for the same I found this paper which gives the formula in the very first page.

[aayushagarwal]

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

[anudeep2011]

“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.

[vineetpaliwal]

@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 .

[aayushagarwal]

@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.

[bugkiller]

For k = 1, the result is straight-forward as i / k != j/k for all i, j ∈ Z, hence every tree is a good tree => n^(n-2)

In general cases, I read the paper here, a very good paper by J.W. Moon

[bcurcio]

The limits were intentionally kept low enough to not let the existance of closed form solution be apparent.

Because 300 people with a 0 second solution wouldn’t be clear enough…

[bugkiller]

A probable reason to 0 sec submission might also be ONE test case per file?

[gamabunta]

One can only hope to scare away the unseasoned

(not that this was ever the intention of course)

[flashmt]

What I tried during contest:

1. Looking for solution when K = 2.

2. Brute force for N = 2, 3 when K = 3 and guess the solution by some random formula (fortunately got accepted after 2nd try :D)

[knsn1994]

calculated ten different values by hand and then guessed the formula !

[lallu1]

@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…

[vineetpaliwal]

@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 n-partite graphs” , I had full knowledge of how that would apply to this problem .

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 .

[lallu1]

@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