719 - Glass Beads

[Christian Schuster]

Are there any special cases to check in problem 719? The problem seems to be quite simple, but I get WA every time.

<font size=-1>[ This Message was edited by: Christian Schuster on 2002-04-04 15:20 ]</font>

[Adrian Kuegel]

I had some problems with this problem,too. I think they have an input with more than 10000 characters. I got Accepted with an array with 100000 chars.

<font size=-1>[ This Message was edited by: Adrian Kuegel on 2002-04-04 16:52 ]</font>

[Christian Schuster]

Thanks, got AC now...

[jiangjun]

先是tl, 然后是wr ,各位高手请帮帮忙，这里是code;
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<fstream>
using namespace std;

int flag1[10000],flag2[10000];


main(){
int n,i,j,k,len,nf,temp,l1,l2,l3;
char chf,chs,prime;
string s;
cin>>n;
getline(cin,s); //get the characther of enter

for(k=0;k<n;++k){
getline(cin,s);
len=s.size();

chf='z';
for(i=0;i<len;++i)
if(s[i]<chf) chf=s[i]; //get the smallest alpha of string

prime = chf; //store the prime char

l1=l2=0; //initiate the length of the flags
chs='z'; //store the next smallest alpha
for(i=0;i<len;++i){
if(s[i]==chf&&s[(i-1+len)%len]!=chf){
flag1[l1++]=i;
if(s[(i+1)%len]<chs) chs=s[(i+1)%len];
}
}

if(l1==0) { cout<<'1'<<endl; continue;}
if(l1==1) { cout<<flag1[0]+1<<endl; continue; }

//**********************do if the satiuation is not satisfide*********************

copy(flag1,flag1+l1,flag2);
l2=l1; l1=0;
chf=chs; chs='z';

for(j=1;j<=len;++j){
for(i=0;i<l2;++i){
if( s[(flag2[i]+j)%len]==chf){
if(chf==prime&&s[ (flag2[i]+len-j)%len ]!=prime||chf!=prime){
flag1[l1++]=flag2[i];
if(s[ (flag2[i]+j+1)%len]<chs) chs=s[(flag2[i]+j+1)%len] ;
}//end if chf
}//end if s
}//end for i

if(l1==0) { cout<<flag2[0]+1<<endl; break; }
if(l1==1) { cout<<flag1[0]+1<<endl; break; }
if(l1==l2&&l1*j==len) {cout<<flag1[0]+1<<endl; break;}

copy(flag1,flag1+l1,flag2);
l2=l1; l1=0;
chf=chs; chs='z';
}
}//end for k
}

[howardcheng]

There is definitely input longer than 10000 characters. Would someone please fix this?

[37951ZR]

I got AC. but my program admit more than 10000 charactors.
(actually admit 30000 charactors in my program.)

[Adrian Kuegel]

Now the input doesn't contain any test case with more than 10000 characters. The old input was also too easy, so programs with O(n^2) algorithm got Accepted; this shouldn't be possible any more with the new input. But you can be sure that it is possible to get Accepted with the right algorithm without IO Optimisation. For example I submitted a JAVA program that uses the readln function of the example for program 100, it got Accepted in 2.354 seconds

[howardcheng]

What is the right algorithm? I used an O(n log n) algorithm and it now runs too long.

[Adrian Kuegel]

It is possible to solve this problem in O(n).

[howardcheng]

I suppose you can use a suffix tree? I used a suffix array and thought it was good enough.

[Adrian Kuegel]

You don't need any advanced data structure for this problem.
Hint: think of something similar to bfs.

[anupam]

adrian, what has been changed in the problem statements?
I had no topics related fixing mistakes.
please help.

[Per]

Hm, I don't think the input is large enough. I just received the rejudgement mail, and it turns out that one of my old O(n^2) solutions was rejudged from TLE to AC, whereas my O(n log n) solution (with a bad constant) was rejudged from AC to TLE. Now that's not a rejudgement you get every day.

Btw, thanks for the hint Adrian! I had been wondering for some time what the simple solution for this problem is.

[Adrian Kuegel]

adrian, what has been changed in the problem statements?

Anupam, you can be sure, I wouldn't change a problem specification. I voted against it, and I don't change my opinion in this matter.
I only increased the input size and corrected the mistake that input contains strings with length >10000.
Per: if you got Accepted with O(n^2), then your program must be very optimised. My O(n^2) program runs about 1 minute on the input.
If I would increase the judge input more, I fear it may happen that some O(n) programs will get TLE.

[Per]

Per: if you got Accepted with O(n^2), then your program must be very optimised. My O(n^2) program runs about 1 minute on the input.

Not particularly, actually, but it contains some silly prunings so that it handles strings of the form S^m (i.e. m concatenations of S) for some short string S efficiently (O(m*|S|^2) = O(n*|S|), to be specific). So if the judge input contains many cases like "abababababab....abab", it will run decently fast, but if one of the b's in the previous string is changed to an a, it will take almost forever (2-3 secs per test case on judge, I think).