1 / 8
Dec 2008

I got a TLE for this problem in Python. The same solution converted to C gets AC in 0.04s. I see 3 people have already solved it in Python. Anyone cares to share some tips?

My approach is dfs with memoization. First, generate a tree from given input, then run the recursive function (with cache) on the tree. Let's define the function f(isGreen,node) as the {minimum|maximum} number of green color nodes in the subtree below @node and @node itself, when the @node have color {green if @isGreen=True, red or blue otherwise}.

Now, we will consider the case we want the maximum number of green nodes.

If the number of children for @node is 0, f(isGreen,node) is defined as follows:

	if @isGreen==True:
		f(isGreen,node) = 1
	else:
		f(isGreen,node) = 0

If the number of children for @node is 1, f(isGreen,node) is defined as follows:

	if @isGreen==True:
		f(isGreen,node) = f(False,@node's child) + 1
	else:
		f(isGreen,node) = max(f(True,@node's child),f(False,@node's child))

If the number of children for @node is 2, f(isGreen,node) is defined as follows:

	if @isGreen==True:
		f(isGreen,node) = f(False,@node's 1st child) + f(False,@node's 2nd child) + 1
	else:
		A = f(True,@node's 1st child) + f(False,@node's 2nd child)
		B = f(False,@node's 1st child) + f(True,@node's 2nd child)
		f(isGreen,node) = max(A,B)

For the case we want the minimum number of green nodes, just change max() to min().

Thanks. My solution is also the same, and it passes when coded in C. What I wanted was for some tips about how you got that code to be fast enough to get AC within the time limit in Python.

I didn't do any optimizations. I think our approach is O(N*2), and it should run within the time limit.
Can you show me your code for checking overhead?

Here's my code:

# removed after bugs/optimizations pointed out, thanks to Hachimori

I checked your code. I fixed following things and made it accepted.

  1. I think your code does not insert the current state into @cache.
  2. Since dictionary datastructure takes O(log n) time for {insertion|lookup},
    I changed @cache into 2D array which takes O(1) for lookup.
    I added one int variable into Node class to represent nodeid.
  3. I added psyco.full().

These fixes made your code run in 6.77secs.
Another big difference between your code and my code was tree datastructure.
Your code used reference to child node whereas my code used 2D adjacent list.
When I changed it into 2D adjacent list, your code run in 1.73secs.

22 days later

Thanks. Sorry for the late reply, I've been having trouble logging in.

Not inserting values into cache! That must be one of the stupidest mistakes I've ever made.

I didn't think that a change from O(log n) to a O(1) would matter much, especially because I thought a 2D list would have a high constant factor with the O(1) performance anyway. Thanks for pointing that out.

I was actually trying to solve it without having to resort to psyco if possible.

I really don't understand why changing to a 2D adjacency list would make things any faster. Maybe the overhead of the data structure was too high?

Thanks for all your help.

In my opinion, creating and accessing class objects take much longer time than 2D list. I checked running time of constructing tree and calc() function using the official dataset. In the experiment, 2D list runs about 3 times faster than class object for {tree construction|calc()}.

For the tree construction, generating Tree class and Node class which have 3 or more variables are clearly slower than 2D list. However, I still don't know why calc() also takes much longer time by using class objects.

By the way, this problem could be solved without psyco by using 2D adjacency list.

Suggested Topics

Want to read more? Browse other topics in Python or view latest topics.