have implemented this solution as a single-pass Haskell program at http://ideone.com/vRag4 .
On 19 Aug 2010, at 08:13, Richard Braakman <[email protected]> wrote: > 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. > -- 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.
