719 - Glass Beads

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

Moderator: Board moderators

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

719 - Glass Beads

Post by Christian Schuster » Thu Apr 04, 2002 3:19 pm

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

Post by Adrian Kuegel » Thu Apr 04, 2002 4:51 pm

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>

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Thu Apr 04, 2002 5:02 pm

Thanks, got AC now...

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

719 wr ???? help

Post by jiangjun » Fri Aug 08, 2003 10:30 am

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

int flag1[10000],flag2[10000];


main(){
8) 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[(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+j)%len]==chf){
if(chf==prime&&s[ (flag2+len-j)%len ]!=prime||chf!=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
}

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

Bad Input

Post by howardcheng » Fri Sep 05, 2003 6:35 pm

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

37951ZR
New poster
Posts: 2
Joined: Mon Nov 03, 2003 2:31 pm
Location: Japanese

Me, too.

Post by 37951ZR » Fri Dec 12, 2003 6:44 pm

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

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

Post by Adrian Kuegel » Sat Feb 14, 2004 2:04 pm

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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Mon Feb 16, 2004 1:07 pm

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

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

Post by Adrian Kuegel » Mon Feb 16, 2004 1:15 pm

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

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

Post by howardcheng » Mon Feb 16, 2004 1:25 pm

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

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

Post by Adrian Kuegel » Mon Feb 16, 2004 1:35 pm

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Feb 16, 2004 2:37 pm

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

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

Post by Per » Mon Feb 16, 2004 2:50 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.

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

Post by Adrian Kuegel » Mon Feb 16, 2004 3:31 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Feb 16, 2004 3:48 pm

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). :)

Post Reply

Return to “Volume 7 (700-799)”