719  Glass Beads
Moderator: Board moderators
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
719  Glass Beads
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 20020404 15:20 ]</font>
<font size=1>[ This Message was edited by: Christian Schuster on 20020404 15:20 ]</font>

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
719 wr ???? help
先是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<chf) chf=s; //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==chf&&s[(i1+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+j)%len]==chf){
if(chf==prime&&s[ (flag2+lenj)%len ]!=primechf!=prime){
flag1[l1++]=flag2;
if(s[ (flag2+j+1)%len]<chs) chs=s[(flag2+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
}
#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<chf) chf=s; //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==chf&&s[(i1+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+j)%len]==chf){
if(chf==prime&&s[ (flag2+lenj)%len ]!=primechf!=prime){
flag1[l1++]=flag2;
if(s[ (flag2+j+1)%len]<chs) chs=s[(flag2+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
}

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am
Bad Input
There is definitely input longer than 10000 characters. Would someone please fix this?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am

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

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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.
Btw, thanks for the hint Adrian! I had been wondering for some time what the simple solution for this problem is.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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.adrian, what has been changed in the problem statements?
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.
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 (23 secs per test case on judge, I think).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.