Hi guys, sorry for replying so late. I was kept busy and did not have time to read through this. By a rough look at Luke's message, I think this is the same path I went before. Once I thought there is this obvious linear solution, but all I could prove is that - We can ignore any consecutive letters from the INPUT, i.e., XX -> X - There is one optimal solution, where the STACK always has the form XYZXYZXYZ... But I mistakenly thought this implies similar in the input: - We can transform in the INPUT XYX -> X I don't have a neat way to get around that.
On the other hand, I see things promising from your writing. But I am not sure I follow the details. On Tue, Aug 10, 2010 at 4:19 AM, Richard Braakman <[email protected]>wrote: > 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]<google-code%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- 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.
