10438 - Meta Editor

[Dominik Michniewski]

Could anyone (I saw that Adrian only got Accepted ) tell me any special test cases for this problem ? I think, that I handle correctly all of cases, but got WA ....

Code: Select all

#include <stdio.h>
#include <ctype.h>

#define MAX	50
#define LEN	20000

char words[LEN/2][MAX+1],line[LEN+1];
int count;

int StrCmp(char *a,char *b)
{
	while(*a && *b && (*a == *b)) { a++; b++; }
	return (*a - *b);
}

void StrCpy(char *s,char *d)
{
	while(*s) { *d = *s; d++; s++; }
	*d = 0;
}

char *ReadWord(char *s)
{
	char t[MAX+1];
	int i = 0;

	while(*s && isspace(*s)) s++;
	while(*s && !isspace(*s))
	{
		t[i++] = *s;
		s++;
	}
	if(i > 0)
	{
		t[i] = 0;
		for(i=0;i<count;i++)
			if(StrCmp(words[i],t) == 0) break;
		if(i >= count) StrCpy(t,words[count++]);
	}
	return s;
}

int main(void)
{
	char *s;
	int i;

	while(gets(line) != NULL)
		if(line[0] == 0)
			printf("\n");
		else
		{
			count = 0;
			s = line;
			while(*s != 0) s = ReadWord(s);
			printf("%s",words[0]);
			for(i=1;i<count;i++) printf(" %s",words[i]);
			printf("\n");
		}
	printf("\n");
	return 0;
}

Regards
Dominik Michniewski

[Adrian Kuegel]

Only patterns that are not seperated by other words should be removed. But if after removing there are new patterns they should be removed, too.
Input:
a b a
a b c a b a b c
Output:
a b a
a b c

[Dominik Michniewski]

Thanks Adrian for hint. Finally I got it Accepted ...

Dominik Michniewski

[Whinii F.]

I just don't get it..

a b c a b a b c

As I think, each of 'a', 'b', 'c' serves as an independant word, then all repeated words are seperated by other words so no word is going to be removed.

Do I need to remove WORD PATTERNS that occur more than one time?
Then there can be more than one way to remove them and they will result differently..
[/quote]

[turuthok]

I remember this problem during the contest ... everybody had a really hard-time understanding what it wants.

Please confirm if I interpret Adrian's 2nd input correctly:

a b c a b a b c

-> Remove repeating "a b" pattern:

a b c a b c

-> Remove repeating "a b c" pattern:

a b c

Is that what this problem wants ???

Thanks,

-turuthok-

[Whinii F.]

turuthok:

Yes, it was that way.
I coded like that and got an AC.

But I'm still confused with the problem statement!

[yahoo]

I can't understand adrian's first input. Why the output of a b a will be a b a . i think it should be a b. The repeating word a should be removed. Will anybody kindly explain. I am getting wrong answer all the time.

[ChristopherH]

For this problem, it appears that 'repeated pattern' means some sequence of words which is repeated without any intervening words.

ie for some nonempty sequence of words W, a sequence ... W W ... is reducible to ... W ...

Which brings up the question of what order to reduce these 'redexes' in. There seems to be a nice confluence property which ensures that it doesn't matter which order you reduce in -- there's probably some simple proof of that but it's not occurring to my sleepy brain right at the moment. I'd be inclined to reduce 'largest first' since that will minimize the total number of reductions.

Incidentally, there are some annoying boundary cases for the tokenizing which can lead to WA even if you've got the concept right. The clean istringstream extraction approach didn't work for me, so I ended up tokenizing manually.

[Cletus]

Code: Select all

Problems 10429-10438 have to be the worst-written
problems I've seen. The only thing difficult about them is
working out what they are trying to say.

So "take a line of text as input and produce a line of output
without the words repeated" and "Produce a line of text for 
each line of input, after removing any repeated pattern" are
supposed to tell us to remove repeated groups of TWO OR
MORE words? Is that the idea?

Incredible.

[Cletus]

Following my previous posting, I now have'
to say "No, that can't be it".

From the problem statement:

Sample Input
test string test string test string
repeat repeat

Sample Output
test string
repeat

If "repeat repeat" is supposed to be reduced
to "repeat", then why on earth should "a b a"
be left alone as "a b a", as per an earlier posting?

Just what is this problem really asking
us to do?

[ChristopherH]

"a b a" does not reduce because there is an intervening "b" between the duplicated "a". Reduce duplicated sequences if and only if there are no intervening words.
"a b c a b c a b c" --> "a b c"
"a b c d a b c" --> "a b c d a b c" (intervening "d" prevents collapse of "a b c")

See above for further comments.

[kiusap]

Could please some of you guys that got Accepted post your program's output for my input?

is there any tricky input that i haven't noticed?

a blank line could not appear anywhere in the input, right?

Code: Select all

a b a c b a c b a b a c b c a c b c a c b a b c b a c a b a b a c b a c a b c b a
b c b c a c b a b a b c b a c a b a c b a c a b a b a b a b a b c a c a b c a c b
c b c a c b a b a b c b c a c a c a c a c b c a b a b a c b c b a b a c a c a c a
c a c a b c b a b a c b a c a b a b c a b c a c b c b c a c b c b a c b a c b a b
b a b c b a c a b c a c b c b a b c b a c a c a b c b c a c b c a c a c a c b a a
a c a b a c a b c a b c a b a b c a c b a c b c b c a b a b c b c b a b c b a b c
a b c b a b c a b a b a c b c a c a c b a c b a c b c b a c b a b c b c a b c b b
b c a c a c b c a c b a b a b c a b a c b c a c b c b c b c b c b c a c b a c b c
b a b a c a c b a b c b a c b a b c a c b a c b a b a c a b a b a b a c a b a c b
b c a b c b c a b a b c b c a b c b c b c a b a b a c b c b a b a b c b a b a c b
a c a c b c b a c b a c b c b a b c b c b c a b a c b a b a c a b a b c a c a b a
a c b c a c b a c b c b c a b c b a b a c b c b a c a b c a c a c a c b c b c a a
c a b c b c b a b a c b c a b c b c a b c a c a c a c a b c a b a c b a b a b c c
c b c a b c b a c a b c a c b a c b a c a c a c a c a c a b a b c b c b c b c a b
c a b c a c b c b c b c b c b c a c b c a c b a b a b a c a b c a b a b a c a b c
c a c a c a c b c b a c b a c b a c a b a c b a c a c b c a b c a b c b c a b a a
b c b c a b c a c a c a b a c a c a c a b a b a b c a c a c b a b c a b c b c b b
b c a b c b a b c b c b a c a c a c b a c a c b c a b c b a b c a c a b a c a c a
a c a b c b c a c a b a c b a b c a b a c a c a b c a c a c b c a c b c a c b a b
b a b a c b a b a c b a b a c a b a c b c b c b a c a b c b a c b a b c b a b c c
c b c b a b a b a b c b a b c a c b c a b a b a c a c b c a b a c a b c a b c a a
a c b c a c b a c a b a b a c b a b c b c b c b a c a c b c a c a c b a b a c a b
a b a c b a b c a b c b c a b a b a b a b a c a c a c a c b c b a b c b c a c a b
b c a b a b a b a b c a b c a b c a c b c b c b a c a b a c b c a c a b a b c a a
c b c a b a c b c a b a b c b c a c a c a b c a c a c b a b a b c a b c a c a b c
b a c a b c a c b a b a b c a c a c b a c a b c a c a c a b c b a c a c b c b c a
b a b a b a c b c a c a c b a c b a b c b a b a c a c a c a c b a c a b a c a c b
a b a b c a c a b c a b c a b c a c a c a c a c a c b c a b c b a c a b a b a c c
c b a c b c b c b a b c b c b c a c b a c a c b a c b a c a c a b a c b a c a c b
b c b a c b c b a c b a b c b c b a c b c a b a c b a b a c b a b a c a c a c b b
c b a c a c a b a b c a b c a c b a c b a c b c a b a c b a b a c a b a b c a c c
b c b a c b c a c a c a b a b a b c b a c a b c b a b a c a b c a c a b c b c b a
c a c a c b a c a b a c a c b a b c a c b c b c b a c b c a c a b a c a c b c a a
c a b c b a b a c a c a b c b a b a c b a c a b a c a b c b a c b c b c b a b c c
b a b a b c a c a b c a b c b a b c b c b c a c b c b a c b a c a c b a b a c b b
b a c b c a c a c a c a b c a c b c b c a c b c b c a b c b a b a c a c a b c b b
a c a b a c a b c b a b c a c a b a b c b a b c a c a b c a c b a c a c a b a c b
b a b a b a b c b c b c a b c a b c a b a c b a b a b a c b c a b c a b c a c a c
a b a b c b c b a c b a b a c b c b c b a b a b a b c b c a c b c a c a b c b c b
a b a c b c b c a b a b c b a c a b c b a c b c b c a b a b a c a c a c b c a b c
b c b a b a b c b a c b a b a b a b c a c a b c a b c b c a b a c a b a b c b c c
c a c a c a c a b a c a c b a c b a b c a b a b a c b a c a c a c a c a b a c a c
a b a c a c a c b c a b c a c a c b a b c a b a b a b c a b c b c b a b c b a b a
a b c b c b c a b a b c a c b a c a b c b c a b a c b c a b c a b a b c a b a c c
a b c a c b c a b c b a c b a c b c b a c a c b a b c a c b a c b c a b a c b c a
a c a c a b c a c b c a c b c b c b a c a b c a b c b c a b a c b a c b c a c a a
c a b c a b c b c a c b a b c b c b c a b c b a c a c a c b a b c b c a c b a b b
a c b a c b c b a c b c a b c a c a c b a c b a c b a c a c a c a b a c b c b a c
c b c b a b a c b a b c b a b c a c b a c a c b c a c a c b a c a b c a b a c b b
c a b a b c b c b a b a b a c a b c a b c b a c b c b c b c a b c a b a b a c b b
b a c b c a b a c b c b a c b c a c a b c a c b a c b a b c a c b c b a b a c b a
b c b a c a c a c b a b a c b a b c b a c a c a b a c a b c b c a c a c b a c a c
c a c b a c b a b c b a b c a c b a b c a c b a b c b c b c a c a b c a c b c b c
c b c a b c b c b c b a c a c b a b a b c b c b a b a b c b a b c a b a c a c a b
a c b a b a c b c b a c a b a c b a b c b c b c b a c b c a b c b a b a b a b a c
b c a c a c b a b a c a b a c a b c a c b c b a b c a c a c a b a b a c b c a b a
a b c b a c a c a c b a c b a c b a c b a c b c b a b a b c a b a c a c b a b a a
a c a b a c a b a b a b c a b c b a b c a c a b c a c a c b a c b a c a c b c b c
a b c a b a c b a c a b a b a c b a c b a b a c b c a b c b c b a c a b c a b c b
a b c b a c a b a b c a b a c a b c a b a b a b c a b c b c a c b c a b c a b a b
c a c b a c b a c a b c b a c b c a b a c a b c b a c a c a c b c b a c a c b a a
b a c a c a c a b a b a c a c a c a c b a c a c b c b c b a b a b a c a c a c a a
c a b c b a c a c b a b c b c a b a b a b a b c b a c a b c a b a b a b c a c a b
a c b a b c a c b a b c a b c b a c b c a c a c b c b a c b a b c b c b a c b c b
a c a c a b a c a c a b c a c b c a c a b a b a b a b a b a b c a c a b c a b a c
a c a b a b a b c a b c a c b a c a b a b c b a b c b c a c b a b a b a c b a c c
b c a b c b a c a b c b c b c a c a b c b c b c a b a b c b a c a c b c a b c a c
c a c b a c b a b c b a b c a b a b a b a b a b c b c a b a b a c b a c a c a b c
c a b a b c b a b a c a b a b a b c b c b c b c a c a b c b c b c a c b c b a b a
c a c a c a c b a b a b a b a c b a c a b c b c b c b c b c a b a b c b a c a c a
c b a b c b a c a b c a b c a c b c b c a b c a c b c b a c a c b c b a b c a c b
b a b c a b a c a b c a b c b a c a c b a b a c a b a c b a b c a c a b c b c b c
c a b c a b c b a c b c a b c b c a c b a b c b c a c a b c a c b a c b a c a b c
b a b a b a c a c a b c a b a b c b a b c b c a b a c b a c b c a b a c a b a c c
a c a b c a c b a c a c a b a b a c b a b c b a c b a c a b a b c b a c a c b a a
a b c b a c a c a c a c a b a b a b a b c b c a b a b c a c a b a b a c a b c b c
a c a c b c b c b a c a b c a b a c b c b c b c a b a c b a c b c b c a b a c a c
c b a c a c b a b a b a b a c a b c b c b a b c a c a c b c a c b a b a b c b c c
c b c b a c b c a c a c b a c a b c a c b a c a b a b c a c b a c b c a b c a b a
b c a c a c b c a c b c a b c b c b c a c a b a b a b a b a c b c a c b a c a c a
a b a c b a c b c b a b c a b a b c b c b c a b c b c b c a c b c a c a c b a b b
b a c b c b a b c b a b c b c a b a b c a c a b a b c b a c a c b c a c b c b a c
c b a c b c b a c b c b c b a b c a b c a b c b c b c a b a b c b c a c b c a b a
b a b a b c b a b a c b c a b a c b a b c b c a b c b a b c b c a c a c b a c a b
a c a c b c a c a c a b c a b a b a b a c b c b c b a b a c b c a b a b a b c b a
a c b a b a b a b a b a c a c b a c b c b c b c b a c b a c b c a b a b a b a b a
c b c b a b c a c a c b a c b a c a b c b a c a c b c a c a b a b a b a c b a b a
b a c a b a c a b c b c a c a c a b a b a b c a c b c b c a b c b a c a b c a b a
b a c b c a c a c b c b a c a c b c a c a b a c a b c b a c a c b a b c b c a c c
a c a b a c a c b c a c a b c a c b c a c b c a b a b c a c a b c a b a c a c a b
b c a c b a b c a c b c a b a b a b a c b a b c a b c b a b c a c b a c b a c b a
b c b a c a c a c b c b c a b a c b a c b a b c a c b a c b c a b a c b c b a c b
a c b c b c a b a b c b c a b c b c a b a b a c a c a b a c b a c b c b a c a c a
b a b a c b c b a c b a c b a c a b a c b c a b a b c a b a c a c b c b c a c b b
c a c a c a c a c b c a b a c b c b a b c a c a c a c b a b a c b c b c b a c a b
b a c b a c a c a c b c a c b c a b a c a b a c a b c a c a b a b c a b a c a c b
b a c b c b a b c a b c b a b c a c a c a c b c a c b a b c b c a c a c a c a b a
a c b a b a c b c a b a c b c b c b c b a c b a b c b c b a b c a b a c b a b a c
c b a b a c b a c b a b c b c b a c b c a c b c a c b c b a b c b a b c b c b c a
b a b c a c a b c a b a c b c b a b c a b c a b c b c b a b c a b a c b a b c b b

thanks

[kiusap]

this is what my WA program outputs:

Code: Select all

a b a c b c a c b a b c b a c a b c b a
b c a c b a b c b a c a b c a c b
c b c a c b a b c a c b c a b a c a
c a b c b a c a b c a c b a b
b a b c b a c a b c a c b a
a c a b c a c b c a b c b a b c
a b c b a b c a b a c b c a c b a b c b
b c a c b a b c a b a c b c
b a c b a b c a c b a c a b a c b
b c a b a c b
a c b a b c a b a
a c b c a b c b a c a b c a c b c a
c a b c b a c b c a b a c b a b c
c b c a b c b a c a b
c a b c a c b a c a b c
c a c b a c a b a c b c a b a
b c a b a c a b c a c b a b c b
b c a b c b a c b c a b c b a b c a b a c a
a c a b a c b a b c a b a c a b c a c b a b
b a c a b c b a b c
c b a b c a c b c a b a c a b c a
a c b c a c b a c a b a c b a b c b a c b c a c b a c a b
a b a c b a b c a b
b c a c b a c a b a c b c a
c b c a c b a b c
b a c a b c a c b a c a b c b a c b c a
b a c b c a c b
a b c a c b c a b c b a c a b a c
c b a b c a c b a c a b a c b
b c b a c b c a b a c b
c b a c a b c a c b c a b a c a b c a c
b c b a c b c a b c b a
c a c b a b c a c b c a b a c b c a
c a b c b a b c
b a b c a c b
b a c b c a b c b a c a b c b
a c a b c b a b c a c b a c a b a c b
b a b c a b a c b c a c
a b c b
a b a c b c a b c
b c b a b c
c a b a c b a b c a b a c
a b a c b c a c b a b c b a
a b c a c b a c a b a c b c a b a c
a b c a c b c a b c b a b c a c b c a b a c b c a
a c a b c a c b a c a b a c b c a
c a b c a c b a b
a c b c a c b a c a b a c
c b a b c a c b a c a b a c b
c a b c b a c b c a b a c b
b a c b c a c b a
b c b a c a b c a c b a c
c a c b a b c a c b c
c b c a b c b a b c a b a c a b
a c b a c a b a c b a b c b a c b c a b c b a c
b c a c b a c a b c a c b a b c a b a c b c a b a
a b c b a b c a b a c b a
a c a b c b a b c a c b c
a b c a b a c b c a b c b a c a b c b
a b c b a c a b c a c b c a b
c a c b a c a b c b a c b c a b a c a b c b a
b a c a
c a b c b a c a b
a c b a b c b a c b c a c b a b c b a c b
a c a b a c
a c a b c a c b a c
b c a b c b a c b c a c
c a c b a b c a b a c a b c
c a b c b a c a b c a c b a
c a c b a c a b c b a c a
c b a b c b a c a b c a c b
b a b c a b a c a b c b a c a b a c b a b c
c a b c b a c b c a c b a c a b c
b a c a b a c
a c a b c a c b a c a b a c b a b c b a
a b c b a c a b c
a c b a c a b a c b c a b a c
c b a c a b c b a b c a c b a b c
c b a c b c a c b a c a b c a c b c a b a
b c a c b c a b a c b c a c b a c a
a b a c b a b c a c b a b
b a c b a b c b a c
c b a b c a c b c a b a
b a b c b a c b c a b a c b a b c a c b a c a b
a c b c a b c b a
a c b c a b a
c b a b c a c b a c a b c b a c b c a b a c b a
b a c a b c a c b c a b c b a c a b a
b a c b c a b a c a b c b a b c a c
a c a b a c b c a b a c a b
b c a c b a b c a c b c a b a c b a b c a c b a
b c b a c b c a b a c b a b c a c b c a b a c b
a c b c a b a c a
b a c a b a c b c a c b
c a c b c a b a c b a b c a c b a c a b
b a c b c a b a c b
b a c b a b c a b a
a c b c a b a c b a b c a b a c
c b a b c a
b a b c a b a c b a b c b

[Christian Schuster]

I just tried to solve this beast once again and came to the conclusion that the order of elimination does matter!

This happens when I repeatedly try to eliminate with length=max..1, scanning from left to right:

Code: Select all

b a b a c a c b a b c b a c b a b c a c b a c b a b a c a b a>b a b a c a b a<c b
b a b a c a c b a b c b a c b a b c a c b a c b a b a c>a b a c<b
b a b a c a c b a b c b a>c b a<b c a c b a c b a b a c b
b a b a c a c b a b c>b a b c<a c b a c b a b a c b
b a b a c a c b a b c a c b a>c b a<b a c b
b a b a c a c b a b>c a c b a b<a c b
b a b a c a c b a>b a<c b
b a c>a c<b a b a c b
b a c b a>b a<c b
b a c>b a c<b
b a c b

And this is for length=1..max, again scanning from left to right:

Code: Select all

b a>b a<c a c b a b c b a c b a b c a c b a c b a b a c a b a b a b a c a b a c b
b a c>a c<b a b c b a c b a b c a c b a c b a b a c a b a b a b a c a b a c b
b a c b a b c b a c b a b c a c b a c b a>b a<c a b a b a b a c a b a c b
b a c b a b c b a c b a b c a c b a c b a c a b a>b a<b a c a b a c b
b a c b a b c b a c b a b c a c b a c b a c a b a>b a<c a b a c b
b a c b a b c b a>c b a<b c a c b a c b a c a b a c a b a c b
b a c b a b c b a b c a c b a c>b a c<a b a c a b a c b
b a c b a b c>b a b c<a c b a c a b a c a b a c b
b a c b a b c a c b a c a>b a c a<b a c b
b a c b a b c a c b a c a b a c b

Now spot the difference!

This problem definitely needs some rethinking, rewording and rejudging.

[TimeString]

My AC program gives output as below:

Code: Select all

a b a c b c a c b a b c b a c a b c b a
b c a c b a b c b a c a b c a c b
c b c a c b a b c a c b c a b a c a
c a b c b a c a b c a c b a b
b a b c b a c a b c a c b a
a c a b c a c b c a b c b a b c
a b c b a b c a b a c b a b c b
b c a c b a b c a b a c b c
b a c b a b c a c b a c a b a c b
b c a b a c b
a c b a b c a b a
a c b c a b c b a c a b c a c b c a
c a b c b a c b c a b a c b a b c
c b c a b c b a c a b
c a b c a c b a c a b c
c a c b c a b a
b c a c b a b c b
b c a b c b a c b c a b c b a b c a b a c a
a c a b a c b a b c a b a c a b c a c b a b
b a c a b c b a b c
c b a b c a c b c a b a c a b c a
a c b c a c b a c a b a c b a b c b a c b c a c b a c a b
a b a c b a b c a b
b c a c b a c a b a c b c a
c b c a c b a b c
b a c a b c b a c b c a
b a c b c a c b
a b c a c b c a b c b a c a b a c
c b a b c a c b
b c b a c b c a b a c b
c b a c a b c a c
b c b a c b c a b c b a
c a c b a b c a b a c b c a
c a b c b a b c
b a b c a c b
b a c b c a b c b a c a b c b
a c a b c b a b c a c b a c a b a c b
b a b c a b a c b c a c
a b c b
a b a c b c a b c
b c b a b c
c a b a c b a b c a b a c
a b a c b c a c b a
a b c a c b a c a b a c b c a b a c
a b c a c b c a b c b a b c a c b c a b a c b c a
a c a b c a c b a c a b a c b c a
c a b c a c b a b
a c b c a c b a c a b a c
c b a b c a c b a c a b a c b
c a b c b a c b c a b a c b
b a c b c a c b a
b c b a c a b c a c b a c
c a c b a b c a c b c
c b c a b c b a b c a b a c a b
a c b a c a b a c b a b c b a c b c a b c b a c
b c a c b a c a b c a c b a b c a b a c b c a b a
a b c b a b c a b a c b a
a c a b c b a b c a c b c
a b c a b a c b c a b c b a c a b c b
a b c b a c a b c a c b c a b
c a c b a c a b c b a c b c a b a c a b c b a
b a c a
c a b c b a c a b
a c b a b c b a c b
a c a b a c
a c a b c a c b a c
b c a b c b a c b c a c
c a c b a b c a b a c a b c
c a b c b a c a b c a c b a
c a c b a c a b c b a c a
c b a b c b a c a b c a c b
b a b c a b a c a b c b a c a b a c b a b c
c a b c b a c b c a c b a c a b c
b a c a b a c b c a b a c
a c a b c a c b a c a b a c b a b c b a
a b c b a c a b c
a c b a c a b a c b c a b a c
c b a c a b c b a b c a c b a b c
c b a c b c a c b a c a b c a c b c a b a
b c a b a c b c a c b a c a
a b a c b a b c a c b a b
b a c b a b c b a c
c b a b c a c b c a b a
b a b c b a c b c a b a c b a b c a c b a c a b
a c b c a b c b a
a c b c a b a
c b a b c a c b a c a b c b a c b c a b a c b a
b a c a b c a c b c a b c b a c a b a
b a c b c a b a c a b c a c
a c a b a c b c a b a c a b
b c a c b a b c a c b c a b a c b a b c a c b a
b c b a c b c a b a c b a b c a c b c a b a c b
a c b c a b a c a
b a c a b a c b c a c b
c a c b c a b a c b a b c a c b a c a b
b a c b c a b a c b
b a c b a b c a b a
a c b c a b a c
c b a b c a
b a b c a b a c b a b c b