If it does work, step 3 can be simplified. By the time you reach step 3, there are no substrings of the form XX or XYX. Thus it must be of the form XYZXYZXYZ...
Then step 3 says: if the word starts and ends with the same letter, remove them both (losing length 2) and record 1 push, otherwise, just remove the first letter (losing length 1) and record 1 push. Thus the number of pushes is: X - 1 XY - 2 XYZ - 3 XYZX - 3 (YZ + 1) XYZXY - 4 XYZXYZ - 5 XYZXYZX - 5 (YZXYZ + 1) Thus if the sequence is of length 3k or 3k+1, you need 2k+1 pushes, and if the sequence is of length 3k+2 you need 2k+2 pushes. In particular, the number of pushes you need if the sequence is of length n is (2n div 3) + 1. Thus you can replace npush += pushcount(s); by npush += ((2 * strlen(s)) / 3) + 1; On 7 Aug 2010, at 00:07, Richard Braakman <[email protected]> wrote: > Today I've been practicing on the problems from the 2010 finals, and > for problem A (Letter Stamper) I found a linear-complexity solution > while the contest analysis only gives a quadratic one. I thought this > might be of interest to the group. > > Stop reading here if you don't want to see solutions to that problem yet! > > > > > --- spoiler -- spoiler -- spoiler -- spoiler -- spoiler -- spoiler -- > > > > > The basic approach: we're supposed to count the total number of pushes > and pops and prints, but the number of prints must be equal to the length > of the input string and the number of pops must be equal to the number of > pushes. Therefore, focus on just the pushes. > > The most naive strategy would be to push and print every letter in turn. > This would mean that every letter in the string represents a push of that > letter, and the prefix of the string represents the growing stack. > This strategy can be optimized in three steps while maintaining that model. > > Step 1: A sequence of the form XX does not need a push for the > second X because it can be printed right after the first X. We only > need to keep the first letter of each sequence of identical letters. > After this pass where every XX is substituted with X, every letter will > be different from its neighbors. > > Step 2: A sequence of the form XYX does not need a push for the > second X because it can pop Y instead. After printing XYX this way, > the stack will look like it would have if just X were pushed. > Represent this by replacing the XYX sequence with just X, and > record that there is now an extra push compared to the number > of letters. Keep doing step 2 as long as there are XYX patterns. > (It is possible to do all of the substitutions in a single pass, > so the complexity remains linear.) > > 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.) > > After Step 3 the push counter holds the optimal number of pushes, > and the answer is that plus the number of pops (which is the same) > plus the number of prints (which is the length of the input string). > > Beware of bugs in the above algorithm. I have only tested it, not proven > it correct. A proof or a counterexample would be warmly welcomed. > > Now follows my implementation. It is in C, and reads from standard input > and writes to standard output. It solves A-small-practice.in and > A-large-practice.in correctly. > > Thank you for your attention :) > > Richard Braakman > > > #include <stdio.h> > #include <stdlib.h> > #include <string.h> > > #define SMAX 7000 > > static char s[SMAX+2]; /* Leave room for newline and NUL */ > > /* Remove terminating newline */ > static void chomp(char *s) { > int len = strlen(s); > if (len > 0 && s[len-1] == '\n') > s[len-1] = 0; > } > > /* Eliminate duplicates, in-place in linear time */ > static void squeeze(char *s) { > int x, y; > if (!*s) > return; > x = 0; > for (y = 1; s[y]; y++) { > if (s[x] != s[y]) > s[++x] = s[y]; > } > s[++x] = 0; > } > > /* Replace all sequences of the form XYX with X, in-place in linear time. > * Return the number of substitutions. */ > static int subst(char *s) { > int x, y; > int count; > > if (!s[0] || !s[1] || !s[2]) > return 0; > /* Logic: s[x] and s[y] are logically adjacent but a physical gap will > * grow between them. Keep testing if s[x] is the middle element in > * the pattern. Then either advance by bringing s[y] across the gap, > * or delete them both by widening the gap. */ > x = 1; > y = 2; > count = 0; > for (y = 2; s[y]; y++) { > if (x > 0 && s[x-1] == s[y]) { > x--; > count++; > } else { > s[++x] = s[y]; > } > } > s[++x] = 0; > return count; > } > > /* Calculate how many of the string's leading characters need to be > * pushed in order to be able to do the remaining characters with > * just pops. */ > static int pushcount(char *s) { > int x, y; > y = strlen(s) - 1; > for (x = 0; x <= y; x++) { > if (s[x] == s[y]) /* Can s[x] be reused at the end to print s[y]? */ > y--; /* If yes, then s[y] does not need a push */ > } > return x; > } > > int main(void) > { > int ncases; > int casenr; > > int nprint, npush; > > fgets(s, sizeof(s), stdin); > sscanf(s, "%d", &ncases); > for (casenr = 1; casenr <= ncases; casenr++) { > fgets(s, sizeof(s), stdin); > chomp(s); > nprint = strlen(s); > squeeze(s); > npush = subst(s); > npush += pushcount(s); > printf("Case #%d: %d\n", casenr, npush*2 + nprint); > } > return 0; > } > > -- > 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.
