Moderator: Board moderators

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>

Christian Schuster
Learning poster

Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

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>
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Thanks, got AC now...

Christian Schuster
Learning poster

Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

### 719 wr ???? help

#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
}
jiangjun
New poster

Posts: 1
Joined: Fri Aug 08, 2003 10:21 am

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

Posts: 68
Joined: Thu Aug 21, 2003 1:56 am

### Me, too.

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

Posts: 2
Joined: Mon Nov 03, 2003 2:31 pm
Location: Japanese

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
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

Posts: 68
Joined: Thu Aug 21, 2003 1:56 am

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

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

Posts: 68
Joined: Thu Aug 21, 2003 1:56 am

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

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

adrian, what has been changed in the problem statements?
I had no topics related fixing mistakes.
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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.
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Adrian Kuegel wrote: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).
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Next