spoj: classical ⇝ rtree ⇝ Roger and tree

This would have been an easy problem if the N is <= 10000, as we can easily formulate the recurrence function.


lposra ←←←←← longestPathOfSubtreeRootedAt

                   ⇛⇛⇛⇛⇛⇛⇛⇛ lposra[i]            
                ⇗⇗
lposra[n] ⇶⇶ max                                       ⇰⇰⇰⇰ ∀ i ∈ children of n
                ⇘⇘
                   ⇛⇛⇛⇛⇛⇛⇛⇛ 1stMax(depths[i]) \
                              + 2ndMax(depths[i]) + 1

but as N can be 105 the recursive solution gave me SIGSEGV. i just couldn’t think of any other way to solve this so flatted my recursive function into traversing and resolving parts and submitted it with 9.35s. but there is a solution with 0.35s, I couldn’t think of another way to solve this. 😦

https://gist.github.com/7ead780ca408a750c591

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s