My questions are based on the information given in the analysis editorial. Please let me know where I am mistaken.
The first question is about actual implementation of the trie. Do we construct the whole trie first, and then recursively find f(v) of the root based on the f(v') of the children? The second question is about the two proofs given, one being the correctness proof and the other 'the pairing is of maximum size' proof. If I didn't get it wrong, the single node tree f(v)=1 would be the base case of the correctness proof. What I couldn't get here, is how the inductive step can be related to pairing two words. Aren't we supposed to... I don't know, compare a trie with n+1 nodes against one with n nodes? Or, is it the case that the inductive hypothesis already has a pair that share this n-suffix? For the maximum proof, I could not quite understand the following sentence: '... that there is no way to pair more than sum(f(c) for all c where c is a child node of v) words with accent-suffixes that are represented by the subtree but not by v directly.' If we use the given example, and look at the node "A", then we would know its children "J" and "H" have f(c) of 0 and 1 respectively, and their sum would be 1. How is it that we cannot pair more than 1 word with suffix of the subtree? I could see that the node "J" (being a subtree of node "A") can actually pair two words CODEJAM and JAM. What am I missing here? Finally, about the other approach given, which is 'to sort the reversed words alphabetically and take any two adjacent words with a longest common prefix, pair them, remove them from the list, and repeat.' I get that sorting them would get the words with same prefix to be adjacent to each other, but how do we find the longest among them? Do we iterate all of them before we are set on one pair of them, and keep track of the used prefixes? It sounds very slow to me. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/e2a4b49f-8c0f-42d7-9cc5-5193f452c9e9%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
