10045 - Echo

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

10045 - Echo

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10045 Echo: I just need some example

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!
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

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
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 10045 - Echo

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;
}


Post Reply

Return to “Volume 100 (10000-10099)”