Thank you for looking at it :) I know that my explanation is a bit too long and complicated, which makes it both hard to follow and hard to be sure it's correct. (I'm referring to the one in my reply to Luke; the one quoted here didn't work out)
One approach I've been thinking about off and on is to rewrite my solution to one that makes a single pass and does not modify the input string. Now that Step 3 is simpler and just depends on the length of its input, it becomes possible to do Step 2 just by counting how many substitutions it would have made (since that determines the length of its output). And maybe casting the algorithm into a simpler form, especially one that does not transform the input string, will also lead to a simpler proof. I might do that this weekend :) Thanks, Richard Braakman (competing as Amtep) On Wed, Aug 18, 2010 at 02:35:11PM -0400, Xiaomin Chen wrote: > 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. > -- 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.
