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.
