CSTREE-python

I would be very thankful if someone could let me know why my solution for cstree gives such errors.

@darkhorse65 @adavis444 @kalptaru_123 @pynhp9x You people solved in python ??

It would appear that no solutions in Python passed any subtask other than subtask 3 (with the exception of a few PyPy solutions that passed subtask 1). Time and Memory are both major issues for this problem, and your RE (NZEC) submissions probably ran out of memory. Fortunately, assuming constant multiplication and exponentiation, subtask 3 has an O(1) Time and Space solution (although O((log N)2(log K)2) Time and Space is probably more accurate).

Since M = N(N-1)/2, Gs is complete, and therefore its complement is empty. Consequently, H will be a complete multipartite graph, or a complete n-partite graph. I recommend reading about complete bipartite graphs for familiarity with the case that K = 2.

We have a formula for the number of spanning trees of a complete multipartite graph on the bottom of the first page of this paper: https://link.springer.com/chapter/10.1007/978-3-642-46908-4_38

For our purposes, k = K, ni = N, and p = NK. The number of spanning trees for K ≥ 2 is therefore (NK)K-2((NK-N)N-1)K.

I am uncertain how to solve the task for large values of K. Calculating the determinant using NumPy’s numpy.linalg.det is likely to be highly inaccurate, as this yields a float from integer inputs. Since the constraints we have are 1 ≤ N ≤ 30 and 1 ≤ K ≤ 108, I am skeptical that any O(N2K2) solution will fit in time or in memory. Any insight into this would be greatly appreciated!

1 Like

I adapted my c++ code to python and almost worked (only failed one case). I’m not used to Python and can’t see my error but I’m pretty sure that it can be done in python.

https://www.codechef.com/viewsolution/25917819

Mmmmm…
Looks like Adavis444’s answer has a point. You calculated modulo at each step thus saving memory.

Time and Memory are both major issues for this problem, and your RE (NZEC) submissions probably ran out of memory.

your solution build arrays of (nk) * (nk) size, that is too large

Too large even for subtasks ??

Here you can have a look at it, I tried my best to explain it clearly for 100 points:D

1 Like