On Mon, Aug 09, 2010 at 12:11:19PM -0400, Xiaomin Chen wrote: > Hi Richard, > > This is very interesting. We knew there was a linear algorithm for this, but > did not found it. Even the quadratic algorithm turns out to be a little > harder for the 1st problem in the final match.:) > I don't quite understand the reasoning below. See one question inline.
> > Step 3: If the whole sequence starts and ends with X, the second X > > does not need a push because there is an X at the bottom of the stack > > and it is possible to pop down to it instead. Represent this by deleting > > the second X. On the other hand, if the sequence ends with a different > > letter Y, then push and print X and forget about it. Represent this by > > deleting X and recording the extra push. Then repeat step 3 until there > > are no more letters. > > (There are no other options for reusing X because after Step 2 there > > are no more palindromic subsequences.) > > > > Here, "no more palindromic subsequences", from the input string, or from any > stack configuration? I meant from the input string. I was trying to say that there would be no way to save a push by popping all the way down to that X (before the end of the string) so we might as well record the push and then pretend there was no X. My reasoning was based on a strategy of leaving letters on the stack as long as possible, so that the ideal solution would be a series of pushes followed by a series of pops (with prints interspersed). My intuition was that since I had already gotten rid of all perfectly balanced (= palindromic) subsequences, the remaining subsequences would all leave some noise on the stack that would not be cleared up until the end. It turns out that I couldn't prove this, but Luke Pebody's modification of Step 3 was easier to tackle :) Please look at my reply to him. -- Richard Braakman (competing as Amtep) -- 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.
