I used Python to solve this problem, although I ultimately didn't
compete in this round. Basically, I took all the lines in the tree,
concatenated them, and replaced ')' with ' ) ' and '(' with ' ( '.
This makes sure that everything in the input is separated by spaces.
Then, I called the split() method of the resulting string, which
resulted in a list L of tokens: ['(', '0.5', 'furry', '(' ... ]. I
passed M = iter(L) to a function that creates a tree-like structure;
this function called M.next() to get each token in order. To get
subtrees, this function could just call itself recursively.
Since I did this outside of the contest, I don't have source code.
Feel free to comment on the approach, though.
I did consider a regular expression approach, but decided it was too
complicated and inefficient. Kudos for getting it to work!
Ultimately, I qualified from Round 1C as well. I didn't solve the
large input set for the last problem on it, though, because my
solution was just a quick brute-force algorithm for the smaller input
set. I'm going to have to learn a lot about dynamic programming
before Sept. 26th!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
