Page 1 of 1
10045 - Echo
Posted: Fri Dec 05, 2003 4:59 pm
by junjieliang
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.
10045 Echo: I just need some example
Posted: Thu Jan 22, 2004 8:30 pm
by ..
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!
Posted: Thu Jan 22, 2004 9:13 pm
by Per
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".
Posted: Thu Sep 09, 2004 11:09 pm
by Maniac
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
Posted: Fri Sep 10, 2004 7:41 am
by ..
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
Posted: Fri Sep 10, 2004 10:33 am
by Maniac
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
Posted: Fri Sep 10, 2004 1:43 pm
by ..
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.
Posted: Fri Sep 10, 2004 2:33 pm
by Maniac
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?
Posted: Fri Sep 10, 2004 2:54 pm
by ..
'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
Posted: Fri Sep 10, 2004 3:01 pm
by Maniac
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
Posted: Sun Jun 12, 2005 2:53 pm
by sidky
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
Re: 10045 - Echo
Posted: Thu Mar 04, 2010 11:53 am
by suneast
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;
}