10045 - Echo

junjieliang · Post by **junjieliang** » Fri Dec 05, 2003 4:59 pm

Is there any tricks with this problem? It appears very straightforward but I keep on getting WA. I am solving this with a queue. Any help?

Thanks.

.. · Post by .. » Thu Jan 22, 2004 8:30 pm

After reading 10045, I just guess that it can be solve by greedy algortihm. (Always takes the first repeating chcracter as the echo)

However, in the problem statistics so many people use seconds to solve this problem...... Does it mean that greedy not work??:o Could anyone give me some example? Thanks!

Per · Post by **Per** » Thu Jan 22, 2004 9:13 pm

The echo must come in the same order as the original text. So "ABBBBBBACCCCC" is "Not consistent with the theory".

And if you patch the greedy algorithm to handle that, you probably won't handle cases like "ABACADABACAD" where the answer is "An echo string with buffer size ten".

Maniac · Post by **Maniac** » Thu Sep 09, 2004 11:09 pm

Hmmm, I'm pretty sure my solution is correct but apparently it's not, cause I keep getting WA.

Can anyone help me with tricky and non-tricky input to test my solution?

Here are some test cases I created myself

Code: Select all

47
a
ABBBBBBACCCCC
ABACADABACAD
ABACADAABACADA
ABBACC
ABBACC012345012345
ABACCB
ABACCB012345012345
ABACBC
ABACBC012345012345
A0123456789A
A012345678A
A0123456789
0123456789
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
01234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678012345678AB
012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678A
AB
ACABCB
ABCAB
aa0123456789b
ABACADAABACADA
aaabcdeaaabcde
ZaaabcdeaaaZbcde
aaaaaaaaabaaaaaaaaab
aaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaab
aaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaab
aaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaab
aaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaac
aaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaac
abcd
012345012345abba
abba012345012345
a
ab
aa
abc
aba
abb
bba
aaa
0123456789
01234567890
0123456789a
ACABCB
ABCAB
aa0123456789b

with my results

Code: Select all

Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
An echo string with buffer size ten
An echo string with buffer size ten
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory

Are these results correct?

Thanks, Erik

.. · Post by .. » Fri Sep 10, 2004 7:41 am

Ouput from my accepted program

Code: Select all

Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
Not consistent with the theory
An echo string with buffer size ten
An echo string with buffer size ten
An echo string with buffer size ten
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory
An echo string with buffer size ten
Not an echo string, but still consistent with the theory
Not consistent with the theory

Maniac · Post by **Maniac** » Fri Sep 10, 2004 10:33 am

I see two differences between our outputs. For the input

Code: Select all

2
aaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaac
012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678A

my program gives

Code: Select all

Not consistent with the theory
Not consistent with the theory

and your AC program seems to give

Code: Select all

Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory

But I don't understand why my answer is wrong. In the first case for example, the last b can't be echoed within the buffer-size ten. Right?

What do you get for

Code: Select all

2
aaaaaaaaabaaaaaaaaac
0123456789012345678A

My result is again...

Code: Select all

Not consistent with the theory
Not consistent with the theory

Thanks for the help, Erik

.. · Post by .. » Fri Sep 10, 2004 1:43 pm

Code: Select all

aaaaaaaaabaaaaaaaaac

I don't remember all the detail, but I think this case can be considered like this:
1. the scientist type in aaaaaaaaab
2. they get echo aaaaaaaaa
3. the scientist type in c

It is still consistent.

Maniac · Post by **Maniac** » Fri Sep 10, 2004 2:33 pm

and what about this sentence in the problem statement:
'The ``buffer size ten'' means, that a character in s1 is not separated by more than nine characters from its echo in s2.'

Clearly, the b is surely separated by more than nine characters from it's echo, whatever is put after the c.

Am I missing something here?

.. · Post by .. » Fri Sep 10, 2004 2:54 pm

'The ``buffer size ten'' means, that a character in s1 is not separated by more than nine characters from its echo in s2.'

You should consider it as

'The ``buffer size ten'' means, that a character in s1 is not separated by more than nine characters of s1 from its echo in s2.'

Input:

Code: Select all

3
aaaaaaaaabaaaaaaaaac
aaaaaaaaabaaaaaaaaacdefghijk
aaaaaaaaabaaaaaaaaacdefghijkl

Output:

Code: Select all

Not an echo string, but still consistent with the theory
Not an echo string, but still consistent with the theory
Not consistent with the theory

Maniac · Post by **Maniac** » Fri Sep 10, 2004 3:01 pm

OK, I think I get it now. IMHO it would have been nice if this was explicitely stated in the problem, or clear from one of the examples....

*zucht* I'll have to change my algorithm pretty much then I'm afraid

Thanks .. and little joey

sidky · Post by **sidky** » Sun Jun 12, 2005 2:53 pm

I solved this problem dfs maintaing the states in a stl set. It solved in 24 seconds. Can anyone please tell me, how to speed this up? I can see that the fastest solutions take only fraction of second.
thanx in advance

suneast · Post by **suneast** » Thu Mar 04, 2010 11:53 am

I used backtracking to solve this problem.
I know my nearly "brute force" code will lead me TLE...
but, I really don't know how to function it more fast.

before posting my TLE code?

I want to know :
can any good guys give me some good ideas?
coule you tell me how to solve it efficiently ?

any help will do.
Thanks in advanced.

p.s: I have already past the test case above fast...It really seems working.

here is my TLE code.

Code: Select all

#include<iostream>
#include<string>

using namespace std;

int len,flag[1010],key[3],one;
char echo[1010];

/*
check whether I have already found the answer.

key[0]=1	means:found nothing
key[1]=1&&one	means:
		string is "Not an echo string, but still consistent with the theory"
key[2]=1	means:the string must be "echo"
*/
void chk()
{
	int i,bound=len-1,cnt=10;
	while(bound && cnt)
		if(!flag[bound])
			bound--,cnt--;
		else if(flag[bound]==1)
			break;
		else
			bound--;
	for(i=0;i<=bound;i++)
		if(!flag[i])
		{
			key[0]=1;
			return ;
		}
	for(;i<len;i++)
		if(!flag[i])
		{
			key[1]=1;
			return ;
		}
	key[2]=1;
}

/*
have to stop my DFS function while I have already found the answer?
*/
bool dfs(char c,int start,int end)
{
	if(end >= len)
	{
		chk();
		if(key[2] || (one && key[1]))
			return true;
		return false;
	}
	int bound=start,cnt=10;
	while(bound<len && cnt)
		if(flag[bound])
			bound++;
		else
			bound++,cnt--;

	for(int i=end;i<len && i<=bound;i++)
		if(!flag[i] && echo[i] == c)
		{
			flag[start]=1;
			flag[i]=2;
			int p=start;
			while(p<len && flag[p])
				p++;
			if(key[2] || (one && key[1]) || dfs(echo[p],p,(p>=i)?p+1:i) )
				return true;
			flag[start]=flag[i]=0;
		}
	chk();
	return false;
}

int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("10045.txt","w",stdout);

	int dataset;
	cin>>dataset;getchar();
	while(dataset--)
	{
		gets(echo);
		len=strlen(echo);

		char buf[256];
		int i;
		memset(buf,0,sizeof(buf));
		for(i=0;i<len;i++)
			buf[echo[i]]++;
		one=0;
		for(i=0;i<256;i++)
			if(buf[i]%2)
			{
				one=1;
				break;
			}
		if(len<=10 && one)
		{
			cout<<"Not an echo string, but still consistent with the theory"<<endl;
			continue;
		}
		memset(flag,0,sizeof(flag));
		key[0]=key[1]=key[2]=0;
		dfs(echo[0],0,1);
		if(key[2])
			cout<<"An echo string with buffer size ten"<<endl;
		else if(key[1])
			cout<<"Not an echo string, but still consistent with the theory"<<endl;
		else
			cout<<"Not consistent with the theory"<<endl;
	}

return 0;
}

OJ Board

10045 - Echo

10045 - Echo

10045 Echo: I just need some example

Re: 10045 - Echo