10679 - I Love Strings!!

All about problems in Volume 106. 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
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10679 - I Love String!! - Is rejudging possible?

Post by Cho » Thu Oct 06, 2005 9:13 am

Last year (when I was very new to UVa), I accidentally figure out the test cases of this problem and thus able to generate correct output even without reading the input. I really did so to see how high I can climb on the ranklist.

I now think what I did is a bit childish and like to remove the record. So, is it possible to append one more data set (random data is good enough) to the test cases and rejudge the solutions?

By the way, I believe those sub-1-second solution was doing similar thing as mine to achieve that result. (Please let me know if I am wrong.)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Oct 06, 2005 10:44 am

Hi Cho,

Are you sure you are talking about this problem? I see you have a fast time, but a printf solution would have 0.000 seconds. And yes, my solution is <1 second and it is genuine, as are many other sub second solutions from respectable people.

Personally, I wouldn't bother too much if you've made the occasional misstep; there are enough people who do this systematically without remorse.

For this problem, I don't think it would be a good idea to add more cases: there are some people who just made the time limit, and they would be disadvantaged. You could ask the judges to reorder the testcases, but I don't think they would be very willing to do so.
But I see you have a time of 0.383 seconds. It is a bit of work, but why don't you try to write an even faster genuine solution? It should be possible and then you clean your sleeves.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Oct 06, 2005 12:23 pm

I didn't keep the cheated solution so don't know exactly what I did. As I can remember, I scanf all the input, then printf the output y or n directly (I can determine the answer with a single if condition only) without any processing of the input strings. And this gave me .383 second.

That's why I think anyone with submission in similar running time cheated as well. I'm sorry about my judgement to those who really solved this problem with decent time.

I know suffix tree or suffix array are the state-of-the-art pattern matching algorithm with linear running time. But there is quite a lot of processing, I really cannot foresee I can implement any of them and solve this problem in less than one second.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Oct 08, 2005 10:28 am

I've just submitted the following WA code and it took 0.428 to finish. That's why it's too hard for me to imagine there are genuine solutions to solve it at similar or even faster speed.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char text[102400], query[1024];

void main()
{
   int t, n;
   
   for(scanf("%d", &t); t--; )
   {
      scanf("%s", text);
      
      for(scanf("%d", &n); n--; )
      {
         scanf("%s", query);
         printf("%c\n", 'y');
      }
   }
}

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 08, 2005 10:48 am

You can improve much on your reading part. The following gives WA in 0.086 seconds:

Code: Select all

#include <stdio.h>

char string[128*1024];
char query[1024];

int main(){
   int cases;
   int queries;
   
   scanf("%d\n",&cases);
   while(cases--){
      fgets(string,sizeof(string),stdin);
      /* ... */
      scanf("%d\n",&queries);
      while(queries--){
         fgets(query,sizeof(query),stdin);
         /* ... */
         }
      }
   return 0;
   }
I admit that this code is not very fail-safe, but it worked for me on this problem.
The reason that scanf is so slow for big input is that most compilers don't actually compile code for it, but include a little interpreter that processes the format string and input at runtime.

But it will be a great task to get the rest of the code under 0.3 seconds :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Oct 14, 2005 10:14 am

joey, thanks a lot for demystifying the ultra fast running time.
Stupid me.. forgetting the fgets function...
Although not as fast, I now manage to finish in 1.5 sec with suffix tree.

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

Run Time Error

Post by Salman » Tue Jan 31, 2006 11:38 am

I am having runtime error using strstr function . Can any one tell me Why?

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

10679 - I Love String (STL) Why TLE?

Post by Psyco » Fri Feb 03, 2006 1:40 pm

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;

idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}

Why TLE? :( :( :(
I used STL.....
Last edited by Psyco on Fri Feb 03, 2006 1:47 pm, edited 1 time in total.

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

Oh.

Post by scidong » Fri Feb 03, 2006 2:05 pm

You should search more.
There are many question like your question, and many answers on those
All living things are amazing thing.
一八???

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

Thanks

Post by Psyco » Fri Feb 03, 2006 2:16 pm

Thanks......

But I can't using KMP...

I am serching many question, But they are all says "Using KMP"

Need I using KMP?

Please.... Hint....

타임 리미트...I want to Accpted

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

Then...

Post by scidong » Fri Feb 03, 2006 2:19 pm

Then, Ask your tutor.
All living things are amazing thing.
一八???

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

RE:&#47932;&#51020;

Post by tmdrbs6584 » Fri Feb 03, 2006 2:20 pm

You are Hooked up!!!

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

10679 - I Love String ( STL ) Why TLE???

Post by Psyco » Fri Feb 03, 2006 2:21 pm

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;

idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}

Why TLE?
I used STL.....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Feb 03, 2006 3:25 pm

Psyco wrote:Why TLE?
I used STL.....
AFAIK, STL string's find() is implemented with O(nm) algorithm (n,m=length of strings.)
It would be a too trivial problem, if such algorithms were allowed to pass!
Need I using KMP?
You can also use suffix trees/arrays or Aho-Corasick to get accepted.

P.S. Please, don't create several identical threads!

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

Post by scidong » Sat Mar 04, 2006 8:18 am

Ye...
That must be TLE.
plz use kmp!
All living things are amazing thing.
一八???

Post Reply

Return to “Volume 106 (10600-10699)”